Interview-day Cheat Sheet
One page, one click to anything you might need 30 minutes before the loop.
How to read this page
Skim top to bottom. Click into anything that feels foggy. If more than two
links feel foggy, you have your study list for the day. Do not try to read
every linked page — pick the ones you need to reinforce.
Backend
System Design
Pattern from signal — fast recall
Cover the right column. Test yourself.
| Signal | Try |
|---|---|
| Sorted array / asked to find a pair / asked to remove duplicates in-place | Two pointers (opposite ends, same direction) |
| Contiguous subarray / substring with a property / "longest ... with at most K" | Sliding window (fixed or variable) |
| Linked list cycle / find middle node / Nth from the end | Fast/slow pointers |
| "Find X in O(log n)" / sorted input / "smallest value such that predicate is true" | Binary search (classic, first-true, answer-space) |
| Unweighted graph shortest path / level-order traversal | BFS |
| Exhaustively explore / tree traversal / topological problems on DAGs | DFS |
| Generate all combinations / permutations / valid configurations | Backtracking |
| "Next greater / smaller element" / histogram rectangle / daily temperatures | Monotonic stack |
| Dynamic connectivity / merge groups / "are A and B in the same set?" | Union-Find |
| "Top K" / K most frequent / median from stream | Heap / Quickselect |
| Task ordering with dependencies / "is there a cycle in a DAG?" | Topological sort (Kahn / DFS) |
| Overlapping intervals / merge intervals / minimum rooms | Sort-by-start + sweep |
| "Count the number of ways" / optimal sub-structure / overlapping subproblems | Dynamic programming |
| "Minimum / maximum in a greedy local choice" | Greedy (prove exchange argument) |
| XOR to find unique / count set bits / subset enumeration via bitmask | Bit manipulation |
Edge-case checklist
- Empty input
- Single element
- All identical elements
- Already sorted / reverse sorted
- Duplicate values
- Negative values and zero
- Very large input (integer overflow risk in mid = (lo + hi) / 2 — use lo + (hi - lo) / 2)
- Cycles (in graphs and linked lists)
- Disconnected graph components
- Recursion depth on pathological inputs
Complexity at a glance
| Recurrence shape | Result | Canonical example |
|---|---|---|
| T(n) = T(n/2) + O(1) | O(log n) | Binary search |
| T(n) = 2·T(n/2) + O(n) | O(n log n) | Merge sort, quicksort (average) |
| T(n) = 2·T(n/2) + O(1) | O(n) | Tree traversal of balanced tree |
| T(n) = T(n - 1) + O(n) | O(n²) | Selection sort, naive insertion sort |
| T(n) = T(n - 1) + O(1) | O(n) | Linked list traversal |
| T(n) = 2·T(n - 1) + O(1) | O(2ⁿ) | Naive Fibonacci without memoization |
What to say when stuck
- "Let me re-read the problem and check my assumptions."
- "I want to try a smaller example to see the pattern."
- "What if I sort first — does that unlock a pattern?"
- "Can I trade space for time here?" (e.g., hash map for lookup)
- "Is there a way to precompute something so the inner loop is constant time?"
- "Let me state the invariant I want to maintain, then design toward it."