Cheat Sheet
The one-page reference. Skim it the morning of an interview to reload the numbers and the templates into working memory. For the “which technique?” decision guide, see the Pattern Map.
The complexity ladder
For most interview inputs (n up to ~10⁵–10⁶), here’s what each complexity buys you:
| Complexity | Name | Feels like | OK up to (~1s) |
|---|---|---|---|
O(1) | constant | instant | any n |
O(log n) | logarithmic | binary search | effectively unlimited |
O(n) | linear | one pass | ~10⁸ |
O(n log n) | linearithmic | sorting | ~10⁶–10⁷ |
O(n²) | quadratic | nested loops | ~10⁴ |
O(2ⁿ) | exponential | all subsets | ~20–25 |
O(n!) | factorial | all permutations | ~10–12 |
Read the constraint backward into a target Big-O. n ≤ 20 → an exponential bitmask/backtracking solution is fine. n ≤ 10⁵ → you need O(n log n) or better (sorting or hashing). n ≤ 10⁹ → you can’t even read all the input; it’s O(log n) (binary search) or math. The constraint is a hint about the intended approach.
Data-structure operations
| Structure | Access | Search | Insert | Delete | Note |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | contiguous, cache-friendly |
| Hash map / set | — | O(1)* | O(1)* | O(1)* | *amortized; the universal speedup |
| Balanced BST / TreeMap | O(log n) | O(log n) | O(log n) | O(log n) | keeps keys sorted |
| Heap (binary) | O(1) peek | O(n) | O(log n) | O(log n) pop | top-k, priority |
| Stack / Queue | — | — | O(1) | O(1) | LIFO / FIFO |
| Trie | — | O(L) | O(L) | O(L) | L = key length; prefix queries |
| Union-Find | — | O(α(n)) | O(α(n)) | — | near-constant connectivity |
| Segment tree / BIT | — | O(log n) | O(log n) | O(log n) | range query on mutable data |
Algorithm complexities
| Algorithm | Time | Space | Chapter |
|---|---|---|---|
| Binary search | O(log n) | O(1) | Day 13 |
| Merge / Quick / Heap sort | O(n log n) | O(n) / O(log n) / O(1) | Day 11–12 |
| BFS / DFS | O(V + E) | O(V) | Day 10 |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | Day 21 |
| Topological sort | O(V + E) | O(V) | Day 23 |
| 1-D / 2-D DP | O(n) / O(n·m) | same or reduced | Day 14 |
| Sliding window | O(n) | O(k) | Day 24 |
| KMP / Z-algorithm | O(n + m) | O(m) | Day 27 |
Templates worth memorizing
# Binary search (lower bound) — Day 13
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target: lo = mid + 1
else: hi = mid
# lo is the first index >= target
# Sliding window (variable) — Day 24
left = 0
for right in range(len(a)):
add(a[right])
while window_invalid():
remove(a[left]); left += 1
best = max(best, right - left + 1)
# BFS — Day 10
from collections import deque
q = deque([start]); seen = {start}
while q:
node = q.popleft()
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt); q.append(nxt)The universal solve loop
When you’re stuck, run this out loud, every time:
- Restate the problem; clarify constraints (n? edges? empty input? what to return when there’s no answer?).
- Read the constraints into a target Big-O.
- Brute force first — get something correct, state its complexity.
- Find the repeated work — that’s where the optimization lives.
- Match it to a pattern (Pattern Map).
- Code, test (incl. edges), state final complexity.
Treat the pattern map as strong priors, not a lookup table. Some problems are novel, and some combine two patterns (e.g. binary search on the answer with a greedy feasibility check). If the clue points one way but the details don’t fit — trust the details.