Art of Codeartofcode
Lesson 11 of 15

20. Probabilistic Data Structures

1
The picture to keep in your head
2
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 breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
20. Probabilistic Data Structures

Practice: five levels

3 min read+10 XP

Assignments

Five levels. Do them in order. Answers are in "Solutions" at the end, so try first.

Level 1: Think (no code)

A. True or false? Explain in one line.

  1. A Bloom filter can say an item is absent when it was actually added.
  2. You can remove an item from a plain Bloom filter by clearing its bits.
  3. HyperLogLog can tell you whether user 42 visited today.
  4. A count-min sketch can report a count lower than the true count.
  5. Two days' HyperLogLogs can be combined to count unique visitors across both days.

B. Which structure, or none? One line each.

  1. Count distinct IP addresses hitting the site each day.
  2. Track each customer's wallet balance.
  3. Skip a disk read when a key isn't in a storage file.
  4. Show the 10 most-searched terms in the last hour.
  5. A set of blocked coupon codes that are added and later removed.

Level 2: Calculate

  1. Size a Bloom filter for 10 million usernames at 1% false positives: bits per item, total MB and number of hashes. How does that compare with storing the names (about 20 bytes each)?
  2. That filter ends up holding 30 million names. Roughly what's the false-positive rate now?
  3. You keep a HyperLogLog of 12 KB per day for 30 days. How much memory is that? Compare with storing 2 million visitor IDs of 16 bytes per day, exactly.
  4. A count-min sketch with ε = 0.1% and δ = 1% counts 100,000 searches. What are its width and depth, and the largest overcount you'd expect (with 99% confidence)?

Level 3: Build

In Python, using hashlib for hashing:

  1. bloom_size(n, p) returning bits and hash count, and a BloomFilter with add and might_contain. Measure the real false-positive rate on 20,000 new items.
  2. A CountingBloomFilter with remove.
  3. A HyperLogLog with 16,384 registers, add, count and merge. Check it's within 2% on 100,000+ distinct items.
  4. A CountMinSketch(eps, delta); check it never undercounts.
  5. A TopK using the sketch and a small heap; check it matches the true top 5.

Level 4: Debug

New customers complain: "Every username I try is taken", and support finds that some genuinely unused names are rejected. The signup check:

python
  1. Find the bug. About what fraction of free names get rejected, if the filter was sized for 1%? Why might customers see it far more often than that?
  2. Fix it.

Level 5: Design

The bookstore wants a real-time analytics panel: unique visitors today and this month, the top 20 searches in the last hour, and a fast "is this book already in this user's wish list?" check used on every product page. Traffic: 2 million visitors a day, 100,000 searches an hour.

Deliver:

  1. The structure for each feature, with sizes and error rates.
  2. How "this month" is computed from daily data.
  3. How "last hour" top searches are kept fresh as time moves.
  4. Where each structure lives (which service, which store) and what happens if it's lost.
  5. Which numbers on the panel must be exact, if any, and how you'd get those.