A lot of problems involve advanced algorithms and require extensive reading/training. This is beyond the scope of this notes. Instead, I will only deal with regular coding work that you have to do everyday. It doesnt have to be super optimized, but runs reasonably fast, uses memory wisely, and is certainly towards bug-free. A few topics that come off my mind: searching, sorting, dynamic programming, streaming alrogithms and some machine learning/data mining topics.
- variation: select top k
- dynamic programming
- 1. there are limited ways of from previous states to current state. figure out each possible previous state. 2. make progress toward goal every step.
- I suggest start with this excellent short tutorial: http://people.csail.mit.edu/bdean/6.046/dp/ with the knapsack problem to understand what does DP do, how do you approach a problem like that, how do you realize it in coding, how can you optimize on the space usage, etc.
- My notes on Ways of Coin Change
- My notes on Distinct Sequence
- Hash Table
- Binary Tree
- Binary Search Tree
- delete: no child. 1 child. two children: find successor with at most 1 child. replace.
- find successor. if right(x): return leftmost(right(x)). else if x = leftchild(parent(x)), return parent(x). else x = parent(x), recur.
- PathFinding: https://news.ycombinator.com/item?id=8349069