Bloom Filter Interview Questions: False Positives, Deletions, and Capacity Planning

A Bloom filter returns “maybe present” for a URL your crawler has never seen. Is that a harmless extra database lookup, or did you just discard a page you needed to crawl? The answer depends on what the application does with the result.

That application decision is central to Bloom filter interview questions. You need to size the filter, interpret its error rate correctly, explain why deletion is dangerous, and preserve the conditions under which a negative result is trustworthy.

The worked examples below focus on membership decisions; the broader B+ tree and LSM tree guide explains where filters fit in a storage engine.

Evidence boundary: primary research and official Redis documentation support the mechanics and product behavior. The numbers, failure cases, and design recommendations are original examples. No independently verified candidate reports establish these exact questions or their interview frequency.

What Does a Bloom Filter Answer Mean?

Official fact: a standard Bloom filter represents a set using a bit array and hash-derived positions. Insertion sets positions to one. A membership check returns negative if any required position is zero; otherwise it returns a possible match. Collisions can make a nonmember appear present. Redis Bloom filter documentation

For the standard insert-only structure, a successfully inserted item remains positive if the bits and hashing rules remain intact. That is the scope of the no-false-negatives property. It is not a guarantee that every application database row has reached every filter replica.

A positive result is not a uniqueness constraint. If a username check must be correct, confirm possible matches in the authoritative store, and still enforce uniqueness atomically when inserting. Two concurrent requests can both pass a precheck before either creates the username.

For a crawler that may deliberately sacrifice a small amount of coverage, discarding possible duplicates can be an explicit approximation. For billing deduplication, discarding a legitimate event because of a collision can lose revenue or corrupt a ledger. State the error consequence before choosing the structure.

What Does a One Percent False-Positive Rate Mean?

It means approximately one percent of queries for absent items return positive under the model's assumptions. It does not mean one percent of all positive answers are wrong. That second quantity also depends on how often the workload asks about members.

Worked example: suppose one million queries contain 10,000 actual members and 990,000 nonmembers. With a one percent false-positive rate and a complete filter, expect about 10,000 true positives and 9,900 false positives. Nearly half the positive answers are wrong, even though the filter meets its one percent target.

Now change the workload to 900,000 actual members and 100,000 nonmembers. The same error rate produces about 1,000 false positives among 901,000 positive answers. The filter's property did not change; the query mix did.

This distinction also determines savings. If every positive triggers an exact lookup, the first workload performs about 19,900 exact lookups instead of one million. The second performs about 901,000. A filter is much less valuable when almost every lookup is a hit already.

In an interview, name the denominator whenever you quote a percentage. “False positives divided by known absent probes” is an error-rate estimate. “False positives divided by all positive answers” is the false-discovery fraction. They answer different operational questions.

How Do You Calculate Bits and Hashes?

Let n be the expected distinct inserted items, m the number of bits, and k the number of hash positions per item. Under the usual uniform-hashing approximation:

p ≈ (1 - exp(-k*n/m))^k
m ≈ -n*ln(p) / (ln(2)^2)
k ≈ (m/n)*ln(2)

These are standard approximate relationships, not an exact promise for every finite filter and hash implementation. The research analysis explicitly states the hashing assumptions and explains why the optimum occurs near half the bits being set. Kirsch and Mitzenmacher: Less Hashing, Same Performance

Calculated example: for one million distinct keys and a target p=0.01, allocate approximately 9,585,059 bits and choose seven hash positions. The raw bit storage is about 1.20 MB in decimal units, or 1.14 MiB. Add implementation metadata, alignment, replicas, and any growth overhead separately.

Compare that with a one-in-a-thousand target: roughly 14.38 bits per item and ten hash positions. A lower error rate costs memory and probe work. It is worthwhile only if the avoided downstream work justifies those costs.

Do not blindly round every quantity down. Round storage up, examine nearby integer values for k, and recompute the expected rate. Also size against the distinct population over the filter's actual lifetime, not an average minute of traffic. Repeatedly inserting the same item into a standard bit filter does not add new set membership, although operational counters may have different semantics.

Reproduce Capacity Saturation

Local experiment: we implemented a deterministic Python 3.12.14 filter for 10,000 keys and a one percent target. It used 95,851 logical bits and seven positions derived from SHA-256 with separate numeric prefixes. A bytearray stored one logical bit per byte for readability, so this demonstration does not measure compact memory consumption or production throughput.

We inserted strings in:0 through in:9999, checked every inserted item, and then queried 100,000 distinct absent strings beginning with out:. All inserted keys were positive. The absent probes produced 974 false positives: 0.974 percent. About 51.94 percent of the logical bits were set.

Then we inserted another 10,000 distinct keys without changing the array or hash count. The same absent probes produced 15,752 false positives: 15.752 percent. The approximate formula predicts about 15.745 percent at that doubled population.

Fixed hashing and inputs make this experiment reproducible. Its observed rate is not a confidence guarantee for a different workload, implementation, or adversarial input set. The result demonstrates a capacity failure: doubling population can increase error far more than twofold.

A useful follow-up is whether extra hashes solve the overloaded filter. They do not automatically help. Once too many bits are set, additional required positions must be evaluated against a new optimum; excessive hashing can worsen both occupancy and CPU cost. Rebuild with an appropriate capacity or use a supported growth strategy.

Why Can't You Just Clear Bits to Delete an Item?

Use a tiny counterexample. Suppose item A maps to positions {1,3}, while B maps to {3,5}. After inserting both, bits 1, 3, and 5 are set. Clearing A's positions also clears bit 3, so B now tests negative despite still being a member. Our local fixture reproduced this shared-bit failure.

A counting Bloom filter replaces each bit with a counter. Insertion increments the corresponding counters; deletion decrements them. That enables a controlled deletion operation, but only if insertion and deletion accounting remains correct. Counting filters are a recognized variant in the primary research. Bloom filter analysis and variants

Design caution: a positive membership test alone is not proof that an item was inserted. Decrementing counters for a false-positive nonmember can damage real members. Double deletion, unmatched repeated insertion, counter overflow, and concurrent lost updates create similar accounting risks.

Therefore, explain how the application knows an item is eligible for deletion. An authoritative lifecycle record, exact reference count, or carefully defined multiset contract may be needed. The extra counters also cost more memory than a bit array.

If deletion is rare, immutable generations and periodic rebuilding may be simpler. If deletion is essential, compare a counting filter or another deletion-capable probabilistic structure against an exact set. Choose based on the required error behavior, deletion rate, memory budget, and operational complexity.

Can a Real System Still Produce False Negatives?

Yes, relative to its authoritative dataset. A replica may be stale; an update may have failed; a filter may be rebuilt from an incomplete snapshot; or the query path may normalize keys differently from the insertion path. Those failures break the completeness or consistency assumptions behind a trustworthy negative result.

Imagine the database commits key K and the asynchronous filter update has not arrived. A negative result cannot safely prove K is absent from that database. A design that skips the database immediately can return incorrect information even though the bit-array algorithm works perfectly.

Engineering recommendation: define what dataset and version each filter covers. For immutable SSTables, a filter can be built with the file and published as part of the same validated artifact. For a mutable global index, define a catch-up watermark and a fallback path while coverage is incomplete.

During a rebuild, keep the old filter serving while constructing the new generation from a snapshot and replaying concurrent inserts. Switch only after the new generation covers the required watermark. If coverage cannot be established, bypass the filter and consult the exact store. Never interpret an unavailable filter as an empty, authoritative set.

Also preserve the hash algorithm, seeds, key encoding, and normalization with the serialized representation. A filter built with one convention and queried with another is not meaningfully compatible, even if both arrays have the same size.

How Should You Plan Growth and Monitor Cost?

Official product behavior: Redis BF.RESERVE accepts an error rate and an initial capacity. Scaling can add subfilters; NONSCALING prevents this and returns an error when capacity is reached. EXPANSION controls the growth factor for additional subfilters. Those semantics differ from silently overfilling the fixed array in our experiment. Redis BF.RESERVE

In a design answer, distinguish the textbook structure from the chosen library. Establish what happens when an insertion fails, how callers observe it, and whether membership checks may consult multiple generations. More capacity can increase memory and lookup work even when the implementation manages error bounds.

Track successful insertions, population estimates, occupancy where available, generation count, insertion failures, memory, and exact-store lookups. Estimate observed false positives using samples whose true absence can be checked. A dashboard that divides every positive result by total traffic does not measure the false-positive rate.

For a simple cost model, let q be the fraction of queries for true members, Cf the filter cost, and Cs the exact-store lookup cost. Expected cost is approximately Cf + [q + (1-q)p]Cs. Compare it with Cs, including network overhead if the filter is remote. This is an illustrative model; benchmark the actual distribution before claiming a latency improvement.

Practice the Membership Contract

Practice question	What to rehearse
Deduplicate a File Exactly When Distinct Lines Exceed Memory	Keep exact deduplication despite a probabilistic precheck.
Design streaming difference at scale	Define which approximation the stream permits.
Design a Large-Scale Polite Web Crawler	Decide whether false positives may reduce crawl coverage.
Design file deduplication algorithm	Separate membership hints from content equality.
Design a generic key-value store	Place a filter before expensive storage reads.

For a short rehearsal, calculate the one-million-key filter, explain the 990,000-absent-query example, and draw the {1,3} / {3,5} deletion failure. Then add a delayed insertion and explain the fallback. Those four steps connect mathematics, implementation, and product correctness.

Continue with Backend Engineer interview practice. For every proposed Bloom filter, state the covered set, the error consequence, the capacity assumption, and the source of truth used when the answer is uncertain.

Sources and Further Reading

• Redis: Bloom filter
• Redis: BF.RESERVE
• Kirsch and Mitzenmacher: Less Hashing, Same Performance