Skip to content

Important Questions

Jump to bottom
Xin Wan edited this page Jul 11, 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

Clone this wiki locally