In this module — 11 sections
Reference card
Everything worth having in a table, in one place. This is not study material — it is what you scan for ten minutes the night before, and what you glance at while estimating.
The modules are prose on purpose: prose carries the causal link that becomes memory, and a table only lists facts. But some things genuinely are lookups, and those live here.
Complexity, and what fits
| Complexity | n=10 | n=1,000 | n=10⁶ | Where |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | hash lookup, array index |
| O(log n) | 3 | 10 | 20 | binary search, balanced tree height |
| O(n) | 10 | 10³ | 10⁶ | linear scan |
| O(n log n) | 33 | 10⁴ | 2×10⁷ | sorting, heapify n elements |
| O(n²) | 100 | 10⁶ | 10¹² ❌ | two nested loops |
| O(2ⁿ) | 1,024 | ❌ | ❌ | subsets, unmemoised recursion |
| O(n!) | 3×10⁶ | ❌ | ❌ | permutations |
Roughly 10⁸ operations per second. So: n ≤ 20 exponential is fine · n ≤ 5,000 quadratic passes · n ≤ 10⁶ needs n log n · n ≥ 10⁸ needs linear or better.
Sorting
| Algorithm | Average | Worst | Space | Stable | In place |
|---|---|---|---|---|---|
| Merge sort | n log n | n log n | O(n) | ✅ | ❌ |
| Quicksort | n log n | n² | O(log n) | ❌ | ✅ |
| Heapsort | n log n | n log n | O(1) | ❌ | ✅ |
| Insertion | n² | n² | O(1) | ✅ | ✅ |
| Counting | n + k | n + k | O(k) | ✅ | ❌ |
Python operation costs
| Operation | Cost | |
|---|---|---|
lst[i], lst.append,
lst.pop() |
O(1) | append is amortised |
lst.pop(0), lst.insert(0, x) |
O(n) | use deque |
x in lst |
O(n) | use a set |
x in set / in dict |
O(1) | average |
lst[a:b] |
O(b−a) | a slice copies |
s += c in a loop |
O(n²) | use "".join() |
sorted() / .sort() |
O(n log n) | Timsort, stable |
heapq.heapify |
O(n) | not n log n |
Graph representations
| Memory | has_edge(u,v) |
neighbours(u) |
|
|---|---|---|---|
| Objects and pointers | O(V+E) | O(degree) | O(degree) |
| Adjacency matrix | O(V²) | O(1) | O(V) |
| Adjacency list | O(V+E) | O(degree) | O(degree) |
Shortest paths
| Situation | Algorithm | Cost |
|---|---|---|
| Unweighted | BFS | O(V+E) |
| Non-negative weights | Dijkstra | O(E log V) |
| Negative weights | Bellman-Ford | O(V·E) |
| All pairs | Floyd-Warshall | O(V³) |
| Known destination + heuristic | A* | ≤ Dijkstra |
| Weights of 0 or 1 | 0-1 BFS (deque) | O(V+E) |
Grid heuristics: Manhattan for 4 directions, Chebyshev for 8, Euclidean always admissible but weaker. Manhattan on an 8-direction grid overestimates and loses optimality.
Latency, orders of magnitude
| Operation | Time |
|---|---|
| L1 cache | 1 ns |
| Main memory | 100 ns |
| Mutex lock/unlock | 25 ns |
| SSD random 4 KB | 15–150 µs |
| Round trip, same datacenter | 0.5 ms |
| Disk seek | 10 ms |
| LLM token | ~20 ms |
| Round trip across continents | 150 ms |
Availability
| SLO | Per year | Per month |
|---|---|---|
| 99% | 3.65 days | 7.3 h |
| 99.9% | 8.77 h | 43.8 min |
| 99.99% | 52.6 min | 4.4 min |
In series it multiplies: three components at 99.9% give 99.7%. Queueing: at 80% utilisation the wait is 4×; at 90% it is 9×; at 95% it is 19×.
Estimation
1 day = 86,400 s ≈ 10⁵ s
1M DAU × 10 actions → 10⁷ req/day → ~120 QPS average, ~350 peak
peak = 2–3× average
cores = QPS × CPU-seconds/request, ÷ 0.6 target utilisation
concurrency = arrival rate × response time (Little's law)Concurrency
Coffman's four conditions (all must hold simultaneously): mutual exclusion · hold and wait · no preemption · circular wait. Break circular wait with a global lock ordering.
| Policy | Idea | Problem |
|---|---|---|
| FCFS | order of arrival | convoy effect |
| SJF | shortest first | starvation, needs prediction |
| Round-robin | fixed quantum | small quantum = more switches |
| Priority | highest first | starvation, fix with aging |
| CFS (Linux) | least virtual runtime | today's default |
Criticality classes (Google, propagated down the RPC
chain, shed from the bottom up): CRITICAL_PLUS ·
CRITICAL · SHEDDABLE_PLUS ·
SHEDDABLE.
Retries: at most 3 per request, at most 10% of client traffic, exponential backoff with jitter, at exactly one layer of the stack.
Combinatorics
C(n,k) = n! / (k!(n−k)!) C(n,k) = C(n,n−k)
C(n,k) = C(n−1,k−1) + C(n−1,k) Σₖ C(n,k) = 2ⁿmath.comb(n, k) · math.perm(n, k) ·
E[trials until first success] = 1/p · coupon collector ≈ n·ln(n)
Recognition table — prompt to pattern
| The prompt says… | Think… |
|---|---|
| "pair that sums to X", "seen this before?" | hash map |
| "sorted array", "find the position" | binary search |
| "smallest k that works", "minimise the maximum" | binary search on the answer |
| "contiguous subarray/substring" | sliding window |
| "k largest", "median of a stream" | heap |
| "next greater element" | monotonic stack |
| "max in a sliding window" | monotonic deque |
| "all combinations/permutations" | backtracking |
| "how many ways", "minimum cost to" | DP |
| "prefix", "autocomplete" | trie |
| "groups", "connected components" | union-find |
| "fewest steps", unweighted | BFS |
| "valid order", "prerequisites" | topological sort |
| "cheapest with positive weights" | Dijkstra |
| "intervals", "meetings" | sort by start + heap |
| "appears once", "no extra space" | XOR |
| "cycle", "find the duplicate in place" | Floyd, fast and slow |