Bloom Filters in a System Design Interview: When "Probably Yes" Is Good Enough

Bloom filters come up in system design rounds more often than people expect: checking whether a username is taken, skipping disk reads for keys that are not in an SSTable, or avoiding recrawling URLs. The trick is to explain the guarantee precisely and then show you know the trade-offs.

The one-sentence guarantee

A Bloom filter answers "is x in the set?" with either definitely not or probably yes. No false negatives, some false positives. Say this early; interviewers listen for it.

How it works

Keep a bit array of size m and k independent hash functions. To insert, set the k bits the hashes point to. To query, check those k bits: if any is 0, the item was never inserted; if all are 1, it might have been, or other items may have set those bits.

Sizing it out loud

For n items and a target false-positive rate p, the standard formulas are m = -n ln p / (ln 2)^2 and k = (m/n) ln 2. A useful rule of thumb: about 10 bits per item gives roughly a 1% false-positive rate with 7 hash functions. For 100 million URLs that is around 120 MB, which fits comfortably in memory, versus many gigabytes for storing the URLs themselves.

Where it fits in an answer

• LSM-tree storage: one filter per SSTable so a read can skip files that cannot contain the key.
• Web crawler: a "seen URL" filter in front of the frontier; an occasional false positive just means one page is skipped.
• Cache penetration: reject lookups for keys that do not exist before they hit the database.

Always state what a false positive costs in that context. If it costs one extra database read, it is fine. If it means wrongly rejecting a payment, a Bloom filter is the wrong tool on its own.

Follow-ups to expect

• Can you delete? Not from a standard filter. Mention counting Bloom filters (small counters instead of bits) or rebuilding periodically.
• What if the set keeps growing? The false-positive rate climbs as the array fills. Use scalable Bloom filters (a chain of filters with tightening rates) or rebuild with a larger m.
• Distributed? Filters can be merged with bitwise OR if they share size and hash functions, which is handy for sharded crawlers.
• Alternatives? Cuckoo filters support deletion and are often more space-efficient at low false-positive rates.

A compact way to present it

State the guarantee, give the sizing estimate with real numbers, place it in the design where a false positive is cheap, and pre-empt the deletion question. That sequence takes two minutes and shows depth without derailing the main design.

Disclosure: written by the team behind Linkjob AI, a real-time interview copilot. We practice system design explanations like this one with our own tool.