linkjobnotes
linkjobnotes




Something about yourself
Bloom Filters in System Design Interviews: When and How to Use Them
Bloom filters come up in system design rounds more often than people expect: "how would a web crawler avoid revisiting URLs?", "how does a database skip disk reads for keys that do not exist?", "how do you check if a username is taken without hitting the database?". Here is a compact way to explain them.
What a Bloom filter is
A Bloom filter is a bit array of size m plus k independent hash functions. To add an item, hash it k times and set those k bits to 1. To check an item, hash it k times: if any bit is 0, the item is definitely not in the set; if all bits are 1, the item is probably in the set.
So it answers "definitely not" or "maybe yes". There are no false negatives, only false positives.
The numbers interviewers like
For n items and a target false positive rate p:
bits needed: m = -n * ln(p) / (ln 2)^2
best number of hashes: k = (m / n) * ln 2
A useful rule of thumb: about 10 bits per item gives roughly a 1% false positive rate with k = 7. For 1 billion URLs that is about 1.2 GB, which fits in memory on one machine. Saying this number out loud shows you can reason about capacity.
Where to use it in a design
Web crawler: check the Bloom filter before adding a URL to the frontier. A false positive means you occasionally skip a new page, which is usually acceptable.
LSM-tree databases (Cassandra, RocksDB, LevelDB): each SSTable keeps a Bloom filter so a read can skip files that cannot contain the key.
Caching layer: avoid caching one-hit wonders by only caching keys seen at least once before.
Username or coupon checks: answer most "not taken" queries from memory and only go to the database on "maybe".
Trade-offs to mention
You cannot delete from a standard Bloom filter, because clearing a bit can remove other items. A counting Bloom filter (small counters instead of bits) supports deletes at about 4x the memory.
The filter must be sized up front. If n grows past the plan, the false positive rate climbs; scalable Bloom filters chain new filters as they fill.
In a distributed setup, decide whether each node keeps its own filter or you shard the filter by key range.
A 60-second answer template
"I would put a Bloom filter in front of the expensive lookup. With 10 bits per element we get about 1% false positives and no false negatives. A false positive only costs us one extra lookup, so correctness is preserved. If we need deletes, I would switch to a counting Bloom filter."
Practicing it
Explaining the math clearly under time pressure is the hard part. I build Linkjob AI, an AI interview assistant, and we use mock rounds like this one to practice structured answers. Disclosure: I work on that product.
