Skip to content

Important Questions

Jump to bottom
Xin Wan edited this page Aug 4, 2018 · 20 revisions

Fill Water questions

  1. 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.
  1. Maximal Rectangle (https://leetcode.com/problems/maximal-square/description/) (Question 84's further question)

Square && Rectangle

  1. Rectangle Overlap (https://leetcode.com/problems/rectangle-overlap/description/)
  • Good question and you just make sure rec2's x1 >= rec1's x2 ... 4 conditions
  1. Rectangle Area (https://leetcode.com/problems/rectangle-area/description/)
  • 836 题升级版

Matrix

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

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

  1. Lowest Common Ancestor of a Binary Tree (https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/)
  2. 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

  1. 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

  1. 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],
]

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

  2. 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.
  1. 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.

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

Interval Questions

  1. Merge Intervals (https://leetcode.com/problems/merge-intervals/description/)
  2. Insert Interval (https://leetcode.com/problems/insert-interval/description/) good question 注意check 条件。

Clone this wiki locally