Prompt and context
A Cuckoo Filter is an approximate membership structure: false means the item is definitely absent, while true means it may be present. Compared with a standard Bloom Filter, it stores short fingerprints in buckets so it can support deletion and flexible lookups; the trade-off is that insertion may relocate entries and can fail near capacity. This problem tests hashing, array layout, randomization, edge handling, and benchmarking.
What the interviewer is evaluating
- Whether you can explain the relationship between a fingerprint and two candidate buckets.
- Whether removal avoids false negatives and relocation is bounded to prevent loops.
- Whether you handle duplicate operations, full buckets, hash collisions, and concurrency boundaries.
- Whether you choose and validate parameters using capacity, fingerprint bits, and a false-positive target.
Clarifying questions to ask first
Ask for expected item count, slots per bucket, acceptable false-positive rate, and memory budget. Is deletion, persistence, concurrent writing, or deterministic behavior required? Can values be encoded into stable bytes, and must hash seeds remain fixed across versions? On insertion failure, should the system rebuild, add a tier, or let the caller consult the source of truth? What backend cost do false positives create?
A 30-second answer framework
For each value I would compute a non-zero fingerprint f and a primary bucket i1, then derive a second bucket i2 from the fingerprint so f can live in exactly two candidates. Lookup checks both buckets; removal clears only a matching fingerprint, unlike clearing shared bits in a Bloom Filter. Insertion tries either bucket first, then performs bounded random relocations when both are full. Reaching the kick limit returns failure and triggers a rebuild or another tier. Fingerprint length, bucket capacity, and maximum load must be calibrated with false-positive, insertion-success, and latency tests.
Step-by-step deep dive
1. Define interfaces and invariants
After a successful add(x), its fingerprint must be in one of the two candidate buckets. mightContain(x) returns false only when neither bucket contains f; remove(x) clears only a matching fingerprint. If two values share a fingerprint, removing one may leave the other returning true, an acceptable false positive, but an inserted value must not become false.
2. Generate fingerprints and candidate buckets
Compute the primary index i1 from a stable encoding, then take a fixed-length non-zero fingerprint f. Derive i2 = i1 XOR hash(f) and reduce it by the bucket count. Index and fingerprint calculation must fix the hash algorithm, seed, byte order, and version; otherwise persisted entries or resized tables become unreadable. Short fingerprints raise the false-positive rate, while long ones consume more memory.
3. Design bucket layout and lookup
Each bucket stores a fixed number of fingerprint slots rather than full values. Lookup reads only i1 and i2, returning “possibly present” when either contains f. Bucket width affects load and local collisions. A contiguous array can reduce pointer overhead; persist bucket count, slot count, fingerprint bits, and hash version with the table.
4. Handle insertion and bounded relocation
Try an empty slot in either candidate bucket. If both are full, choose a bucket and slot, evict its fingerprint, and move the evicted fingerprint to its alternate bucket. Relocation needs a maximum count or visited-bucket guard; it must not loop forever. Make randomness, kick count, and failure cause observable so high load can be distinguished from a poor hash distribution.
5. Implement deletion and duplicate operations
Search both candidate buckets for a matching fingerprint and clear one slot. If callers require strict element-level deletion, short fingerprints can collide; verify against an authoritative store or use longer fingerprints. remove should be idempotent for absent values. Define whether duplicate add consumes another slot; you may allow duplicates or detect an existing fingerprint and skip the write.
6. Test, fail, and resize safely
Test that inserted values never produce false negatives, random absent values produce the expected false-positive rate, deletion behaves as specified, duplicate operations are stable, full buckets relocate, and deterministic inputs behave consistently. Record load factor, relocation failures, lookup latency, and memory. At a threshold, rebuild with a larger table or add a tier; retain the old snapshot during resize so readers do not observe a gap.
Model high-quality answer
I would compute a stable non-zero fingerprint f and primary bucket i1, then derive i2 = i1 XOR hash(f); each bucket stores a fixed number of fingerprints. Lookup checks both and returns false only when f is absent from both. Deletion clears a matching slot, so it does not clear shared bits as a Bloom Filter would; if a short-fingerprint collision matters, consult the source of truth. Insertion tries both buckets, then performs bounded random kicks and returns failure at the limit. I would fix encoding, hash seed, bucket count, slots, and version, define duplicate behavior, and make deletion idempotent. Tests cover no false negatives for inserted values, absent-sample false positives, deletion, full buckets, relocation failure, and concurrent boundaries. High load or failure rate triggers a rebuild or another filter tier.
Common mistakes
- Treating a Cuckoo Filter as an exact set and ignoring false positives.
- Storing only one bucket index, so an evicted fingerprint cannot find its alternate.
- Omitting a kick limit and allowing a cycle to block the request.
- Allowing a zero fingerprint that is indistinguishable from an empty slot.
- Clearing an entire bucket or the wrong slot during deletion, creating false negatives.
- Ignoring duplicate operations, persistence versions, dual reads during resize, and insertion failure.
Follow-up questions and responses
Why can a Cuckoo Filter delete while a Bloom Filter normally cannot?
A Cuckoo Filter removes a fingerprint from a specific slot. A Bloom Filter bit may be shared by multiple values, so clearing it can break another value. Both can return false positives, and strict deletion still requires thinking about fingerprint collisions.
How do you choose fingerprint length and bucket width?
Start with item count, target false-positive rate, memory, and load goals. Use theory to estimate fingerprint bits and slots, then benchmark with the real distribution. Longer fingerprints reduce false positives but use more space; wider buckets can improve load at the cost of scanning.
Can you just drop a new item when relocation reaches the limit?
Return an explicit failure; never claim that insertion succeeded. The caller can rebuild a larger filter, write to another tier, or retain the item in the source of truth. Monitor load and failure rate so membership is not silently lost.
How do you make lookup and removal consistent across threads?
Choose snapshot or locking semantics. Use atomic slot updates, sharded locks, or immutable snapshot publication. Concurrent lookup and removal may allow a transient false positive unless the contract requires linearizability; ordinary unsynchronized memory accesses are not a consistency design.