Interview questions

Interview questions (with the counter-questions you'll get)

Q1. What is a Bloom filter, and when would you use one?

They're testing: the most-asked probabilistic structure.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** A bit array with k hash functions. Adding sets k bits; checking tests them. Any 0 means definitely not present; all 1s means probably present. Use it to avoid expensive lookups for items that don't exist: LSM storage skipping files, crawlers skipping seen URLs, username checks before hitting the database.
3
4**Counter-questions:**
5- *"What's the false-positive rate and how do you control it?"* → It depends on bits per item and hash count; about 9.6 bits per item and 7 hashes give 1%.
6
7**Trap:** claiming it can have false negatives, or that it stores the items.

Q2. Can you delete from a Bloom filter?

They're testing: depth beyond the basics.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** Not from a plain one: clearing bits might clear bits shared with other items, creating false negatives. Use a counting Bloom filter (counters instead of bits, about 4× memory) or a cuckoo filter, or rebuild the filter periodically from the source of truth.
3
4**Counter-questions:**
5- *"Risks with counting filters?"* → Removing items never added, and counter overflow if undersized.
6
7**Trap:** "Just set the bits back to 0."

Q3. How would you count unique visitors per day for a site with millions of users?

They're testing: HyperLogLog and its trade-off.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** One HyperLogLog per day, for example Redis `PFADD` and `PFCOUNT`, about 12 KB each with about 0.81% standard error. Weekly or monthly uniques come from merging daily HLLs. If an exact count is needed for billing, compute it offline from logs.
3
4**Counter-questions:**
5- *"Why not a set per day?"* → Millions of IDs per day is tens of MB per day and grows; HLL stays fixed size and merges cheaply.
6
7**Trap:** summing daily unique counts to get monthly uniques, which double-counts repeat visitors.

Q4. Explain how HyperLogLog works.

They're testing: the intuition.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** Hash each item; the number of leading zeros in a random hash is like a coin-flip streak, and long streaks suggest many distinct items. To reduce noise, the first bits choose one of many registers, each keeping its maximum run; a harmonic mean with corrections gives the estimate. Duplicates hash identically, so they don't inflate it.
3
4**Counter-questions:**
5- *"How do you reduce the error?"* → More registers: error falls with the square root, so 4× registers halves it.
6
7**Trap:** saying it samples the data.

Q5. What is a count-min sketch?

They're testing: frequency estimation.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** A d × w grid of counters with one hash per row. Adding increments one cell per row; estimating takes the minimum across rows. It never undercounts, and overcounts by at most ε × N with probability 1 − δ, for w ≈ e/ε and d ≈ ln(1/δ). Fixed memory regardless of distinct items.
3
4**Counter-questions:**
5- *"Is it good for rare items?"* → Not really: the overcount can be larger than their true count. It shines for frequent items.
6
7**Trap:** confusing it with HyperLogLog (how often vs how many distinct).

Q6. Design trending hashtags or trending searches.

They're testing: applying top-K in a system.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** Stream events into a processor sharded by term; count per time window with exact counters per shard or a count-min sketch; keep a top-K heap per window; merge the shards' top lists. Define trending as unusually high compared with normal, not just frequent. Serve the result from a cache refreshed every minute or so.
3
4**Counter-questions:**
5- *"How do you stop one bot inflating a term?"* → Count unique users per term (HLL per term for big ones), rate-limit per user, and filter spam.
6
7**Trap:** sorting all terms by raw count every second.

Q7. How do LSM-tree databases use Bloom filters?

They're testing: linking to storage internals.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** Each on-disk file (SSTable) has a Bloom filter of its keys. A read checks filters first and only reads files that might contain the key, saving disk reads, especially for keys that don't exist. Cassandra and RocksDB both do this, with tunable false-positive rates.
3
4**Counter-questions:**
5- *"What does a false positive cost here?"* → One unnecessary file read, nothing worse.
6
7**Trap:** not knowing why reads in an LSM-tree need help.

Q8. Your Bloom filter's false-positive rate in production is 40%, not 1%. Why?

They're testing: operational understanding.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** Most likely it's overfilled: many more items than it was sized for, so most bits are 1. Other causes: weak or correlated hash functions, or a bug in the number of hashes. Fix by rebuilding at the right size for expected growth, monitoring the fraction of bits set, or using a scalable Bloom filter.
3
4**Counter-questions:**
5- *"How do you rebuild without downtime?"* → Build a new filter in the background from the source of truth, then swap it in atomically.
6
7**Trap:** blaming randomness.

Q9. When should you not use a probabilistic structure?

They're testing: judgement.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** When the answer must be exact or a mistake is costly: money, inventory, permissions, billing, legal reporting. Also when the data is small enough to count exactly; then exact is simpler and fine.
3
4**Counter-questions:**
5- *"Can you combine them?"* → Yes: a Bloom filter in front of an exact store, so the exact store has the final say.
6
7**Trap:** using one because it's clever, not because it's needed.

Q10. How would a web crawler avoid re-crawling the same URLs, at billions of URLs?

They're testing: a classic application.

Think about your answer first, then open it.

reveal

1Show the strong answer, counter-questions and trap
2**Strong answer:** Normalise URLs, then check a Bloom filter of seen URLs before adding to the frontier. Billions of URLs at 1% need about 1.2 GB per billion, which fits in memory or shards across a few machines. A false positive means skipping a page that wasn't really seen, which is acceptable for a crawler. Persist the exact seen-set on disk for recovery and periodic rebuilds.
3
4**Counter-questions:**
5- *"Pages change; what about re-crawling?"* → That's scheduling by freshness, separate from the seen check; the filter handles "never seen", and a recrawl queue handles "seen, but time to revisit".
6
7**Trap:** a database lookup per discovered URL at billions of URLs.
8
9---
10
11## Practice coverage
12
13Every section in this chapter is tested at least once.
14
15| Section | Tested by |
16|---|---|
17| 20.1 Why approximate | Level 1B.2, Level 5.5, Q9 |
18| 20.2 Bloom filter | Level 1A.1, Level 1B.3, Level 3.1, Level 4, Q1, Q7, Q10 |
19| 20.3 Counting Bloom filter | Level 1A.2, Level 1B.5, Level 3.2, Q2 |
20| 20.4 HyperLogLog | Level 1A.3, Level 1A.5, Level 1B.1, Level 2.3, Level 3.3, Q3, Q4 |
21| 20.5 Count-min sketch | Level 1A.4, Level 2.4, Level 3.4, Q5 |
22| 20.6 Top-K | Level 1B.4, Level 3.5, Level 5.3, Q6 |
23| 20.7 Size vs error | Level 2.1, Level 2.2, Q8 |
24| 20.8 In interviews | Level 5.1, Q6, Q10 |
25
26---

20. Probabilistic Data Structures