The Staff Engineer Probabilistic Data Structures Interview: Bloom Filters, Sketches, and Error Budgets

A system-design interviewer asks you to track unique visitors, identify popular objects, and avoid expensive lookups for missing keys. You could draw three exact tables. You could also propose three tiny sketches and declare the memory problem solved. A senior or staff engineer needs a stronger answer: which question does each structure answer, which mistakes can it make, and what happens when the application treats an approximation as a fact?

This guide builds a practice design for an object-access analytics service. Its membership filter protects a storage lookup, its frequency sketch identifies candidates for cache warming, and its distinct counter feeds a dashboard. These are illustrative requirements, not an employer's disclosed interview questions. The recommendations connect algorithm guarantees to application behavior; they are not evidence that a particular answer improves hiring outcomes.

1. Start with the decision and its error direction

Before choosing a structure, ask what consumes the answer. Does a positive response merely trigger another lookup, or does it discard a customer's event? Does an estimated count inform a chart, enforce a contractual limit, or create an invoice? The same numerical error can be harmless in one path and unacceptable in another. Write down the fallback before discussing memory.

A useful opening is: “I will keep authoritative object state and billing records exact. Approximate structures will reduce work or summarize analytics. Each consumer gets an explicit error contract.” Then clarify the identity being counted, the time window, the tolerated staleness, and whether updates can be replayed. A unique user is different from a unique device, and neither definition emerges automatically from a hash function.

The families also answer different questions. Apache DataSketches distinguishes cardinality, frequency, and other sketch families. Membership asks whether a supplied key may be present. Frequency asks how often a supplied key appeared. Cardinality asks how many distinct keys appeared. None of those questions, by itself, asks for a complete list of the keys.

2. Use Bloom filters to reject work safely

A standard Bloom filter sets several positions in a bit array for each inserted key. A lookup finding an unset position can reject membership; finding every position set means the key may be present. RocksDB uses filters on SST files to avoid unnecessary file lookups. That is a concrete place to draw the optimization: a positive continues to the authoritative lookup rather than becoming a returned object.

Explain the condition behind the familiar “no false negatives” statement. It concerns keys successfully inserted into the represented set under the structure's assumptions. If a database write becomes visible before its corresponding filter update, a reader can observe a filter negative for a real database key. That is a publication or freshness defect in the surrounding system, even if the filter implementation is correct.

For the practice design, publish a filter together with an immutable object-index generation, then consult both under that generation identifier. Keep recent writes in an exact delta until incorporated. If a filter is missing, incompatible, or behind the required generation, bypass it and perform the exact lookup. This is a proposed design, not a guarantee provided by the data structure. Discuss whether the backing service has enough capacity for that bypass.

Illustrative sizing and lookup calculation

Redis documents the conventional Bloom sizing formula: approximately m = -n ln(p) / (ln(2))² bits for capacity n and target false-positive probability p. Its optimal hash count is near (m/n) ln(2). These idealized formulas help compare choices; implementation layouts and metadata add overhead.

For an illustrative ten million distinct keys and a one-percent target, the array needs about 95.9 million bits, or 12.0 decimal megabytes, with roughly seven probes. If 100,000 lookups per second are truly absent, a one-percent false-positive rate would produce about 1,000 unnecessary backing lookups per second in expectation. Real present-key traffic still reaches the backing store. Measure the actual workload before interpreting this as a latency or cost saving.

3. Treat growth and deletion as separate requirements

An expected capacity is an operating assumption. Guava warns that inserting substantially more elements than expected deteriorates false-positive probability. In your design, monitor occupancy or the implementation's estimated error, and define when to rebuild. State whether rebuilding temporarily doubles memory, which source supplies the keys, and how readers switch generations without dropping coverage.

Clearing a standard Bloom bit to delete one item can erase evidence shared with another. The 2014 Cuckoo Filter paper describes a fingerprint-based alternative supporting deletion, but also requires that a safely deleted item was previously inserted. Deleting an item merely because an approximate lookup said “present” can remove a colliding item's evidence. Insertion failures and duplicate-insertion handling also belong in the contract.

For a bounded retention window, consider immutable time buckets that expire as units instead of individual deletion. Explain the boundary behavior: a query covering part of a bucket may include older data unless another mechanism filters it. If product requirements demand exact per-record removal, an approximate structure alone does not establish that the requirement is satisfied. Describe the source-of-truth operation and the summary's rebuild or expiry policy separately.

4. Size frequency error against the whole stream

A Count-Min sketch hashes each update into a counter in each row; a point query takes the minimum of the corresponding counters. For nonnegative updates with suitable hashing and no counter overflow, collisions inflate estimates. The original Count-Min paper by Cormode and Muthukrishnan gives a point-query bound: the estimate is no smaller than the true frequency and exceeds it by at most εN with probability at least 1−δ, where N is total update weight. Conventional dimensions are width ceil(e/ε) and depth ceil(ln(1/δ)).

That is an additive error relative to stream mass, not a percentage of each object's own count. In an illustrative stream of one hundred million unit updates, ε = 0.0001 permits an additive error of 10,000 within the stated probability guarantee for a fixed query. A count of fifty is therefore not measured to four decimal places of relative accuracy. A guarantee for one query also needs care before being extended to many queries.

Redis's Count-Min documentation explicitly cautions that low-frequency results can be noise. For cache warming, use the sketch to screen candidates, then verify promising objects with sampled logs or exact counters. Explain where candidate identities come from: querying known keys is different from enumerating the most frequent keys. Keep the candidate mechanism and its memory budget visible in the diagram.

Decide whether replay means another occurrence or recovery of the same event. A repeated increment changes frequency even when the event ID is identical. In this practice design, rebuild each completed analytics window from a declared input range and publish one revision; do not add a replacement window's counters to its previous revision. Keep exact accounting in a different path if retries must never create duplicate charges.

5. Merge distinct populations, not estimated totals

HyperLogLog estimates distinct cardinality. Redis documents up to 12 KB for its implementation and a standard error of 0.81 percent, along with a merge operation for distinct counts across inputs. Those are implementation-specific properties. Standard error describes an error distribution; it is not a hard promise that every answer falls within that percentage.

Suppose two regions each report approximately one million visitors. Adding their estimates does not estimate the global distinct population correctly when people visit both regions. Merge compatible sketch states to represent the union, then estimate it. Define the user identifier and its byte encoding consistently across producers. Otherwise, the same person may hash as different identities before the cardinality algorithm even begins.

If the requirement is “users active in both regions,” choose a structure with supported intersection semantics. DataSketches Theta sketches provide union, intersection, and difference. Its set-operation accuracy documentation explains that mixed set expressions can have larger error distributions than a standard sketch. Ask for bounds on the resulting population, especially when an intersection is small; do not assume subtraction preserves the quality of the input estimates.

6. Make merge compatibility and recovery explicit

“Mergeable” needs a schema. In the practice design, every persisted summary carries its algorithm family, format version, dimensions or precision, hashing configuration, key-encoding version, time interval, and input revision. Reject incompatible states rather than accepting bytes because their lengths happen to match. Test a rolling upgrade with old readers and new writers before changing the serialized format.

Guava's Bloom-filter API makes the compatibility issue concrete: its union requires compatible bit sizes, hash-function counts, strategies, and funnels, and the union must still be sized for the combined set. Correctly OR-ing two filters does not preserve the original error target if the result is overloaded. Compatibility and capacity are separate checks.

Ask whether merging the same input twice is harmless for the selected operation. A membership union can retain the same bits, while adding frequency counters twice counts the stream twice. Persist which partition revision has contributed, and define replacement rather than accidental accumulation. During recovery, verify source coverage and freshness alongside the estimated value. A numerically plausible dashboard can still omit an entire region.

7. Rehearse with adversarial follow-ups

Use this illustrative practice rubric, not an employer's scoring standard: explain the query, error direction, source coverage, update semantics, compatibility rule, and fallback for every box you draw. Rehearse once with a healthy system, then repeat after one region stops publishing, capacity doubles, or a producer changes key encoding. Give each failure a detection signal and an operator action.

For validation, compare summaries with exact results on controlled datasets and retained samples. Exercise empty inputs, repeated keys, skewed frequencies, disjoint and overlapping populations, and incompatible formats. Across repeated randomized trials, inspect the error distribution rather than demanding that every probabilistic estimate equal an exact count. Separately test deterministic safety properties, such as bypassing an unpublished filter generation and rejecting an incompatible merge.

Finish the interview answer by returning to the consumer. The object lookup remains correct when its optimization is unavailable; the cache-warming system can tolerate noisy candidates; the analytics dashboard exposes an estimate with coverage and freshness. If the interviewer changes that dashboard into billing or an exact eligibility decision, revisit the architecture. The preparation goal is to explain where approximation belongs and how you would prove that the surrounding system respects its limits.