Prompt and context
Implement a Bloom filter with add(value) and mightContain(value). It is a prefilter before an expensive lookup: false means the value is definitely absent, while true means the authoritative store must still be checked. Cover n, p, m, k, deletion, resizing, concurrency, and tests.
What the interviewer is testing
Correct membership semantics
A standard Bloom filter permits false positives but not false negatives. The name mightContain should prevent callers from treating true as proof of membership.
Explainable sizing
The bit-array length m and hash count k control memory, speed, and error rate. Ask for expected cardinality and an acceptable p before choosing parameters.
Complete boundaries
A strong answer states that the standard structure cannot safely delete one value, saturation raises the false-positive rate, and growth requires rebuilding or a scalable layered design.
Questions to clarify first
- How many values are expected, and what false-positive rate p is acceptable?
- Is the value serialized to a stable byte sequence across processes and versions?
- Is the filter append-only, or must it support deletion and updates?
- What are the memory, latency, and concurrent-write budgets?
- When capacity is reached, should the filter rebuild, reject writes, or add a layer?
- How will false positives and authoritative confirmations be measured?
A 30-second answer
“I would use an m-bit array and k sufficiently independent positions. add sets those k bits; a zero bit during a query proves absence, while all ones means possible presence. For expected n and target p, use m=-n ln(p)/(ln2)^2 and k=(m/n)ln2. A standard filter cannot delete safely, so deletion needs counting buckets; capacity changes need a rebuild or layers. I would test no false negatives, sampled false-positive rate, saturation, and concurrency guarantees.”
Step-by-step deep answer
State the invariant and API
All bits start at zero. Stable hash functions produce k indexes for each value; insertion only changes bits from zero to one. If a query sees a zero at any required index, that value could not have inserted this exact set of positions.
Compute m and k
For expected n items and target false-positive rate p, use m = -n ln(p) / (ln(2)^2) and k = (m/n) ln(2). With n=1,000,000 and p=1%, m is about 9.6M bits, roughly 1.14 MiB, and k is about 7.
Choose hashes and bit operations
Double hashing can derive positions as h_i(x) = h1(x) + i*h2(x) modulo m, avoiding k full hash implementations. Fix byte encoding, endianness, and seeds; changing them makes persisted filters incompatible.
Explain deletion and resizing
Several values can share a bit, so clearing it for one deletion can create a false negative. A standard Bloom filter therefore has no safe delete operation. Counting Bloom filters add per-bucket counters at a memory cost. When the expected capacity changes, rebuild a larger filter or use multiple capacity-bounded layers.
Handle concurrency and lifecycle
Concurrent reads are usually straightforward. Concurrent writes must not lose bit-setting operations; atomic OR, sharded bit arrays, or a write lock are possible choices. Persist the capacity, m, k, hash algorithm, seeds, and format version together.
Pseudocode
~~~text add(x): for i in 0..k-1: bits[index(hash1(x), hash2(x), i)] = 1
mightContain(x): for i in 0..k-1: if bits[index(hash1(x), hash2(x), i)] == 0: return false return true ~~~
Complexity and verification
Each operation checks or sets k positions, so time is O(k) and extra space is O(m). Test that every inserted value returns true, estimate false positives from random absent samples, observe saturation near capacity, and cover empty, duplicate, seed/version, and concurrent-write cases.
| Operation | Contract | Complexity |
|---|---|---|
add(x) | Sets bits and never removes membership evidence | O(k) |
mightContain(x) | false is definite absence; true is possible presence | O(k) |
| Resize | Rebuild or add a capacity-bounded layer | Depends on item count and m |
Model answer
“A Bloom filter is a probabilistic membership prefilter. I would maintain an m-bit array and k position functions. Insertion sets k bits; a query finding any zero returns false, while all ones returns true but only as ‘possibly present,’ so the backing store confirms it. Compute m and k from n and p; one million items at 1% false positives needs about 9.6M bits and seven positions. The standard structure cannot delete because bits are shared; use a counting variant for deletion and rebuild or layer filters as capacity grows. I would fix encoding and seeds, then test no false negatives and measure false positives on absent samples.”
Common mistakes
Treating true as proof
All required bits being one can result from other values. The caller still needs an authoritative lookup.
Using one hash
A single hash can distort bit distribution and the designed error rate. Use double hashing or explain the independence assumptions behind multiple positions.
Clearing bits for deletion
Clearing a shared bit can make another inserted value return false. Use counting buckets or rebuild instead.
Ignoring saturation
As more bits become one, false positives rise. Track estimated cardinality and set-bit ratio, and rebuild before the budget is exceeded.
Testing only hits
Without absent samples, boundary capacity, and duplicate insertion tests, the implementation does not demonstrate its error contract.
Follow-up questions and responses
Why can’t false positives be zero?
Different values can map to the same finite set of bits. More memory and a suitable k reduce the rate but do not remove collisions.
When would you choose a Cuckoo filter?
Compare it when deletion, fingerprint storage, or lookup behavior matters. Benchmark memory, writes, and deletes instead of choosing by name.
How would you persist it?
Store the bit array with m, k, hash algorithm, seeds, encoding version, and capacity estimate. Validate the version on load.
How would you monitor quality?
Measure backend-confirmed false positives, set-bit ratio, estimated cardinality, lookup latency, and rebuild count. Trigger rebuild or a new layer at a defined threshold.
What assumptions underlie the formula?
It assumes near-uniform hashing, insertion volume near n, and sufficient independence among positions. Calibrate with samples from real data.
How do you avoid lost concurrent writes?
Use atomic bit setting or sharded locks, and ensure readers observe complete writes. If eventual consistency is acceptable, publish merged immutable snapshots.