Random number generator with excepted nums
[m216] Check if any interval overlaps given number

CLRS book has a very good sample code snippet that works for determine if an
interval overlaps anyone of a given list of intervals.
[M234] Check if a number is power of 3

First find the range of the number by squaring prev number. Then do a binary
search between start and end points.

If the question is to check if multiple of three, then we only need to double
the prev number every time to get the range.
[M237] Longest substring with at most K distinct chars.

Keep a LRU cache. Scan the string. After adding a new char, check if the number
of distincts is greater than 2, if not, update max. Otherwise, take the oldest
number in the LRU, update start point and evict it from the LRU.

Seems if in the while loop doing a "check status" -> "update max" -> "update
status" is error prone: whether or not to update status doesn't depends on the
loop variable.
[M229] Iterator for zipped integer stream

- Remember Iterator is a generic interface.
- In case the zipped stream is given as a linked list, you'll utilize a normal
  iterator.
- You'll need a buffer and hasNext() returns false when the buffer is empty.
- When calling next(), you'll need to update the buffer, and reload it if necessary.
[M231] Longest cycle size
[GOOG] Minimum difference allocation

DP.
Questions containing "max", "min", "best" are very likely dp-able. This question
is best approached by asking "how do we use the last hat?". We can either not
using that, or use that on the last person.
[M184] Implement readline using c/c++

A few takeaways:
- Use c++ stl(vector here) and smart pointers(not used here)
- static variable storing global states (not sure if good practice)
- state-transition diagram is very helpful
[M185 GOOG FB] Longest Increasing Subsequence

Only return the size of LIS.
Keep an ascending aray. Everytime reading an element from input array, we try to
insert into the ascending array. The insertion position is where the leftmost
greater element is in the ascending array is.
[M186 GOOG] Max number in sliding window.

Maintain a deque storing indices into the array. The deque will form an
non-ascending array. Each slide,
1. Compare the new element with the last element in the deque, if non-greater,
enqueue. Otherwise, dequeue until queue is empty or the queue last element is
greater.
2. If the queue head is the same as the index of the item to be evicted from the
window, remove that from the queue.
[M186 varient] Iterator class for max in sliding window

Take away:
- (minor) don't forget remove() API
- Iterator interface can assist the logic while writing normal version code. You
  can image the loop variable is true when hasNext() is true.
Add README
Change a few bruteforcer class to inner classes
Find the min window covering all chars in target string

Assuming no dup chars in target string.
LRU.
Maintain a LRU storing the last appeared position of target chars. Update min on
the fly.
[M188 GOOG] Convert an integer x to sign*p*2^b format

The key is to find the greatest b s.t. x can be divisible by 2^b. This be is
found by exponential-grow-and-binary-search. Notice since we're using 2 as the
base, to check divisibility you can chek number of tailing zeros.
Edge cases are zero and Integer.MIN_VALUE (overflow when doing Math.abs)
BinaryTree iterative serializer/deserializer

Use preorder traversal to serialize.
[M195 Twitter] Longest path in N-ary tree

Very similar to "longest path in binary tree".
Clean up in binaryDeserializer test
[M197 GOOG] Integer division supporting infinite decimal

The key is to find out where dividend starts to repeat. The repeated quotient
starts RIGHT AFTER the first repeated dividend.

This solution still has overflow problems unresolved. Besides it's rather
verbose. Call for more concise solutions.
[M150] Longest subarray with equal number of ones and zeros

Similar to the problem to check if exists a zero-sum subarray