Coding Interview Cheat Sheets
Pattern recognition cards, complexity quick-reference, and study guides — all in one place.
206
Problems
21
Patterns
12
Cheat cards
Pattern Recognition Cards
Use these when you are unsure which pattern fits a problem.
Sliding Window
Practice →Maintain a contiguous sub-sequence and expand/shrink from one end.
- ✓ Longest/shortest subarray with a constraint
- ✓ Substring problems with a frequency limit
- ✓ Fixed-size window max/min/sum
O(n) time · O(1)–O(k) space
Two Pointers
Practice →Use two indices to reduce an O(n²) search to O(n) on sorted or structured data.
- ✓ Sorted array: pair sum, 3Sum, container
- ✓ In-place modification (remove dups, move zeros)
- ✓ Slow/fast for cycles or middle of list
O(n) time · O(1) space
Binary Search
Practice →Halve the search space each step — works on any monotonic condition, not just arrays.
- ✓ Sorted array or rotated sorted array
- ✓ "Minimum X such that condition holds"
- ✓ Search in 2D sorted matrix
O(log n) time · O(1) space
Prefix Sum
Practice →Precompute running sums to answer range sum queries in O(1).
- ✓ Range sum queries (immutable array)
- ✓ Subarray sum equals k
- ✓ Count of subarrays divisible by k
O(n) build · O(1) query
Hash Map
Practice →Trade space for O(1) average lookup to turn O(n²) problems into O(n).
- ✓ Two-sum variants
- ✓ Frequency counting / grouping
- ✓ First/last occurrence
O(n) time · O(n) space
Stack
Practice →LIFO structure for matching, undoing, or finding the next greater/smaller element.
- ✓ Matching brackets / nesting
- ✓ Next greater element (monotonic stack)
- ✓ Expression evaluation
O(n) amortized · O(n) space
BFS / Queue
Practice →Level-order traversal; guarantees shortest path in unweighted graphs.
- ✓ Shortest path (unweighted)
- ✓ Level-by-level tree traversal
- ✓ Multi-source spread (rotting oranges)
O(V + E) time · O(V) space
Heap / Priority Queue
Practice →Always access the min or max in O(log n); ideal for k-th element and scheduling.
- ✓ Kth largest/smallest element
- ✓ Merge k sorted lists/streams
- ✓ Task scheduling / rearrangement
O(n log k) time · O(k) space
Dynamic Programming
Practice →Break into overlapping sub-problems. Define state → recurrence → base case → optimise.
- ✓ Optimal value (min cost, max profit)
- ✓ Count of ways
- ✓ "Can we achieve X?" yes/no
O(n²) typical · O(n)–O(n²) space
DFS / Backtracking
Practice →Explore all paths; prune branches that can never lead to a valid solution.
- ✓ All subsets / permutations / combinations
- ✓ Word search in a grid
- ✓ N-queens, Sudoku
O(2ⁿ) or O(n!) · O(n) recursion stack
Union-Find
Practice →Near-O(1) union and find for dynamic connectivity problems.
- ✓ Connected components (dynamic)
- ✓ Cycle detection (undirected)
- ✓ Merging groups (accounts merge)
O(α(n)) per op · O(n) space
Topological Sort
Practice →Linear ordering of vertices in a DAG — detect cycles and find dependency order.
- ✓ Course scheduling / prerequisites
- ✓ Build order / dependency resolution
- ✓ Detect cycles in directed graph
O(V + E) time · O(V) space
Time Complexity Quick Reference
Interview target for n = 10⁶: aim for O(n log n) or better.
| Complexity | Type |
|---|---|
| O(1) | Constant |
| O(log n) | Logarithmic |
| O(n) | Linear |
| O(n log n) | Log-linear |
| O(n²) | Quadratic |
| O(2ⁿ) | Exponential |
| O(n!) | Factorial |
Pattern Decision Tree
When you see these keywords in a problem, reach for the corresponding pattern.
| Keyword / constraint | Pattern to try first |
|---|---|
| Longest / smallest subarray with constraint | Sliding Window |
| Sorted array, pair sum, in-place removal | Two Pointers |
| "Minimum X satisfying condition" with large range | Binary Search on Answer |
| Range sum query, subarray sum = k | Prefix Sum + Hash Map |
| Shortest path, minimum steps, level-by-level | BFS |
| All paths, all subsets/permutations, Sudoku | DFS / Backtracking |
| Kth largest, merge k sorted, task schedule | Heap |
| Max/min value with sub-problems, count of ways | Dynamic Programming |
| Prerequisites, dependency order, build system | Topological Sort |
| Brackets matching, next greater element | Monotonic Stack |
| Connected groups, dynamic connectivity | Union-Find |
| Prefix matching, autocomplete, word dictionary | Trie |
Ready to practice?
Apply these patterns to real problems with difficulty filters and progress tracking.