Prompt and context
Implement a static Xor Filter with batch construction and membership queries. Explain the three-segment layout, peeling queue, fingerprint assignment, build retries, false-positive rate, and why in-place deletion is unsupported.
An Xor Filter is a static approximate-membership structure: it stores a short fingerprint for each key and XORs fingerprints at three positions during a query. Research shows it can compete with Bloom and Cuckoo Filters on space and lookup speed, but construction depends on a peelable random hypergraph. A failed seed requires rebuilding, so the structure fits batch generation followed by read-only publication.
What the interviewer evaluates
The interviewer checks whether you can build the three arrays, handle duplicates and an empty set, peel a hypergraph with a degree queue, assign fingerprints in reverse order, use identical hashing for build and query, calculate false positives, explain deletion and update limits, and reason about retries, peak memory, and concurrent reads.
Clarifying questions
Dataset and update model
Confirm key count, duplicate policy, rebuild cadence, update latency, and whether deletion is mandatory. Xor Filters target static sets; dynamic workloads should compare Cuckoo Filters or layered rebuilds.
Error and space targets
Confirm the acceptable false-positive rate, fingerprint width, whether false negatives are allowed, and the priority between lookup throughput and peak build memory.
Key and hash boundary
Confirm whether keys are integers, byte strings, or structured objects; how the hash seed is persisted; and whether cross-language implementations require identical byte order and normalization.
30-second answer
“I divide the table into three segments; each key maps to one position in each segment and stores a fixed-width fingerprint. During construction I track slot degrees and incident edges, peel degree-one slots, and rebuild with a new seed if edges remain. In reverse peel order, a slot is assigned the key fingerprint XOR the other two slot values. A query recomputes the three positions and XORs them; equality means ‘possibly present.’ The table is static and approximate, so it does not support safe in-place deletion.”
Step-by-step solution
Step 1: Define layout and fingerprints
Derive three positions and a low-bit fingerprint from independent 64-bit hash results. Split the table into roughly equal segments and reduce each position within its segment. Define zero-fingerprint handling consistently so an empty slot cannot be confused with a real value.
Step 2: Build hypergraph degrees
Treat each key as a hyperedge connecting three slots. During construction, store each slot’s degree and incident-edge list, then enqueue degree-one slots. Deduplicate keys first or define set semantics explicitly; otherwise one hyperedge can be counted repeatedly.
Step 3: Peel the graph
Pop a degree-one slot, find its unique edge, and record the edge, unique slot, and other two slots. Remove the edge and decrement the degree of all three slots; enqueue newly degree-one slots. If unremoved edges remain after the queue empties, this seed produced a non-peelable graph.
Step 4: Assign fingerprints in reverse
Process recorded edges in reverse peel order. Set the unique slot to the key fingerprint XOR the current values of the other two slots. XORing all three slots then yields that key fingerprint; unwritten slots contribute zero.
Step 5: Implement lookup
Lookup uses the same seed, position function, and fingerprint function as construction, reads the three segments, and XORs them. Equality means only “possibly present,” not proof of membership; the caller must resolve hits against a database or exact set.
build(keys):
repeat with a new seed:
edges = positions_and_fingerprints(keys, seed)
queue = all degree-1 slots
order = peel(edges, queue)
if order contains every edge:
table = zeroed slots
for edge in reverse(order):
table[edge.unique] = edge.fp XOR table[edge.other1] XOR table[edge.other2]
return seed, table
fail after bounded retries
contains(key):
a, b, c = positions(key, seed)
return table[a] XOR table[b] XOR table[c] == fingerprint(key)Step 6: Handle failure and resources
A build failure is not a lookup false negative; it means the graph for this seed has no complete peel order. Bound retries, change the seed or table size, and return an explicit error rather than publishing a partial table. Degree arrays, edge lists, and the peel stack make peak build memory larger than the final read-only table.
Step 7: Explain updates and verification
The table solves equations over the complete key set, so an insertion or deletion can break other keys’ XOR relationships. Update by rebuilding, atomically swapping two versions, or layering small filters. Test an empty set, one key, duplicates, hash collisions, failed builds, serialization recovery, false positives, and concurrent read-only lookups.
Model answer
I would map the key set to a three-segment 3-uniform hypergraph, peel it with a degree queue, and assign short fingerprints in reverse peel order. Lookup performs three slot reads and XORs, so it is constant time, but the result is approximate membership. A build failure means the current seed is not peelable; I would retry with a new seed under a bound and reject publication after the limit. Because the table depends on every key, in-place insertion or deletion is unsafe; production updates rebuild a new table and atomically swap it. Persist the seed, table size, fingerprint width, and byte order with the version, then measure false positives against an exact set.
Common mistakes
- Mistake: Returning a partial table after construction fails. → Why it fails: Unprocessed edges can create false negatives. → Fix: Change the seed or table size and publish only after every edge is assigned.
- Mistake: Using a different seed or segment mapping at lookup. → Why it fails: Build and lookup address different slots. → Fix: Persist and version the seed, segment boundaries, and hash implementation.
- Mistake: Treating a positive lookup as exact membership. → Why it fails: Short fingerprints create false positives. → Fix: Use the filter as a pre-check, then consult exact storage.
- Mistake: Supporting in-place deletion. → Why it fails: Shared slots participate in other XOR equations. → Fix: Rebuild, use two versions, or choose a dynamic filter.
Follow-ups and responses
Why use three segments instead of one array?
Three segments give every edge one slot in each region, which makes the peelable hypergraph construction and constant-time lookup practical. Exact proportions and load factor should be benchmarked.
How do you choose fingerprint width?
Shorter fingerprints reduce space but increase false positives. Measure misses with independent keys and balance the resulting exact-store lookup cost against memory savings.
Do seed retries make results unstable?
The table changes, but lookups are reproducible when the final seed, version, and table are persisted together. Include construction metadata in the same release manifest.
When would you choose Bloom or Cuckoo Filter instead?
Frequent insertion, deletion, counting, or online resizing favors a dynamic filter. Xor Filters are strongest for static, batch-built sets where compact read-only lookup matters.