- Linked List
- Recursion vs. Iteration
- Dynamic Programming
- Bit Manipulation
- Combinations and Permutations
- Other problems that need us to find patterns
- Binary Search Tree: for all nodes, left children <= current node <= right children
- Balanced vs. Unbalanced: In a balanced tree, the depth of the left and right subtrees of every node differ by 1 or less.
- Full Binary Tree: every node other than the leaves has two children.
- Perfect Binary Tree: a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.
- Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
|Algorithm||Average Time||Worst Time||Space|
|Quick sort||n log(n)||n^2|
|Merge sort||n log(n)||n log(n)||depends|
f(1) = 1;
- An instance is solved using the solutions for smaller instances.
- The solution for a smaller instance might be needed multiple times.
- The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
- Additional space is used to save time.
The problem of climbing steps perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.
|OR (|)||AND (&)||XOR (^)||Left Shift (<<)||Right Shift (>>)||Not (~)|
There are 50 people in a room, what’s the probability that two people have the same birthday? (Ignoring the fact of leap year, i.e., 365 day every year)
12/06/2013 – Add “Add Two Numbers”, “Binary Tree Traversal(pre/in/post-order)”, “Find Single Number”.
12/07/2013 – Add “Word Break”
12/08/2013 – Add “Reorder List”
12/10/2013 – Add “Edit Distance”, ” Reverse Integer”
12/14/2013 – Add “Copy List with Random Pointer”, “Evaluate Reverse Polish Notation”, “Word Ladder”.