Top-10,000 Selection From a 17 GB Single-Pass Log
The ranking team must emit the 10,000 highest-scoring records from a 180-million-row nightly log. Records are fixed 96 bytes, stored in one file of about 17 GB; the machine that processes it has 4 GB of RAM and a single 200 MB/s SSD, and the file can be read only once because three downstream jobs consume the output at 05:00. The score is a 32-bit integer, and ties at the cut-off must be broken by ascending record id. Two designs are on the table: (A) one sequential pass that maintains a min-heap of 10,000 entries keyed by score, evicting the root whenever a larger score arrives, then sorting the surviving 10,000; (B) a full external merge sort of the 17 GB file followed by truncation to 10,000 rows. A third engineer suggests sampling 1% of the file and extrapolating the cut-off score. The compliance owner wants a deterministic, exactly correct answer.
1. Quantify both designs - comparisons and I/O - and decide which one to build.
Read the worked answer
Design A (bounded heap). Every record costs one comparison against the root: 1.8e8 comparisons. The expensive sift-down is not paid per record: after warm-up a record must beat the current 10,000th best, and the expected number of replacements is k·ln(n/k) ≈ 1e4 × ln(1.8e4) ≈ 9.8e4, each costing log2(1e4) ≈ 13.3 comparisons ≈ 1.3e6. Final sort of 10^4 entries is negligible. Memory is 10^4 × ~128 B ≈ 1.3 MB. I/O is one sequential read: 17 GB / 200 MB/s ≈ 87 s.
Design B (external sort). Comparisons ≈ n log2 n = 1.8e8 × 27.4 ≈ 4.9e9 - about 20× more. With 4 GB RAM the runs are ~3 GB, so ~6 runs and roughly two merge passes, i.e. ~85 GB of read+write traffic ≈ 425 s, five times the I/O.
Verdict: build A. Its advantage is not a better asymptotic class - both are O(n log n)-ish in the worst case - but that it avoids re-reading and re-writing 17 GB, and its inner loop is one cache-resident comparison per record. The instinct 'sorting is the general answer' is exactly what the I/O budget punishes here.
2. The product owner now asks for the top 90 million rows instead of 10,000. Does design A still win? Derive the crossover point.
Read the worked answer
Heap memory is k × (96 B payload + ~32 B of pointers/keys) ≈ 128k bytes. With ~3 GB usable after OS and read buffers, k_max ≈ 3e9 / 128 ≈ 23 million. At k = 90e6 the structure needs ~11.5 GB - it does not fit, so it either swaps (destroying the single-pass property) or spills to disk, at which point it has become a badly organised external sort.
The asymptotics also collapse. log2(9e7) = 26.4 against log2(1.8e8) = 27.4: the heap no longer saves comparisons per element. Worse, k/n = 0.5, so replacements are no longer rare - k·ln(n/k) ≈ 9e7 × 0.69 ≈ 6.2e7 sift-downs × 26 comparisons ≈ 1.6e9, which is the same order as one external sort pass.
Rule to state explicitly: the bounded-heap trick pays while (a) k fits comfortably in RAM and (b) k·ln(n/k)·log k << n·log n, i.e. k << n. At k = 90e6 neither holds; design B, or a disk-based partition/quickselect where each partition is small enough to buffer, is the right answer.
3. Evaluate the 1% sampling proposal against the determinism requirement, and say what one pass must additionally maintain if the team also wants the 99th-percentile score.
Read the worked answer
A 1% sample is 1.8e6 rows. The cut-off is the p = 1e4/1.8e8 = 5.6e-5 quantile; the number of sampled rows above it is ~1e4 with standard deviation ~100, so the estimated cut-off moves by roughly one part in a hundred in rank terms. That is harmless for a dashboard and fatal for a compliance report, because (i) the boundary is dense - thousands of records can share the 10,000th score - so a small shift in the cut-off changes which ids are emitted, and (ii) the required tie-break by ascending id cannot be reproduced from a sample at all. Sampling answers 'about how high is the 10,000th score', not 'which 10,000 rows'.
For the percentile, the same single pass should maintain a fixed-width histogram over the score range - e.g. 2^16 buckets with 4-byte counters, 256 KB - updated alongside the heap. That yields the 99th percentile to within one bucket width with no second pass. Label it as bounded-error: exact percentile and exact top-k are different guarantees, and only the heap gives the second.