Course 8: Data Structure

1. Linear data structure
   1. Queue: O(1) push, O(1) pop, O(1) top
   2. Stack: O(1) push, O(1) pop, O(1) top
   3. Hash: O(1) insert, O(1) delete, O(1) find;
      1. Open hash (array of linked list), closed hash (next array element, do not support delete);
      2. Rehash;
      3. HashTable vs. HashSet vs. HashMap
2. Tree data structure
   1. Heap: O(logN) add, O(logN) remove, O(1) min/max
   2. Trie

Problems:

1. Min-stack
2. Implement a queue by two stacks O(1)
3. Largest rectangle in histogram (very good analysis) （code 好的一点是在stack里事先加个-1，可以避开最左边的特殊情况）（pop时处理可以不用左右各走一遍）
4. Max tree (same with largest rectangle): 找每个点的父亲，找左右两边第一个比它大的，两者相比小的那个是父亲
5. LRU Cache (LFU Cache)
6. Longest consecutive sequence
7. Subarry sum
8. Anagrams
9. Find Median from data stream (heap)
10. Word search II (trie)