20. Probabilistic Data Structures
1
The picture to keep in your head2
20.1 Why is "approximately right, fast and tiny" a good trade?3
20.2 How does a Bloom filter work?4
20.3 What is a counting Bloom filter?5
20.4 How does HyperLogLog count unique visitors?6
20.5 What is a count-min sketch?7
20.6 How do you find the top K and heavy hitters?8
20.7 How do you choose size vs error rate?9
20.8 Where does each one show up in interviews?10
Memory card and where the analogy breaks11
Practice: five levels12
Interview questions13
Solutions14
Sources15
Code lab20. Probabilistic Data Structures
Memory card and where the analogy breaks
3 min read+10 XP
The memory card (tear this page out)
| # | Question | Memory code |
|---|---|---|
| 20.1 | Why approximate? | Small and nearly right beats huge and exact, when nearly is enough |
| 20.2 | Bloom filter? | No means no; yes means maybe |
| 20.3 | Counting Bloom filter? | Tallies, not ticks, so you can rub one out |
| 20.4 | HyperLogLog? | The longest lucky streak tells you how many tried |
| 20.5 | Count-min sketch? | Mark every board; trust the smallest tally |
| 20.6 | Top-K? | Count roughly, keep the leaders, and swap out the weakest |
| 20.7 | Size vs error? | Decide the error first; the size follows. And never overfill |
| 20.8 | In interviews? | In the set? Bloom. How many unique? HyperLogLog. How often? Count-min. Who's top? Top-K |
The whole chapter in one line: Pick the question (in the set, how many unique, how often, who's top), pick the error you can live with, and the answer fits in kilobytes.
Where the analogy breaks
- A bouncer can remember a face. These structures remember nothing about individuals: you can't ask a Bloom filter or HyperLogLog to list what's inside.
- A bouncer's guess can be off in any direction. These errors have a known shape: Bloom filters never say a false "no", count-min sketches never undercount.
- A bouncer can take a bigger card mid-evening. These structures are sized up front; outgrowing them means rebuilding.
Quick check
Five questions on this chapter. Pick an answer, then check it.
quiz