Question 1

What does a counting Bloom filter change, and what does it cost?

Accepted Answer

Hit these points: it replaces each bit with a small counter (commonly ~4 bits) → add increments the k counters, remove decrements them — so it supports deletes, which a standard filter can't → the cost is roughly 4× the memory of a plain bit array → watch for counter overflow under heavy duplication → reach for it only when you genuinely need deletes and can pay the space.

Question 2

What problem does a scalable Bloom filter solve?

Accepted Answer

Hit these points: it handles unknown or growing n without saturating → when the current filter fills, it adds a new, larger filter to the chain → geometric error bounds across layers keep the total FP rate capped → a query checks each layer until a "maybe" or runs out and returns "no" → cost: memory grows with n and you pay roughly k probes per layer → use it when you can't size n up front.

Question 3

What's a cuckoo filter and where does it beat a Bloom filter?

Accepted Answer

Hit these points: it stores short fingerprints in buckets, with each item having 2 candidate buckets (cuckoo hashing) → it supports deletes (remove the fingerprint) and has good locality — typically 2 bucket probes → it's smaller than a Bloom filter once the target FP rate is low (roughly p &le; 3%; illustrative) → trade-off: insertions can fail/relocate when buckets are full, so it has a load-factor ceiling → pick it for deletes + tight space at low error rates.

Question 4

What does a blocked / register-blocked Bloom filter optimize, and at what cost?

Accepted Answer

Hit these points: it packs an item's k bits into a single cache line (or register) → so a lookup is one memory access instead of k scattered ones → that's a speed/locality win on modern CPUs → the cost is a slightly worse FP rate for the same bits, because confining bits to one block reduces independence → use it when lookup throughput / cache misses dominate and you can spare a touch of accuracy.

Question 5

You need deletes but RAM is very tight. Counting or cuckoo — which, and why?

Accepted Answer

Hit these points: prefer a cuckoo filter — it supports deletes and is smaller than a counting Bloom (and smaller than standard Bloom once p is low) → counting Bloom pays ~4× the bits for its counters, which is exactly what "RAM is tight" rules out → the cuckoo trade-off: insertion can fail near the load-factor ceiling, so size for a safe load factor and have a resize/rebuild path → if deletes were rare you'd skip both and just rebuild a standard filter, but "need deletes + tight RAM" points squarely at cuckoo.

Question 6

Item count n is unknown and may grow a lot. Which variant, and what's the failure mode you're avoiding?

Accepted Answer

Hit these points: use a scalable Bloom filter that chains new, larger layers as it fills → the failure mode you're avoiding is saturation: a fixed-size standard filter sized for the wrong n silently drives its FP rate toward 1 as it overfills → scalable keeps the aggregate FP capped via geometric error bounds → cost: memory grows with n and lookups probe each layer → alternative is sharding fixed filters by key hash, but that still needs a growth plan; scalable bakes the growth in.

Question 7

What's the Staff framing of a Bloom filter in a pipeline — what is it, and what is it not?

Accepted Answer

Hit these points: it's a cheap negative filter in front of an expensive, authoritative check — not the source of truth → "no" is certain, so it removes the bulk of work (drops/skips) without a lookup; "maybe" falls through to the real store → it never decides correctness — it just strips the cheap certainties so the authoritative path handles a fraction of traffic → the anti-pattern is treating "maybe present" as a final answer for anything correctness- or money-sensitive → the whole value is the certain "no" eliminating real cost.

Question 8

When should you reach for NO filter variant at all — just use a real data structure?

Accepted Answer

Hit these points: when false positives are unacceptable and there's no cheap verify step — use an exact set/index → when you must enumerate or return the items — filters store no keys, so they can't list anything → when the set is tiny (a few thousand) — a plain hash set is smaller, exact, and supports deletes, so there's no win → when queries are hit-dominated — "maybe" every time buys nothing → the discipline: a filter earns its keep only when negative answers are common and a certain "no" removes real work.

Question 9

Standard Bloom is the default — defend that, then steelman reaching for a variant by default.

Accepted Answer

For standard-as-default: best space at a given FP rate, dead simple, no insertion-failure modes, well understood operationally — variants each add a cost (4× RAM, layered probes, load-factor ceilings). Steelman for a variant: if you know the system will churn (deletes) or grow unbounded (unknown n), starting standard guarantees a painful migration or a saturation incident later, so picking cuckoo/scalable up front is the honest choice. Synthesis: default to standard and only deviate when a specific limit provably bites — deletes → counting/cuckoo, unknown n → scalable, speed → blocked — decided by the workload, not by reaching for the fanciest tool.

Question 10

Two variants each fix one of your problems but cost on another axis. How do you make the call?

Accepted Answer

Hit these points: name the axes explicitly — deletes, growth (unknown n), space, speed/locality — and rank which limit actually bites your workload → quantify the cost of each variant against your real budget: counting's 4× RAM across a fleet, cuckoo's insertion-failure ceiling and rebuild, scalable's per-layer probes and growing memory, blocked's slightly higher FP → prefer the change that relieves your binding constraint while costing on an axis you have slack on → consider composition (e.g., scalable + per-layer blocked) only if the complexity is justified → the staff move: pick from the limit that bites, with the cost stated, and a rebuild/migration path — not "it's the newest, so it's better."

Question 11

Design dedup for a 100-node, 10B-event/day ingest pipeline with 0.1% duplicate tolerance — what and why?

Accepted Answer

Hit these points: per-node Bloom filter in front of an authoritative dedup store (Redis / sharded KV) → the Bloom is a cheap negative filter: "no" is certain, so it drops most duplicates locally; only "maybe" hits pay the cross-node/store lookup — that's where the savings live → size each filter from target p (~0.1% → ~14.4 bits/item; illustrative) → if per-node n is unknown/unbounded, use a scalable Bloom so the FP rate stays capped as it grows → shard the authoritative store by key and roll/rebuild filters on a time window (events expire), so saturation never pushes FP up → cuckoo or counting only if you actually need deletes → structure: cheap-negative-filter framing, size from p, name the source of truth, scalable for unknown n, rebuild/shard plan for saturation.

Question 12

Design a distributed dedup tier for a high-throughput event pipeline using the right filter variant(s).

Accepted Answer

A strong answer covers: per-node/local filter as a cheap negative filter in front of a sharded authoritative dedup store, so most duplicates die locally and only "maybes" pay the network/store cost → choose the variant from the binding limit: unknown/growing per-node n → scalable Bloom (or time-windowed rolling filters if events expire); continuous deletes → cuckoo (deletes + tight space) over counting's 4× RAM → size from target p set by the cost of a false "maybe" (a cross-node lookup) &times; event rate → shard the authoritative store by key hash for horizontal scale; roll/rebuild filters per window to cap saturation and age out stale entries → correctness: "maybe" never decides dedup alone — it gates the authoritative check → observability: measured FP, load factor, verify-hit rate, with alerts that trigger a new scalable layer or a roll → trade-offs: scalable's growing memory + per-layer probes vs static saturation; cuckoo's insertion ceiling vs counting's RAM; local filter staleness vs network savings.

Question 13

Design a CDN/cache "one-hit-wonder" admission filter so single-access objects never pollute the cache.

Accepted Answer

A strong answer covers: goal — admit an object to cache only on its second request, so objects requested once (the bulk of long-tail traffic) never evict hot content → use a Bloom filter as a "have I seen this key before?" gate: on a request, if the filter says "no" → record it in the filter but don't cache; if "maybe seen" → admit to cache → the asymmetry is fine here: a false positive admits a true one-hit-wonder occasionally (small waste), and there are no false negatives that would block a genuinely repeated object → n (distinct keys per window) is large and shifting, so use time-windowed/scalable filters that roll so old keys age out and the filter never saturates → size from a tolerable FP rate (illustrative) and per-window key estimate → observe admission rate and cache hit-ratio lift → trade-offs: a tighter filter (more bits) reduces wasteful admissions but costs RAM; rolling windows trade a little staleness for bounded size and built-in expiry; this is a classic Bloom admission policy (e.g., TinyLFU-style) where the filter's certain "no" is exactly what protects the cache.

Variants at scale: pick the one whose limit bites

The decision matrix

What each one actually changes

The Staff use: a cheap negative filter

When NOT to use any of them

Retrieval practice

Rehearse out loud

Primary sources (read these next)

Interview — pick your bar