For each of the following structures, you should understand how to implement and use them. You should also know their time complexity for common operations (add, remove, access).
- Dynamic array (aka Vector, Array List)
- Linked list
- Hash table
- Heap (just know about min- and max-heap)
- Binary tree
- Trie (aka Prefix tree). A common application is for autocomplete or predictive text dictionary (think T9).
- Binary search tree
- Self-balancing binary search trees: AVL tree / Red-black tree. You typically just need to know about them and their usage rather than know how to implement them.
NOTE: Balanced Binary Search Trees are even better than heaps because in addition to
insert,delete, andmin|max—which is the contract of the Priority Queue absract data type—, they providefindSuccessorandfindPredecessorin O (log n) time. The main reason you'd prefer heaps is because the latter are in place: they don't use any extra space.
- Binary search — find the position of an input element within a sorted array.
- Graph/tree Traversal: Depth First Search (DFS)
- Graph/tree Traversal: Breadth First Search (BFS) — guarantees shortest path.
- Quicksort vs. Merge sort
- Random permutation
The three pillars of object-oriented programming are: encapsulation, inheritance, and polymorphism. You should understand, be able to talk about, and apply the following object-oriented principles.
- Encapsulation
- Inheritance
- Polymorphism (since we're talking about OOP, I’m referring to inclusion polymorphism)
- Composition (and why one might prefer composition over inheritance)
These are not sorted in any particular order other than alphabetical.
TBD: currying, memoization