1Show the Level 1 solution
2**A.**
31. **False.** No false negatives: an added item always finds its bits set.
42. **False.** Those bits may belong to other items too; clearing them creates false negatives.
53. **False.** HLL only estimates how many; it keeps nothing about who.
64. **False.** Collisions only add, and the minimum is still at least the true count.
75. **True.** Take the maximum of each register to get the union's HLL.
8
9**B.**
101. **HyperLogLog.**
112. **None**: balances must be exact, in a database.
123. **Bloom filter.**
134. **Top-K** (count-min sketch + heap) per window.
145. **Counting Bloom filter** (or cuckoo filter), confirmed against the real list if a "maybe" matters.
Show the Level 2 solution
1. Bits per item = −ln(0.01) ÷ (ln 2)² ≈ **9.6**. Total ≈ 95.9 million bits ≈ **12 MB**. Hashes ≈ 9.6 × 0.693 ≈ **7**. Storing the names: 10 million × 20 bytes = **200 MB** before any overhead, so the filter is about **17× smaller**.
2. With 3× the planned items, the rate is (1 − e^(−7 × 30/95.9))^7 ≈ **44%**. The filter now sends almost half of all free names to the database.
3. 30 × 12 KB = **360 KB**. Exact: 2 million × 16 bytes = 32 MB a day, about **960 MB** for 30 days, and it can't give you monthly uniques without merging all the sets.
4. Width = e ÷ 0.001 ≈ **2,719**; depth = ln(100) ≈ 4.6, rounded up to **5**. Largest overcount ≈ ε × N = 0.001 × 100,000 = **100**, with 99% confidence.
1Show the Level 3 solution
2Tested solution (Python 3), the key parts:
3
4```python
5def hashes(item, k, m):
6 d = hashlib.sha256(str(item).encode()).digest()
7 h1 = int.from_bytes(d[:8], "big")
8 h2 = int.from_bytes(d[8:16], "big") | 1
9 return [(h1 + i * h2) % m for i in range(k)] # k positions from one hash
10
11
12def bloom_size(n, p):
13 m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
14 k = max(1, round(m / n * math.log(2)))
15 return m, k
16
17
18class BloomFilter:
19 def __init__(self, n, p):
20 self.m, self.k = bloom_size(n, p)
21 self.bits = bytearray((self.m + 7) // 8)
22
23 def add(self, item):
24 for h in hashes(item, self.k, self.m):
25 self.bits[h // 8] |= 1 << (h % 8)
26
27 def might_contain(self, item):
28 return all(self.bits[h // 8] >> (h % 8) & 1 for h in hashes(item, self.k, self.m))
29
30
31class HyperLogLog:
32 def __init__(self, p=14):
33 self.p, self.m = p, 1 << p # 16,384 registers
34 self.reg = bytearray(self.m)
35
36 def add(self, item):
37 x = int.from_bytes(hashlib.sha256(str(item).encode()).digest()[:8], "big")
38 idx = x >> (64 - self.p) # first bits pick a register
39 rest = x & ((1 << (64 - self.p)) - 1)
40 rank = (64 - self.p) - rest.bit_length() + 1 # leading zeros + 1
41 self.reg[idx] = max(self.reg[idx], rank)
42
43 def merge(self, other):
44 out = HyperLogLog(self.p)
45 out.reg = bytearray(max(a, b) for a, b in zip(self.reg, other.reg))
46 return out
47
48
49class CountMinSketch:
50 def __init__(self, eps, delta):
51 self.w = math.ceil(math.e / eps)
52 self.d = math.ceil(math.log(1 / delta))
53 self.table = [[0] * self.w for _ in range(self.d)]
54
55 def add(self, item, n=1):
56 for row, col in enumerate(hashes(item, self.d, self.w)):
57 self.table[row][col] += n
58
59 def estimate(self, item):
60 return min(self.table[row][col] for row, col in enumerate(hashes(item, self.d, self.w)))
61```
62
63All checks pass: the 10-million-name filter is 11.98 MB with 7 hashes; the measured false-positive rate is 0.97%; overfilling 3× pushes it to 44%; counting-filter removal works; HyperLogLog is within 0.1% on one day and 0.7% on the merged two days; the count-min sketch never undercounts; and top-K matches the true top 5. The full file, including `count()` and `TopK`, is in `code/ch20_probabilistic.py`.
1Show the Level 4 solution
2**The bug:** it treats the Bloom filter's "**maybe**" as "**definitely taken**". The filter has false positives by design, so some free names are rejected without the database ever being asked. In the tested demo, **194 of 20,000** free names (about **1%**) are wrongly rejected.
3
4Customers may see it **far more often** than 1% because:
5- The filter may be **overfilled** (20.7): sized for 10 million, now holding many more, so the rate climbs toward 40%.
6- People try **similar** names, and a rejected favourite is memorable.
7
8**The fix:** use the filter only to skip the database on a **"no"**; confirm every **"maybe"** with the real data:
9
10```python
11def is_taken(bloom, name, db):
12 if not bloom.might_contain(name):
13 return False # definitely free: no database call
14 return name in db # maybe: the database decides
15```
16
17Also: add new usernames to the filter as accounts are created, monitor its fill, and rebuild it larger before it overfills. And keep a **unique constraint** on usernames in the database (Chapter 17) as the final word.
1Show the Level 5 (sketch) solution
21. **Structures:** unique visitors: one **HyperLogLog** per day (12 KB, ~0.81%). Top searches: a **count-min sketch** (ε = 0.1%, δ = 1%, about 2,719 × 5 counters) plus a **top-20 heap**, per minute. Wish list check: a **Bloom filter per user** for large lists, or simply the exact wish-list IDs cached per user, since wish lists are small. A Bloom filter only pays off when the set is big.
32. **This month:** `PFMERGE` the daily HLLs for the month on demand, or keep a running monthly HLL updated alongside the daily one.
43. **Last hour:** keep **60 per-minute** sketches and top lists in a ring; the hour's top 20 is a merge of the last 60 (sketches merge by adding cells). Drop the oldest minute every minute.
54. **Where:** HLLs in Redis (`PFADD` on each visit, from the web tier or an event consumer). Sketches and top lists in a stream processor fed by search events from a queue (Chapter 22), writing the current top 20 to a cache for the panel. Loss: HLLs and sketches can be rebuilt from event logs; the panel shows "temporarily unavailable" meanwhile. Nothing customer-facing depends on them.
65. **Exact numbers:** anything used for **billing, payouts or official reports** (for example, author royalties per sale) comes from the orders database, not these structures. Label the panel's numbers "approximate".