Topic 1.4
Interview Math Without a Calculator
In one line
Memorise a few anchors: ln 2 ≈ 0.693, (ln 2)² ≈ 0.48, 1% needs ~10 bits and 7 hashes per item, 0.1% ~14.4 bits, each 10× costs ~4.8 bits, and 10 bits/item gives just under 1%. With those you can size any filter in your head.
Think of it like this
A cook who knows "a cup of rice feeds two" doesn't weigh every grain. A few anchors turn Bloom filter sizing into quick mental arithmetic.
Key ideas
- 01
Anchors: ln 2 ≈ 0.69; (ln 2)² ≈ 0.48; e^(−0.7) ≈ 0.5; bits/item ≈ 1.44 × log2(1/p); log2(100) ≈ 6.64, log2(1000) ≈ 10.
- 02
Quick table: 1% → ~10 bits, 7 hashes; 0.1% → ~14–15 bits, 10 hashes; 0.01% → ~19 bits, 13 hashes; 10% → ~5 bits, 3 hashes.
- 03
From bits/item to p: with b bits per item and optimal k ≈ 0.69 b, p ≈ 0.6185^b. So 8 bits → ~2%, 10 bits → ~0.8%, 16 bits → ~0.05%.
- 04
Memory: n × bits ÷ 8. 100M × 10 bits = 1 Gbit = 125 MB. 1B × 10 bits = 1.25 GB.
- 05
Say your rounding out loud ("about 10 bits per item, so roughly 125 MB"); interviewers care about the method and orders of magnitude.
Code & diagrams
Given: 100M items, 10 bits/item
memory = 100M x 10 bits = 1e9 bits = 125 MB
k_opt = 10 x 0.69 = 6.9 -> 7
kn/m = 7 / 10 = 0.7 ; e^-0.7 ~ 0.5 ; fill ~ 0.5
p ~ 0.5^7 = 1/128 ~ 0.8% (exact: 0.82%)
Check k too low / too high at 10 bits/item:
k = 3 -> 1.7% k = 7 -> 0.82% k = 14 -> 1.9%Interview problem
The problem
100M items, 10 bits per item
An interviewer gives you 100 million items and 10 bits per item. Estimate the memory, the optimal number of hashes and the false-positive rate, reasoning aloud without a calculator.
Explain it without notes
Why does each 10× reduction in p cost about 4.8 bits per item?
Practice
Estimate in your head: 2 billion items at 1%; 50 million items at 0.1%.
Trade-offs
- ↔
Quick estimates are for design discussions; implement with exact formulas and measure.
Done when you can
I can estimate memory, k and p for any Bloom filter mentally using a few anchors.