My Notes

1. Largest rectangle in histogram, max amount of trapped rain water
2. When to use what sorting algorithm, why most of time quick sort is better than merge and heap sort
3. Some good algorithms based upon trie
4. Shortest string containing all 4-digit number (0000-9999, De Bruijn sequence)
5. DP to minimize cost of cutting logs
6. Print out all numbers containing 5 for a given n (groupon)
7. Construct a long string by repeating a short string (amazon) 
8. Fib series in O(logn)
9. Huffman code
10. Given two sorted array M and N with size m and n, each time pick one number from M and one number from N and add them them. Try to find the k smallest sum (given two ascending sorted array A and B)
11. Dutch national flag problem
12. Given an int array, find out if there exist 3 ints that can be used to contruct a triangle in O(nlogn). (51. google interview (3 numbers to form triangle))
13. Given a set of movie starting / ending times, find out at most how many movies can be watched without conflict. Is that a graph problem? (51. google interview (reasonable but also requires some work)) 
14. K-d tree to find out nearest neighbor in a given points set 
15. Given n x n matrix with increasing rows and columns, find out k-th smallest element in O(nlogn)
16. 平面N个点，找两点连线正好把点分到两半 
17. Given a function of "int Read4096(char * buf)" implement "int ReadBytes(char * buf, num_bytes)"
18. Sort linked list (better use merge sort rather than quick sort) 
19. Mirror a BT 
20. Count reverse ordered pair
1. stackoverflow
2. (53. facebook interview (how to use reverse ordered pair))