Interview prep implementations with tests and complexity analysis.
| Category | Algorithm | Complexity | File |
|---|---|---|---|
| 📦 Arrays | Two Sum (hash map + two-pointer) | O(n) | arrays/two_sum.py |
| 📦 Arrays | Sliding Window (max sum, unique substr) | O(n) | arrays/sliding_window.py |
| 📦 Arrays | Kadane's Algorithm (max subarray) | O(n) | arrays/kadane.py |
| 📦 Arrays | Two Pointers (sorted sum, dedup, palindrome) | O(n) | arrays/two_pointers.py |
| 🔤 Strings | Anagram, Reverse Words, First Unique, LCP | O(n) | strings/manipulation.py |
| 🔗 Linked Lists | Singly (push, pop, find, reverse) | O(1)/O(n) | linked_lists/singly.py |
| 📚 Stacks | Stack + Valid Parentheses | O(1) | stacks/stack.py |
| 📬 Queues | Queue (deque-based) | O(1) | queues/queue.py |
| #️⃣ Hash Maps | Custom HashMap (open addressing) | O(1) avg | hashmaps/hashmap.py |
| 🌳 Trees | BST (insert, search, in-order) | O(log n) | trees/bst.py |
| ⛰️ Heaps | Kth Largest, Top K Frequent, Merge K Sorted | O(n log k) | heaps/priority_queue.py |
| 🌐 Graphs | BFS, DFS iterative + recursive | O(V+E) | graphs/traversals.py |
| 📊 Sorting | Quick Sort (in-place + functional) | O(n log n) | sorting/quick_sort.py |
| 📊 Sorting | Merge Sort (divide & conquer) | O(n log n) | sorting/merge_sort.py |
| 📊 Sorting | Heap Sort (in-place) | O(n log n) | sorting/heap_sort.py |
| 🔍 Searching | Binary Search (iterative + recursive) | O(log n) | searching/binary_search.py |
| 🧮 Matrix | Rotate 90°, Spiral Order | O(n²) | matrix/operations.py |
| 🔄 Dynamic Programming | Fibonacci (memo + bottom-up), Climbing Stairs | O(n) | dynamic_programming/fibonacci.py |
| 🔙 Backtracking | Permutations, Subsets (power set) | O(n!/2^n) | backtracking/permutations.py |
python -m pytest tests/ -v- Two pointers eliminates O(n²) brute force on sorted arrays — always ask "is it sorted?"
- Sliding window replaces nested loops for subarray/substring problems
- Kadane's is just a clever rolling max — once you see it, you can't unsee it
- BFS = shortest path in unweighted graphs, DFS = explore everything
- Dynamic programming = recursion + memoization — start top-down, optimize bottom-up
- Backtracking = DFS on a decision tree — add, recurse, undo
- Heaps solve any "top K" problem efficiently —
heapqin Python is a min-heap - Valid parentheses is the canonical stack problem — learn the pattern, solve 10 variants
MIT