Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Solution

For finding the majority elements, there is a very famous algorithm Boyer–Moore majority vote algorithm. But the original algorithm is for finding the majority number that appears more than ⌊ n/2 ⌋ times. So we need to modify the algorithm to find numbers that appears more than n/3. Use 2 counter to keep tracking of 2 candidate numbers.

For every number in array,

1. Check if it is one of the two candidate numbers.
2. Check if its’ counter is 0, if counter is 0, update candidate number and set counter to 1.
3. If it is not satisfy either of the above conditions. Decrement the counter by 1.

After the first round loop, we have two “majority” numbers but we don’t know if they appears more than n/3 time. So we start another loop to count the occurrence time.

Finally, if the occurrence time is more than n/3, add it to result set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ret  = new LinkedList<Integer>();
        if( nums.length == 0 ){
            return ret;
        }
        int count1 = 0;
        int count2 = 0;
        int m1 = 0;
        int m2 = 0;
        for( int n : nums ){
            if( n == m1 ){
                count1++;
            }else if( n == m2 ){
                count2++;
            }else if ( count1 == 0 ){
                m1 = n;
                count1 = 1;
            }else if ( count2 == 0 ){
                m2 = n;
                count2 = 1;
            }else{
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for(int n : nums ){
            if( n == m1 ){
                count1++;
            }else if( n == m2 ){
                count2++;
            }
        }
        
        if( count1 > nums.length/3 ) ret.add(m1);
        if( count2 > nums.length/3 ) ret.add(m2);
        
        return ret;
        
    }
}

Question

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

1
2
3
4

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution

We can solve this problem in 2 ways.

1. Use sliding window to get every 10-letter-long subString of the input string. Store them in a hash set. Every time insert new substring to hash set, check if it’s exist in hash set. If exist, put it in a result hash set. We choose hash set to store the result, because the result need to be unique.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   public class Solution { public List<String> findRepeatedDnaSequences(String s) { HashSet<String> subStrings = new HashSet<String>(); HashSet<String> repeatedSubstrings = new HashSet<String>(); for(int i = 0 ; i <= s.length()-10; i++){ String subS = s.substring(i,i+10); if( !subStrings.add(subS) ){ repeatedSubstrings.add(subS); } } return new ArrayList(repeatedSubstrings); } }

2. The solution before is pretty straight forward but need a lot memory to store the sub-strings. We can optimize the algorithm by using bit manipulate. There are only 4 letters, we can use 2 bit to present a letter. 00, 01, 10, 11 stand for A, C, T, G. An integer is 32 bits. so we can use an integer rather than a string to present a substring.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   public class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> result = new LinkedList<String>(); if(s == null || s.length() < 10 ){ return result; } HashMap<Character,Integer> map = new HashMap<Character, Integer>(); map.put('A',0); // 00 map.put('C',1); // 01 map.put('T',2); // 10 map.put('G',3); // 11 Set<Integer> subStrings = new HashSet<Integer>(); Set<Integer> repeated = new HashSet<Integer>(); int temp = 0; for(int i = 0 ; i < s.length(); i++ ){ temp = (temp << 2) + map.get( s.charAt(i) ); if( i >= 9 ){ temp = temp & ( (1 << 20) - 1 ); // temp & 111111 , filt the last 20 digits. if( subStrings.contains(temp) && !repeated.contains(temp) ){ result.add( s.substring(i-9,i+1) ); repeated.add(temp); }else{ subStrings.add(temp); } } } return result; } }

Question

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution

This meaning of this problem is to find the next closest number that greater than current number. If the number is in descending order, it means it’s already the biggest permutation, then sort it in ascending order.

There are some principles we should to know before start to solve this problem:

1. Descending order is the biggest permutation of a set of numbers.
2. On the contrary, ascending is the smallest permutation.
3. To minimize the increased amount, we have to make the highest changed position increase as less as we can.

Following the principles we can solve this problem in 3 steps:

1. Start from tail, find the first element with index i that satisfy num[i-1] < num[i]. So from num[i] to num[n-1] is in descending order.
2. In order to minimize the increase amount, we need to find a closest number with num[i-1] in the descending list to exchange with num[i-1].
3. After exchange, from num[i] to num[n-1] is still in descending number, it means it’s in the greatest permutation. In order to keep the whole number increase minimum, remember we just increased the highest position? Then we need to make the remaining part of as small as possible, so we just reversely sort the num[ i , n-1 ].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length <= 1){
            return;
        }
        
        int numberLength = nums.length;
        int firstIndex = -1;
        int secondIndex = -1;
        int exchangeNumberIndex = -1;
        for(int i = numberLength-1; i >0; i--){
            if( nums[i-1] < nums[i]){
                firstIndex = i-1;
                secondIndex= i;
                break;
            }
        }
        if( firstIndex == -1 ){
            reverse(0,numberLength-1,nums);
            return;
        }
        for(int i = numberLength-1 ; i >= secondIndex ; i--){
            if( nums[i] > nums[firstIndex] ){
                exchangeNumberIndex = i;
                break;
            }
        }
        swap(firstIndex, exchangeNumberIndex, nums);
        reverse(secondIndex,numberLength-1,nums);

    }
    
    private void swap(int n, int m, int[] numbers){
        int temp = numbers[n];
        numbers[n] = numbers[m];
        numbers[m] = temp;
    }
    
    private void reverse(int startIndex, int endIndex, int[] numbers){
        while( startIndex < endIndex ){
            swap(startIndex++,endIndex--,numbers);
        }
    }
}

Question

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

1
2
3
4
5

  0
  |
  1
 / \
2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

1
2
3
4
5
6
7

0  1  2
 \ | /
   3
   |
   4
   |
   5

return [3, 4]

Solution

First of all, we can think a simple situation. What’s the MHT for a one path tree? The answer is pretty straight forward, the middle 1 or 2 points, depends on even or odd nodes the tree has, is the MHTs.

Question

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution

Because the head of linked list could be duplicated, so we need to add a dummy head node to the original linked list. Then check the values of node, if it’s duplicated just skip the node and redirect the pointer to next node.