What it is
Probabilistic structures trade exactness for absurd space efficiency. A Bloom filter answers "is X possibly in the set?" — false positives happen at a rate you choose, false negatives never do. It's an m-bit array with k hash functions: insert sets k bits, query checks whether all k are set. HyperLogLog estimates the number of distinct items in a stream within about 1% using a fixed 12 KB, by tracking maximum runs of leading zeros in hashed values. A count-min sketch approximates per-item frequencies in a stream with a small 2-D counter grid, only ever overestimating.
In interviews these are the 'smart trick' layer: URL dedup in a web crawler, cache-penetration defence (don't hit the database for keys that can't exist), not re-recommending videos a user has seen, daily-active-user counts, and trending topics. The scoring is on knowing the error direction — which way each structure can be wrong — and whether that error is acceptable in your specific design.
A Bloom filter in front of the store answers 'definitely not seen' in memory — 1 GB covers a billion URLs at 1% false positives — and the only cost is that one crawl in a hundred gets wrongly skipped, which I can live with.
The picture
The variants and when to pick each
Bloom filter — the error is one-sided, and that's the whole design question
A 'no' from a Bloom filter is certain; a 'yes' is a maybe. So the design question is always: what happens on a false positive? In a crawler, a URL wrongly marked 'seen' is silently never crawled — a tiny, acceptable loss. In cache penetration defence, a false positive means one wasted database read — harmless. In spam filtering, a false 'spam' verdict blocks legitimate mail — unacceptable without pairing the positive path with an exact check.
Sizing is quotable: about 10 bits per element for 1% false positives (9.6 to be exact), with k ≈ 7 hash functions; every halving of the error rate costs about 5 more bits per element. A billion URLs at 1% is roughly 1.2 GB — versus hundreds of GB to store them exactly.
The two limits: fixed capacity and no deletes
A Bloom filter's size is fixed at creation for a target element count — overfill it and the false-positive rate climbs without warning. If the set grows unpredictably, use scalable Bloom filters (a chain of progressively larger filters) or size for the multi-year estimate upfront.
You also can't delete: clearing one item's bits would clear other items sharing them, creating false negatives — the one guarantee you sold. The counting Bloom filter variant swaps bits for small counters at about 4× the space, or you rebuild the filter periodically from the source of truth, which doubles as a defence against drift.
They're already in your design — say where
Every LSM-tree engine — RocksDB, Cassandra, HBase — keeps a Bloom filter per SSTable so a point read can skip files that definitely lack the key, turning a multi-file disk search into memory checks. CDNs use them to cache objects only on the second request, keeping one-hit wonders out of the cache. Mentioning that your 'NoSQL read path is fast partly because of per-SSTable Bloom filters' connects two concepts and reads as depth, not trivia.
HyperLogLog and count-min sketch — counting at stream scale
HLL answers 'how many distinct?' in a fixed 12 KB per counter with ~0.8% standard error — Redis ships it as PFADD/PFCOUNT. The killer feature is mergeability: the union of two HLLs is the register-wise max, so per-shard or per-day counters combine into global or monthly ones with no rescan. Exact distinct-counting 10B daily events would need a set of every ID; HLL does it in the space of one thumbnail.
Count-min sketch answers 'how often did X appear?' with a small grid of counters (a few hundred KB), only ever overestimating. Pair it with a min-heap and you get top-K heavy hitters — the standard skeleton for trending hashtags: sketch counts frequencies, heap keeps the current top 100.
Numbers worth memorising
| Bloom sizing rule | ~10 bits/element → 1% FPR, k ≈ 7 hashes |
| 1B items in a Bloom filter | ≈ 1.2 GB at 1% FPR |
| HyperLogLog | 12 KB fixed, ~0.81% error, counts billions |
| Count-min sketch | 2000 × 5 counters ≈ 40 KB for stream-scale accuracy |
| Halving the Bloom error rate | +~5 bits per element |
Where the interviewer pushes
The push is always the false positive: "your crawler's Bloom filter says 'seen' for a URL it never crawled — what happens, and is that OK?" The strong answer owns the consequence: that URL is silently never crawled, at 1% FPR that's one in a hundred candidate URLs lost, and for a crawler that's acceptable because coverage was never going to be 100% anyway — I'd tune the FPR down (more bits) if completeness mattered. The weak answer hand-waves that errors are 'rare'; the interviewer wants the error direction and its cost named.
Second push: "count exactly 10 billion unique events a day." The trap word is exactly — first establish whether 1% error is acceptable (for a dashboard, yes: HLL, 12 KB, merge per-shard counters by register-wise max). If it genuinely must be exact — billing, compliance — then no sketch qualifies and I'd say so: partition the ID space, count exact sets per partition in something like RocksDB, and pay the storage. Knowing when the probabilistic answer is wrong scores as high as knowing the structure.