IVN
0%

Top_Interview_Questions

Posted on Edited on In
Symbols count in article: 8.5k Reading time ≈ 8 mins.

128. Longest Consecutive Sequence

要求：O(n) time

法一：pq

此实现为排队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间

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
public class LeetCode128 {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
        }
        int res=1;
        int cur=1;
        int pre=Integer.MIN_VALUE;
        while(!pq.isEmpty()){
            int i=pq.poll();
            if(pre!=Integer.MIN_VALUE){
                if(i==pre+1){
                    cur++;
                    res=Math.max(res,cur);
                }else if(i==pre){
                    continue;
                }else{
                    cur=1;
                }
            }
            pre=i;
        }
        return res;
    }
}

法二：set

HashSet and Intelligent Sequence Building

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
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

Complexity Analysis

  • Time complexity : O(n)O(n).

    Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for n iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n⋅n) complexity, the nested loops actually run in O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.

  • Space complexity : O(n)O(n).

    In order to set up O(1)O(1) containment lookups, we allocate linear space for a hash table to store the O(n)O(n) numbers in nums. Other than that, the space complexity is identical to that of the brute force solution.

134. Gas Station

Time Limit Exceeded

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
public int canCompleteCircuit(int[] gas, int[] cost) {
    List<Integer> starts=new LinkedList<>();
    int n=gas.length;
    int[] dif=new int[n];
    //dif[i]=change of gas from gas[i] to gas[i+1] or gas[0]
    for (int i = 0; i < n; i++) {
        dif[i]=gas[i]-cost[i];
        if(dif[i]>=0){
            starts.add(i);
        }
    }
    for (Integer start : starts) {
        int tank=0;
        int count=0;
        int i=start;
        while(count!=n){
            tank+=gas[i];
            tank-=cost[i];
            if(tank<0){
                break;
            }
            i=(i+1)%n;
            count++;
        }
        if(count==n){
            return start;
        }
    }
    return -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
public int canCompleteCircuit(int[] gas, int[] cost) {
    List<Integer> starts=new LinkedList<>();
    int n=gas.length;
    int total=0;
    int min=0;
    int start=0;
    //dif[i]=change of gas from gas[i] to gas[i+1] or gas[0]
    for (int i = 0; i < n; i++) {
        total+=gas[i]-cost[i];
        if(total<min){
            start=(i+1)%n;
            min=total;
        }
    }
    int tank=0;
    int count=0;
    int i=start;
    while(count!=n){
        tank+=gas[i];
        tank-=cost[i];
        if(tank<0){
            break;
        }
        i=(i+1)%n;
        count++;
    }
    if(count==n){
        return start;
    }
    return -1;
}

136. Single Number

You must implement a solution with a linear runtime complexity and use only constant extra space.

Approach 4: Bit Manipulation

Concept

  • If we take XOR of zero and some bit, it will return that bit
    • a⊕0=a
  • If we take XOR of two same bits, it will return 0
    • a⊕a=0
  • a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
    int res=0;
    for (int num : nums) {
        res^=num;
    }
    return res;
}

138. Copy List with Random Pointer

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
public class LeetCode138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        Node p=head;
        Node pre=null;
        while(p!=null){
            if(!map.containsKey(p)){
                map.put(p,new Node(p.val));
            }
            Node cur=map.get(p);
            if(pre!=null){
                pre.next=cur;
            }
            if(p.random!=null){
                map.putIfAbsent(p.random,new Node(p.random.val));
                cur.random=map.get(p.random);
            }
            pre=cur;
            p=p.next;
        }
        return map.get(head);
    }
}

139. Word Break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean wordBreak(String s, List<String> wordDict) {
    int n=s.length();
    boolean[] dp=new boolean[n+1];
    dp[0]=true;
    //dp[i]: s[0,i-1]
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            //[0,j-1] [j,i-1]
            if(dp[j] && wordDict.contains(s.substring(j,i))){
                dp[i]=true;
                break;
            }
        }
    }
    return dp[n];
}

140. Word Break II

注意：

  • 本题用backtracking的参数范围:

    • 1 <= s.length <= 20
    • 1 <= wordDict.length <= 1000
    • 1 <= wordDict[i].length <= 10
    • s and wordDict[i] consist of only lowercase English letters.
    • All the strings of wordDict are unique.

  • 上一题dp的参数范围:

    • 1 <= s.length <= 300
    • 1 <= wordDict.length <= 1000
    • 1 <= wordDict[i].length <= 20
    • s and wordDict[i] consist of only lowercase English letters.
    • All the strings of wordDict are unique.
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
public class LeetCode140 {
    List<String> res;
    List<String> path;
    public List<String> wordBreak(String s, List<String> wordDict) {
        res=new ArrayList<>();
        path=new ArrayList<>();
        backtracking(s,wordDict,0);
        return res;
    }

    void backtracking(String s, List<String> wordDict,int start){
        if(start==s.length()){
            StringBuilder sb=new StringBuilder();
            for (String s1 : path) {
                sb.append(s1);
                sb.append(" ");
            }
            sb.deleteCharAt(sb.length()-1);
            res.add(sb.toString());
        }
        for (int i = start; i < s.length(); i++) {
            if(wordDict.contains(s.substring(start,i+1))){
                path.add(s.substring(start,i+1));
                backtracking(s,wordDict,i+1);
                path.remove(path.size()-1);
            }
        }
    }
}

148. Sort List

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Approach 1: Top Down Merge Sort

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

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode mid = getMid(head);
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        return merge(left, right);
    }

    ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummyHead.next;
    }

    ListNode getMid(ListNode head) {
        ListNode midPrev = null;
        while (head != null && head.next != null) {
            midPrev = (midPrev == null) ? head : midPrev.next;
            head = head.next.next;
        }
        ListNode mid = midPrev.next;
        midPrev.next = null;
        return mid;
    }
}

Approach 2: Bottom Up Merge Sort

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

class Solution {
    ListNode tail = new ListNode();
    ListNode nextSubList = new ListNode();

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        int n = getCount(head);
        ListNode start = head;
        ListNode dummyHead = new ListNode();
        for (int size = 1; size < n; size = size * 2) {
            tail = dummyHead;
            while (start != null) {
                if (start.next == null) {
                    tail.next = start;
                    break;
                }
                ListNode mid = split(start, size);
                merge(start, mid);
                start = nextSubList;
            }
            start = dummyHead.next;
        }
        return dummyHead.next;
    }

    ListNode split(ListNode start, int size) {
        ListNode midPrev = start;
        ListNode end = start.next;
        //use fast and slow approach to find middle and end of second linked list
        for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
            if (end.next != null) {
                end = (end.next.next != null) ? end.next.next : end.next;
            }
            if (midPrev.next != null) {
                midPrev = midPrev.next;
            }
        }
        ListNode mid = midPrev.next;
        midPrev.next = null;
        nextSubList = end.next;
        end.next = null;
        // return the start of second linked list
        return mid;
    }

    void merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode newTail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                newTail.next = list1;
                list1 = list1.next;
                newTail = newTail.next;
            } else {
                newTail.next = list2;
                list2 = list2.next;
                newTail = newTail.next;
            }
        }
        newTail.next = (list1 != null) ? list1 : list2;
        // traverse till the end of merged list to get the newTail
        while (newTail.next != null) {
            newTail = newTail.next;
        }
        // link the old tail with the head of merged list
        tail.next = dummyHead.next;
        // update the old tail to the new tail of merged list
        tail = newTail;
    }

    int getCount(ListNode head) {
        int cnt = 0;
        ListNode ptr = head;
        while (ptr != null) {
            ptr = ptr.next;
            cnt++;
        }
        return cnt;
    }
}