Bloom Filter
Space-efficient probabilistic set — answers "possibly in set" or "definitely not" with tunable false-positive rate.
Interview tip Lead with a 30-second definition, then one real system example and name 2–3 designs where Bloom Filter is non-negotiable.
① What it is (30 seconds)
Space-efficient probabilistic set — answers "possibly in set" or "definitely not" with tunable false-positive rate.
② How it works in system design
Multiple hash functions set bits in bit array. Lookup: all bits set → maybe present. Any bit zero → definitely absent. No false negatives for standard insert-only use.
Typical placement
Client→Edge / Gateway→Bloom→Services→Data stores
③ Concrete system design example
Scenario: Web crawler: Bloom filter of seen URLs avoids redundant fetches — 1% false positive just re-crawls a few duplicates, saves 90% DB lookups.
④ Important interview Q&A
| Question | Answer |
|---|---|
| Can Bloom filter delete? | Standard no; counting Bloom or secondary structure needed. |
| False positive rate? | More bits + more hash functions → lower FP rate, more memory. |
| vs Hash set? | Bloom far smaller; hash set exact but memory heavy at billions of keys. |
⑤ Seen in these system designs
- Web Crawler — seen URL filter
- Gmail Search — spam pre-filter
- Google Photos Duplicate — candidate filter
In interviews, after explaining the concept, say: "This shows up directly in …" and link two designs.
⑥ Revision checklist
- No false negatives (insert-only)
- FP rate trade-off
- Memory math
- Use case vs exact set