Important Questions

Fill Water questions

84. Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram/description/)

• Needs to build a increasing stack and it will allow you let where is left boundary.

85. Maximal Rectangle (https://leetcode.com/problems/maximal-square/description/) (Question 84's further question)

Square && Rectangle

836. Rectangle Overlap (https://leetcode.com/problems/rectangle-overlap/description/)

• Good question and you just make sure rec2's x1 >= rec1's x2 ... 4 conditions

223. Rectangle Area (https://leetcode.com/problems/rectangle-area/description/)

• 836 题升级版

Matrix

54. Spiral Matrix (https://leetcode.com/problems/spiral-matrix/description/)

• You need to traverse more nodes in horizontal.
• Mark top-left and bottom-right point.
• See https://leetcode.com/problems/spiral-matrix/solution/

Frequent Questions

What's difference between Comparator and Comparable?

1. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(16);
- class Cell implements Comparable<Cell>!

2. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(16n new MyComparator());
- class MyComparator implements Comparator<Cell>!

// Class whose objects to be sorted must implement this Comparable interface
public interface Comparable {
   public int compareTo(Object obj);
}

// Some third class can implement this interface to sort.
public interface Comparator {
    public boolean equals(Object obj);

    public int compare(T o1, T o2);
}

LCA Tree

236. Lowest Common Ancestor of a Binary Tree (https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/)
237. Lowest Common Ancestor of a Binary Search Tree (https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/)

Q5.3:Lowest common ancestors of k nodes.

public TreeNode LCA(TreeNode root, Set<TreeNode> set) {
    if (root == null || set.contains(root)) {
        return root;
    }

     TreeNode left = LCA(root.left, set);
     TreeNode right = LCA(root.right, set);

     if (left != null && right != null) {
         return root;
     }

     return left == null ? right : left;
}

Q5.4 LCA for two nodes in k-nary tree

Q5.5 Lowest common ancestors for k nodes of K nodes.

class TreeNode {
    int val;
    List<TreeNode> children;
}

public TreeNode LCA(TreeNode root, Set<TreeNode> nodes) {
    if (root == null || nodes.contains(root)) {
        return root;
    }

    int counter = 0;
    TreeNode tmp = null;
    for (TreeNode child : root.children) {
        TreeNode node = LCA(child, nodes);
        if (node != null) {
            counter++;
            if (counter > 1) {
                 return root;
            }
             tmp = node;
        }
    }

     return tmp;
}

Q5.6 LCA for two nodes a and b in a very large tree that contains billions of nodes.

Tree Path Questions

124. Binary Tree Maximum Path Sum (https://leetcode.com/problems/binary-tree-maximum-path-sum/description/) The max path from any node to any node

• Time complexity is O(n) and space complexity is O(logn) if tree is balanced.

Basic Questions

Difference between TCP and UDP

• Both TCP and UDP are protocols used for sending bits of data — known as packets — over the Internet.
• TCP is not just one way communication — the remote system sends packets back to acknowledge it is received your packets.
• TCP guarantees the recipient will receive the packets in order by numbering them.
• The recipient sends messages back to the sender saying it received the messages. If the sender does not get a correct response, it will resend the packets to ensure the recipient received them.
• Packets are also checked for errors.
• TCP is all about this reliability — packets sent with TCP are tracked so no data is lost or corrupted in transit.
• The UDP protocol works similarly to TCP, but it throws all the error-checking stuff out. All the back-and-forth communication and deliverability guarantees slow things down.
• When using UDP, packets are just sent to the recipient. The sender will not wait to make sure the recipient received the packet — it will just continue sending the next packets.
• If you are the recipient and you miss some UDP packets, too bad — you can not ask for those packets again. There is no guarantee you are getting all the packets and there is no way to ask for a packet again if you miss it, but losing all this overhead means the computers can communicate more quickly.
• UDP is frequently used for live broadcasts and online games.

TCP 三次握手

https://github.com/jawil/blog/issues/14

Combinations

77. Combinations (https://leetcode.com/problems/combinations/description/)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

40. Combination Sum II (https://leetcode.com/problems/combination-sum-ii/description/) Including the duplicated elements but all elements are positive.

41. Combination Sum IV (https://leetcode.com/problems/combination-sum-iv/description/) DP

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

377. Combination Sum IV (https://leetcode.com/problems/combination-sum-iv/description/)

• DP
• DFS + Memorization

Good reading for negative number followup: https://leetcode.com/problems/combination-sum-iv/discuss/85038/JAVA:-follow-up-using-recursion-and-memorization.

254. Factor Combinations (https://leetcode.com/problems/factor-combinations/description/) 容易出bug。 因为题目说不要直接返回target，很容易在选择时直接写i< target, 但是在这种情况下就无法满足最终target ＝＝ 1的情况。所以solution是在最终check 解的size是不是大于1.

Interval Questions

56. Merge Intervals (https://leetcode.com/problems/merge-intervals/description/)
57. Insert Interval (https://leetcode.com/problems/insert-interval/description/) good question 注意check 条件。
58. My Calendar I https://leetcode.com/problems/my-calendar-i/description/) good question using TreeSet
59. My Calendar III (https://leetcode.com/problems/my-calendar-iii/description/) bug: 当比较order时，如果order相同，需要end放在前面。
60. Non-overlapping Intervals (https://leetcode.com/problems/non-overlapping-intervals/description/)

Can I Win

394. Coins in a Line (https://www.lintcode.com/problem/coins-in-a-line/description)
395. Coins in a Line II https://www.lintcode.com/problem/coins-in-a-line-ii/description

public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
       if (values == null || values.length == 0) {
           return false;
       } else if (values.length <= 2) {
           return true;
       }
       
       Map<Integer, Integer> map = new HashMap<Integer, Integer>();
       map.put(values.length, 0);
       map.put(values.length - 1, values[values.length - 1]);
       map.put(values.length - 2, values[values.length - 1] + values[values.length - 2]);
       
       int first = getMoney(values, 0, map);
       int sum = 0;
       for (int val : values) {
        sum += val; 
       }
       
       return first * 2 > sum;
    }
    
    private int getMoney(int[] values, int pos, Map<Integer, Integer> map) {
        
        if (pos > values.length) { //bug
            return 0;
        }
        
        if (map.containsKey(pos)) {
            return map.get(pos);
        }
        
        int val = Math.max(
            Math.min(getMoney(values, pos + 2, map), getMoney(values, pos + 3, map)) + values[pos],
            Math.min(getMoney(values, pos + 3, map), getMoney(values, pos + 4, map)) + values[pos] + values[pos + 1]);
        
        map.put(pos, val);
        return val;
    }
}


public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
       if (values == null || values.length == 0) {
           return false;
       } else if (values.length <= 2) {
           return true;
       }
       
       Map<Integer, Integer> map = new HashMap<Integer, Integer>();
       map.put(values.length, 0);
       map.put(values.length - 1, values[values.length - 1]);
       map.put(values.length - 2, values[values.length - 1] + values[values.length - 2]);
       
       
       int sum = 0;
       for (int val : values) {
        sum += val; 
       }
       
       int first = getMoney(values, 0, map);
       
       return first * 2 > sum;
    }
    
    private int getMoney(int[] values, int pos, Map<Integer, Integer> map) {
        
        if (pos > values.length) { //bug
            return 0;
        }
        
        if (map.containsKey(pos)) {
            return map.get(pos);
        }
        
        int sum = 0;
        for (int i = pos; i < values.length; i++) {
            sum += values[i];
        }
        
        int val = sum - Math.min(getMoney(values, pos + 1, map), getMoney(values, pos + 2, map));
        
        map.put(pos, val);
        return val;
    }
}


public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        } else if (values.length <= 2) {
            return true;
        }
        
        int[] f = new int[values.length + 1];
        int size = values.length;
        f[size] = 0;
        f[size - 1] = values[size - 1];
        f[size - 2] = values[size - 1] + values[size - 2];
        f[size - 3] = values[size - 3] + values[size - 2];
        
        for (int i = size - 4; i >= 0; i--) {
            f[i] = Math.max(
                Math.min(f[i + 2], f[i + 3]) + values[i],
                Math.min(f[i + 3], f[i + 4]) + values[i] + values[i + 1]
                );
        }
        
        int sum = 0;
        for (int val : values) {
            sum += val;
        }
        
        return f[0] * 2 > sum;
    }
}


public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        } else if (values.length <= 2) {
            return true;
        }
        
        int[] f = new int[values.length + 1];
        int size = values.length;
        f[size] = 0;
        f[size - 1] = values[size - 1];
        f[size - 2] = values[size - 1] + values[size - 2];
        f[size - 3] = values[size - 3] + values[size - 2];
        
        for (int i = size - 4; i >= 0; i--) {
            f[i] = Math.max(
                Math.min(f[i + 2], f[i + 3]) + values[i],
                Math.min(f[i + 3], f[i + 4]) + values[i] + values[i + 1]
                );
        }
        
        int sum = 0;
        for (int val : values) {
            sum += val;
        }
        
        return f[0] * 2 > sum;
    }
}


public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        } else if (values.length <= 2) {
            return true;
        }
        
        int[] f = new int[values.length + 1];
        int size = values.length;
        f[size] = 0;
        f[size - 1] = values[size - 1];
        f[size - 2] = values[size - 1] + values[size - 2];

        int sum = values[size - 1] + values[size - 2];
        
        for (int i = size - 3; i >= 0; i--) {
            sum += values[i];
            f[i] = sum - Math.min(f[i + 1], f[i + 2]);
        }
        
        return f[0] * 2 > sum;
    }
}

To Do

https://leetcode.com/problems/set-intersection-size-at-least-two/solution/ https://leetcode.com/problems/task-scheduler/description/