Bloom Filters for Data Engineers: Cheap Membership Tests

bloom filters are the data structure you reach for when the real question is not "what is the value?" but "have I seen this key before?" — and you need the answer in constant time, in a handful of bits per element, against a set far too large to keep in memory as a hash table. A bloom filter is a probabilistic data structure that answers a membership test with one of exactly two verdicts: definitely not in the set, or possibly in the set. That asymmetry is the whole trick. It never says "yes" with certainty, but it never says "no" incorrectly — so a downstream system can treat a "definitely not" as gospel and skip an expensive lookup, a disk read, or a network round-trip entirely, while treating a "maybe" as a cheap pre-filter that occasionally lets a non-member through.

The price of that speed and space is a tunable false positive rate — the probability that the filter says "maybe" for a key it has never seen. You buy the filter's compactness with that error, and the entire engineering discipline of bloom filters is about sizing the bit array and choosing the number of hash functions so the false positive rate lands exactly where your pipeline can tolerate it. Get the math right and a filter for a hundred million keys fits in a couple of hundred megabytes at a tenth of a percent error; get it wrong and either the filter overflows into uselessness or you waste memory you did not need to spend. This guide walks the contract, the sizing math, the deletion-capable and growth-capable variants, the way LSM-tree databases wire a bloom filter in front of every SSTable, and a tuned Python implementation you can lift into a streaming dedup job.

When you want hands-on reps immediately after reading, drill the data-structures practice library →, rehearse hashing on the hash-table practice library →, and sharpen the sizing math on the optimization practice library →.

---

On this page

• What a bloom filter actually is
• The math — bits, hashes, and false-positive-rate sizing
• Variants — counting and scalable bloom filters
• Bloom filters in databases — LSM and SSTable
• Building and tuning one in Python
• Cheat sheet — bloom filter recipes
• Frequently asked questions
• Practice on PipeCode

---

1. What a bloom filter actually is

The one-sided-error membership test — "definitely not" is certain, "maybe" is probabilistic

The one-sentence invariant: a bloom filter is a fixed-size bit array plus k independent hash functions that records set membership by turning bits on, answers a membership test with either "definitely not present" (certain, zero false negatives) or "possibly present" (a small tunable false positive rate), and buys that compactness by discarding the ability to enumerate or delete the set it stores. Everything else about bloom filters — the sizing formulas, the counting variant, the LSM integration — is a consequence of this single asymmetric contract, and the fastest way to lose a senior interview is to describe a bloom filter as "a fast hash set" instead of naming the one-sided error up front.

The two moving parts.

• The bit array. A vector of m bits, all initialised to 0. This is the entire stored state — there are no keys, no pointers, no values. A bloom filter for a billion URLs holds no URLs; it holds a few billion bits, most of them related to no single URL in particular.
• The k hash functions. k independent hash functions h_1 … h_k, each mapping an element to a bit position in [0, m). In practice these are not k separate functions but two good hashes combined by double hashing (section 2). The choice of k is not free — there is a mathematically optimal value for any given m and expected element count n.
• No stored elements. Because the filter never stores the element itself, its memory footprint is independent of how large each element is. A filter over 1 KB log lines costs exactly as many bits per element as a filter over 8-byte integers. This size-independence is the property that makes bloom filters irreplaceable at scale.

Insert and query — set bits, then test bits.

• Insert(x). Compute the k hash positions for x and set each of those bits to 1 (a bitwise OR). If a bit was already 1 from a previous element, it stays 1 — collisions are expected and harmless on insert.
• Query(x). Compute the same k positions for x. If any of those k bits is 0, x was definitely never inserted — return "definitely not". If all k bits are 1, return "maybe": either x was inserted, or the k bits it maps to were all coincidentally set by other elements (a false positive).
• Why there are no false negatives. Insert only ever turns bits on, and a plain bloom filter never turns them off. So every bit that a genuine member set on insert is still 1 at query time. A genuine member can therefore never produce a 0 bit, which means it can never be reported "definitely not". Absence of deletion is exactly what guarantees absence of false negatives.

Why "probabilistic" is the honest label.

• The false positive. As more elements are inserted, more bits flip to 1. Eventually a never-inserted key can hash to k positions that other elements already lit. The filter reports "maybe" for a key it has never seen — a false positive. The rate is not random noise; it is a precise function of m, n, and k.
• The tunable error. You choose the false positive rate before you build the filter by sizing m for your expected n. A 1% rate costs about 9.6 bits per element; a 0.1% rate costs about 14.4 bits; a 0.01% rate about 19.2. The rate is a design parameter, not an accident.
• The space win. An exact hash set of 100 million 40-byte URLs needs several gigabytes. A bloom filter at 1% false positive rate needs roughly 120 MB — one to two orders of magnitude smaller — because it stores bits about elements, not elements.

What interviewers listen for.

• Do you say "no false negatives, only false positives" in the first two sentences? — required answer.
• Do you name the verdict as "definitely not" vs "maybe" rather than "yes/no"? — senior signal.
• Do you explain that memory is independent of element size? — senior signal.
• Do you note that a plain bloom filter cannot delete or enumerate, and reach for a counting or cuckoo filter when deletion is required? — senior signal.
• Do you frame the false positive rate as a design knob rather than "some small error"? — required answer.

Worked example — hand-simulating insert and query

Detailed explanation. The fastest way to internalise the contract is to run a tiny filter by hand: a 10-bit array, 3 hash functions, and three inserted elements, then probe both a member and a non-member. Because everything is small, you can watch each bit flip and see exactly how a false positive is born.

• Filter shape. m = 10 bits, indices 0…9, k = 3 hash functions.
• Hashes (illustrative). For each element the three functions produce three positions in [0, 10).
• Members inserted. "alice", "bob", "carol".

Question. After inserting the three members, what does the filter answer for "bob" (a member) and for "dave" and "erin" (non-members)?

Input.

Element	h1	h2	h3	Role
alice	1	4	9	insert
bob	4	6	7	insert
carol	0	4	6	insert
dave	2	5	8	query
erin	1	6	7	query

Code.

Start:   index  0 1 2 3 4 5 6 7 8 9
         bits   0 0 0 0 0 0 0 0 0 0

insert alice {1,4,9}:   0 1 0 0 1 0 0 0 0 1
insert bob   {4,6,7}:   0 1 0 0 1 0 1 1 0 1
insert carol {0,4,6}:   1 1 0 0 1 0 1 1 0 1   <- final state

query bob   {4,6,7}: bits[4]=1, bits[6]=1, bits[7]=1  -> ALL set  -> "maybe" (true member)
query dave  {2,5,8}: bits[2]=0                          -> a 0     -> "definitely not"
query erin  {1,6,7}: bits[1]=1, bits[6]=1, bits[7]=1  -> ALL set  -> "maybe" (FALSE POSITIVE)

Step-by-step explanation.

1. The array starts all zero. Inserting "alice" sets bits 1, 4, and 9. Inserting "bob" sets 4 (already on — no change), 6, and 7. Inserting "carol" sets 0, 4 (already on), and 6 (already on). The final state has six bits lit.
2. Querying "bob" checks bits 4, 6, 7 — all 1, so the filter says "maybe". "bob" really is a member, so this is a true positive.
3. Querying "dave" checks bits 2, 5, 8. Bit 2 is 0, so the filter short-circuits to "definitely not" — and indeed "dave" was never inserted. A single 0 is a certificate of absence.
4. Querying "erin" checks bits 1, 6, 7. Bit 1 was set by "alice", bit 6 by "bob"/"carol", bit 7 by "bob". All three are 1, so the filter says "maybe" — but "erin" was never inserted. This is a false positive, produced entirely by other elements' bits coinciding.
5. Notice the query short-circuits: the moment it sees a 0, it can stop and answer "definitely not". Only "maybe" requires checking all k bits.

Output.

Query	Bits checked	Result	Truth
bob	4,6,7 → 1,1,1	maybe	true member
dave	2,5,8 → 0,…	definitely not	correct
erin	1,6,7 → 1,1,1	maybe	false positive

Rule of thumb. A bloom filter query stops at the first 0 and returns "definitely not"; it returns "maybe" only when every one of the k bits is set. False positives are not bugs — they are the designed-in cost of storing bits instead of elements, and their rate is what the sizing math controls.

Worked example — when a bloom filter beats an exact set

Detailed explanation. The decision to use a bloom filter is an economic one: it is worth it when the exact structure does not fit in memory, when a "definitely not" saves a genuinely expensive operation, and when the workload can tolerate a small rate of wasted work on false positives. Walk through the classic "should I hit the backend?" cache scenario.

• The workload. A read-through cache in front of a slow object store. Most requested keys do not exist; each miss costs a 20 ms round-trip to confirm absence.
• The alternative. An exact in-memory hash set of all existing keys — correct, but too large to hold on every edge node.
• The bloom option. A small per-node bloom filter of all existing keys. "Definitely not" answers a miss locally in microseconds; "maybe" falls through to the real lookup.

Question. For 50 million existing keys and a request stream that is 80% non-existent keys, how much backend traffic does a 1% bloom filter remove?

Input.

Parameter	Value
Existing keys (n)	50,000,000
Requests	100,000,000
Fraction non-existent	80% (80,000,000)
Bloom false positive rate	1%
Exact set size (40-byte keys)	~3–4 GB
Bloom size @ 1%	~60 MB

Code.

# Traffic saved by a bloom pre-filter on the miss path
requests            = 100_000_000
nonexistent         = 80_000_000        # truly absent keys
fpr                 = 0.01

# Absent keys the bloom correctly rejects locally (no backend call)
rejected_locally    = nonexistent * (1 - fpr)   # 79,200,000
# Absent keys that slip through as false positives (wasted backend call)
false_positives     = nonexistent * fpr         #    800,000

print(f"absent requests             : {nonexistent:,}")
print(f"rejected locally by bloom   : {int(rejected_locally):,}")
print(f"false positives to backend  : {int(false_positives):,}")
print(f"backend miss-calls removed  : {rejected_locally / nonexistent:.1%}")

Step-by-step explanation.

1. Of the 80 million requests for absent keys, the bloom filter rejects (1 − 0.01) = 99% of them locally — 79.2 million round-trips never happen.
2. The remaining 1% — 800,000 requests — are false positives that fall through to the backend and confirm absence there. That is the wasted work you paid for with the false positive rate.
3. The existing-key requests (20 million) all hit "maybe" and proceed normally; the bloom never blocks a real member because it has no false negatives.
4. The memory trade is stark: the exact set costs 3–4 GB per node, the bloom about 60 MB — roughly 60× smaller — small enough to replicate to every edge node.
5. The net effect is that 79.2 million of 80 million miss round-trips vanish. The filter converted an expensive network confirmation of absence into a local bit test, at the cost of 0.8 million wasted confirmations.

Output.

Metric	Without bloom	With 1% bloom
Backend calls for absent keys	80,000,000	800,000
Per-node memory	3–4 GB (exact set)	~60 MB
Miss round-trips removed	0	79,200,000 (99%)
Wasted calls (false positives)	0	800,000

Rule of thumb. Reach for a bloom filter when a "definitely not" avoids expensive work (disk read, network call, decompression), when the exact set will not fit where you need it, and when the workload can absorb a small false-positive rate of wasted work. If any of those three is false, use an exact hash set instead.

Data structures interview question on the membership contract

A senior interviewer often opens with: "You are designing a service that ingests billions of events and must drop events it has already seen. Someone proposes a bloom filter for dedup. Explain precisely what guarantee a bloom filter gives you, what failure mode you inherit, and whether that failure mode is safe for a dedup use case — then state what you would change if it is not."

Solution Using the one-sided-error contract and its dedup implications

The guarantee
-------------
  query(x) == "definitely not"  =>  x was NEVER inserted   (certain)
  query(x) == "maybe"           =>  x MIGHT have been inserted
                                    (true member OR false positive)

  No false negatives. Possible false positives at rate p.

Applying it to dedup (keep first occurrence, drop repeats)
----------------------------------------------------------
  on event e:
      if e in bloom:            # "maybe"  -> treat as duplicate -> DROP
          drop(e)
      else:                     # "definitely not" -> first sight -> KEEP
          keep(e)
          bloom.add(e)

Failure mode inherited
----------------------
  A false positive => "maybe" for an event we have NOT seen
                   => we DROP a genuinely new event  (DATA LOSS)

  There are no false negatives, so we never KEEP a true duplicate.

Step-by-step trace.

Event	In bloom?	Verdict	Action	Correct?
e1 (new)	no	definitely not	keep + add	yes
e1 (repeat)	yes	maybe	drop	yes
e2 (new)	no	definitely not	keep + add	yes
e3 (new, false positive)	yes	maybe	drop	NO — data loss

1. e1 arrives new: the filter says "definitely not", so we keep it and insert it. Correct.
2. e1 arrives again: the filter says "maybe", we treat it as a duplicate and drop it. Correct — this is exactly the dedup we wanted.
3. e2 arrives new: "definitely not", keep and insert. Correct.
4. e3 arrives new but happens to hash to already-set bits: "maybe". We drop a genuinely new event. This is the inherited failure mode — a false positive in a dedup filter is silent data loss, not a duplicate that slips through.

Output:

Property	Bloom dedup result
Duplicates that slip through	0 (no false negatives)
New events wrongly dropped	~p × (new events) — data loss
Direction of error	drops real data, never keeps duplicates
Safe when	occasional lost event is acceptable (metrics, sampling)
Unsafe when	every event must survive (billing, audit)

Why this works — concept by concept:

• One-sided error — the filter's only mistake is "maybe" for a non-member; it never says "definitely not" for a member. In dedup this means the error direction is dropping new data, never keeping duplicates. You must decide whether that direction is tolerable.
• False positive as data loss — because a "maybe" triggers a drop, every false positive discards a real event. For lossy analytics (approximate counts, sampled telemetry) this is fine; for exactly-once billing it is a correctness bug.
• The safe redesign — if loss is unacceptable, use the bloom only as a cheap pre-filter: on "maybe", confirm against an exact store before dropping. The bloom removes the expensive check for the 99% "definitely not" cases and only the rare "maybe" pays for an exact lookup.
• Cost — O(k) hashing per event and ~9.6·n bits of memory at 1%. The exact-confirm fallback adds one authoritative lookup per false positive, i.e. O(p·n) extra lookups. That is the price of turning lossy dedup into lossless dedup.

DATA STRUCTURES
Topic — data-structures
Probabilistic and set-membership data-structure problems

Practice →

HASHING Topic — hash-table Hash-table and hashing fundamentals

Practice →

---

2. The math — bits, hashes, and false-positive-rate sizing

Bit-fill probability, the false-positive-rate formula, and how to size m and k

The mental model in one line: the false positive rate of a bloom filter is a closed-form function of three numbers — the bit-array size m, the number of inserted elements n, and the number of hash functions k — so you never guess a bloom filter's error, you compute it, and you invert the formula to size m for whatever error your pipeline can tolerate. Every senior bloom-filter conversation lives or dies on whether you can state optimal k = (m/n) ln 2 and "about 9.6 bits per element per 1% error" without reaching for a calculator.

The bit-fill probability — the foundation of every formula.

• One bit staying zero. Each of the k·n bit-sets (n elements × k hashes) picks a position uniformly at random. The probability a specific bit is not chosen by one set is (1 − 1/m); after k·n sets it is (1 − 1/m)^{kn}, which for large m approximates e^{−kn/m}.
• One bit being one. The complement: P(bit = 1) ≈ 1 − e^{−kn/m}. As you insert more elements (n grows) or use more hashes (k grows), more bits flip to 1 and the array saturates.
• The load ratio. The exponent kn/m is the real driver. It is the expected number of bit-sets per bit. Keep it moderate and the array stays sparse; push it high and nearly every bit is 1 and the filter becomes useless.

The false-positive-rate formula.

• The core equation. A false positive happens when all k queried bits are 1 for a non-member. Treating the bits as independent, p ≈ (1 − e^{−kn/m})^k. This is the number you quote and the number you minimise.
• Independence caveat. The bits are not perfectly independent, so the exact rate is very slightly different, but the approximation is excellent for the m sizes used in practice and is the standard interview answer.
• Monotonic in n. For fixed m and k, p only rises as n rises. A bloom filter has a design capacity: exceed the n you sized for and the error climbs past your target.

Optimal k — the number of hashes that minimises error.

• The result. For fixed m and n, p is minimised at k* = (m/n) · ln 2 ≈ 0.693 · (m/n). Fewer hashes leave too many 0 bits testable (higher p for large keys); more hashes saturate the array too fast.
• The error at optimal k. Substituting k* gives p ≈ (1/2)^{k*} = 2^{−k*}, equivalently p ≈ 0.6185^{m/n}. Each additional bit per element multiplies the error by about 0.6185.
• The intuition. At the optimum, exactly half the bits are 1 and half are 0 — the array carries the maximum information per bit, and each hash independently has a 50% chance of hitting a 0 for a non-member.

Sizing — inverting the formula for a target p.

• Bits from a target rate. Solve for m: m = −(n · ln p) / (ln 2)^2. Since (ln 2)^2 ≈ 0.4805, this is m/n ≈ −1.4427 · log2(p) bits per element.
• The numbers to memorise. 1% → ~9.6 bits/elem, k=7; 0.1% → ~14.4 bits/elem, k=10; 0.01% → ~19.2 bits/elem, k=13. Each 10× reduction in error costs about 4.8 more bits per element.
• Then k. With m chosen, set k = round((m/n) · ln 2). Round to the nearest integer; a fractional hash is not a thing.

Double hashing — faking k hashes with two.

• The problem. Computing k independent, strong hashes per element is expensive when k is 7–13.
• Kirsch–Mitzenmacher. Compute two hashes h1(x) and h2(x), then derive the i-th index as g_i(x) = (h1(x) + i · h2(x)) mod m for i = 0 … k−1. This yields asymptotically the same false-positive rate as k independent hashes.
• The practical recipe. Use a single 128-bit hash (e.g. MurmurHash3) and split it into two 64-bit halves for h1 and h2. One hash call, k cheap combinations.

Worked example — computing the false positive rate for a given filter

Detailed explanation. Before sizing, make sure you can evaluate the forward formula: given m, n, k, what error do you actually have? This is the check you run when you inherit someone else's filter and want to know if it is over- or under-provisioned.

• The filter. m = 8,000,000 bits, n = 1,000,000 elements, k = 5 hashes.
• Load ratio. kn/m = 5·1,000,000 / 8,000,000 = 0.625.
• Goal. Compute p and check whether k = 5 is optimal for this m/n.

Question. What is the false positive rate of this filter, and is its k chosen well?

Input.

Parameter	Value
m (bits)	8,000,000
n (elements)	1,000,000
k (hashes)	5
m/n (bits per element)	8

Code.

import math

m, n, k = 8_000_000, 1_000_000, 5

# Probability a given bit is still 0 after n*k sets
p_zero = math.exp(-k * n / m)          # e^{-kn/m}
p_one  = 1 - p_zero

# False positive rate: all k queried bits are 1
fpr = p_one ** k
print(f"P(bit=1)          = {p_one:.4f}")
print(f"false positive p  = {fpr:.4%}")

# Optimal k for this m/n, and the error it would give
k_opt = (m / n) * math.log(2)
fpr_opt = 0.5 ** k_opt
print(f"optimal k         = {k_opt:.2f} (use {round(k_opt)})")
print(f"fpr at optimal k  = {fpr_opt:.4%}")

Step-by-step explanation.

1. The load ratio kn/m = 0.625, so P(bit = 0) = e^{−0.625} ≈ 0.535 and P(bit = 1) ≈ 0.465. Fewer than half the bits are set — the filter is under-hashed for its size.
2. The false positive rate is 0.465^5 ≈ 0.0217, i.e. about 2.17%. That is the real error this filter delivers.
3. The optimal k for m/n = 8 is 8 · ln 2 ≈ 5.55, so k = 6 would be slightly better than k = 5.
4. At the optimal k, the error would be 0.5^{5.55} ≈ 0.0214 — about 2.14%. In this case k = 5 versus k = 6 barely matters because m/n = 8 fundamentally caps the error near 2%.
5. The lesson: with only 8 bits per element you are stuck near a 2% floor no matter how you pick k. To reach 1% you need more bits, not a cleverer k.

Output.

Quantity	Value
P(bit = 1)	0.465
False positive rate (k=5)	2.17%
Optimal k for m/n=8	~6
FPR at optimal k	2.14%
Verdict	error is bits-limited, not k-limited

Rule of thumb. When the false positive rate is too high, first check whether you are bits-limited: if m/n is small, no choice of k will save you. Add bits per element (raise m) to move the error floor, then set k = round((m/n)·ln 2).

Worked example — sizing a filter for a target false positive rate

Detailed explanation. The common task is the inverse: you know how many elements you expect and the error you can tolerate, and you must produce m and k. Do this for a URL-dedup filter at three target rates so you can feel the bits-per-element cost curve.

• Expected elements. n = 10,000,000 distinct URLs.
• Targets. 1%, 0.1%, 0.01%.
• Deliverable. m in bits and megabytes, plus k, for each target.

Question. Size the bit array and choose k for n = 10M at each of the three target rates.

Input.

Target p	−ln p	m/n = −ln p / (ln 2)^2
0.01	4.605	9.585
0.001	6.908	14.378
0.0001	9.210	19.170

Code.

import math

def size_bloom(n: int, p: float) -> tuple[int, int]:
    """Return (m_bits, k) for n elements at target false positive rate p."""
    m = math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))
    k = max(1, round((m / n) * math.log(2)))
    return m, k

for p in (0.01, 0.001, 0.0001):
    m, k = size_bloom(10_000_000, p)
    print(f"p={p:<7} m={m:>12,} bits  ({m/8/1e6:6.1f} MB)  k={k}")

# p=0.01    m=  95,850,584 bits  (  12.0 MB)  k=7
# p=0.001   m= 143,775,876 bits  (  18.0 MB)  k=10
# p=0.0001  m= 191,701,168 bits  (  24.0 MB)  k=13

Step-by-step explanation.

1. For 1%, m/n ≈ 9.585, so m ≈ 95.85M bits ≈ 12.0 MB, and k = round(9.585 · ln 2) = round(6.64) = 7.
2. For 0.1%, m/n ≈ 14.378, so m ≈ 143.8M bits ≈ 18.0 MB, and k = round(9.96) = 10.
3. For 0.01%, m/n ≈ 19.17, so m ≈ 191.7M bits ≈ 24.0 MB, and k = round(13.29) = 13.
4. Every 10× tightening of the error adds a flat ~4.8 bits per element (~6 MB here) and ~3 more hashes. The cost is linear in the number of nines you want, not exponential — going from 1% to 0.0001% only doubles the memory.
5. Crucially, none of these depend on how long the URLs are. Whether the URLs average 40 or 400 bytes, the filter is 12/18/24 MB. That is the size-independence property paying off.

Output.

Target p	m (bits)	Size	k
1%	95,850,584	12.0 MB	7
0.1%	143,775,876	18.0 MB	10
0.01%	191,701,168	24.0 MB	13

Rule of thumb. Memorise "~9.6 bits per element per 1%, plus ~4.8 bits for each extra 10×", and you can size any bloom filter in your head. Always size m for the maximum n you expect — a bloom filter sized for too few elements silently exceeds its target error as it fills.

Worked example — double hashing to avoid k separate hash calls

Detailed explanation. Computing 10 independent hashes per element would dominate the CPU cost of a hot dedup loop. The Kirsch–Mitzenmacher double-hashing trick computes one strong hash and derives all k indices from it, with no measurable loss in false-positive rate.

• One 128-bit hash. Split into two 64-bit lanes h1, h2.
• Derive k indices. g_i = (h1 + i·h2) mod m.
• Guard. Ensure h2 is odd/non-zero relative to m so the sequence does not collapse to a single index.

Question. Implement the k index generator using double hashing from a single MurmurHash3 128-bit digest.

Input.

Component	Value
Base hash	mmh3.hash128 (128-bit)
Lanes	h1 = high 64 bits, h2 = low 64 bits
Derivation	g_i = (h1 + i·h2) mod m
k	7

Code.

import mmh3   # pip install mmh3 (MurmurHash3)

def bloom_indexes(item: str, m: int, k: int):
    """Yield k bit positions in [0, m) using Kirsch-Mitzenmacher double hashing."""
    digest = mmh3.hash128(item, signed=False)   # 128-bit
    h1 = digest & 0xFFFFFFFFFFFFFFFF            # low 64 bits
    h2 = digest >> 64                           # high 64 bits
    if h2 == 0:
        h2 = 1                                  # avoid a degenerate constant sequence
    for i in range(k):
        yield (h1 + i * h2) % m

print(list(bloom_indexes("alice", m=97, k=7)))
# e.g. [12, 45, 78, 14, 47, 80, 16]  (positions in [0, 97))

Step-by-step explanation.

1. A single mmh3.hash128 call produces 128 bits of well-distributed hash. Splitting it gives two 64-bit values that behave like two independent hash functions.
2. The generator produces g_0 = h1, g_1 = h1 + h2, g_2 = h1 + 2·h2, and so on, each reduced modulo m. Seven cheap additions replace seven full hash computations.
3. The if h2 == 0 guard prevents the pathological case where every g_i collapses to h1 — which would turn the k-hash filter into a 1-hash filter and wreck the error rate.
4. Because h1 and h2 are effectively independent, the derived indices are close enough to independent that the false-positive rate matches the k-independent-hash formula to within noise.
5. The same digest is reused for insert and query, so both paths cost exactly one hash call plus k modular additions — the double-hashing recipe is what makes bloom filters cheap enough for per-event use.

Output.

Metric	k independent hashes	Double hashing
Hash computations per op	k (e.g. 7)	1
Extra work per op	—	k additions + mods
False-positive rate	baseline	matches baseline
Typical speedup	1×	~5–10× on the hash step

Rule of thumb. Never compute k independent hashes in a production bloom filter. Take one 128-bit MurmurHash, split it into two 64-bit lanes, and derive all k indices with h1 + i·h2 mod m. It is the standard implementation in every serious library.

Optimization interview question on false-positive-rate sizing

A senior interviewer might ask: "You need a bloom filter for 100 million keys with at most a 0.1% false positive rate, and it must fit in under 256 MB of RAM. Show me the sizing math — bit-array size, bits per element, the number of hash functions — confirm it fits the memory budget, and explain what happens to the error if the key count grows to 150 million without a rebuild."

Solution Using the closed-form sizing formulas and a capacity-overrun analysis

import math

n_design = 100_000_000     # keys we size for
p_target = 0.001           # 0.1% target FPR
budget_bytes = 256 * 1024 * 1024

# 1. Size m and k for the design point
m = math.ceil(-(n_design * math.log(p_target)) / (math.log(2) ** 2))
k = max(1, round((m / n_design) * math.log(2)))
size_mb = m / 8 / 1e6
print(f"m = {m:,} bits = {size_mb:.1f} MB,  k = {k},  fits budget: {m/8 < budget_bytes}")

# 2. What the SAME filter's FPR becomes if n grows to 150M without a rebuild
def fpr(m, n, k):
    return (1 - math.exp(-k * n / m)) ** k

for n_actual in (100_000_000, 125_000_000, 150_000_000):
    print(f"n={n_actual:,}  ->  fpr={fpr(m, n_actual, k):.3%}")

Step-by-step trace.

Step	Computation	Value
bits per element	−ln(0.001)/(ln 2)^2	14.378
m	100M × 14.378	~1.4378 × 10^9 bits
m in MB	m / 8 / 1e6	~179.7 MB
budget check	179.7 MB < 256 MB	fits
k	round(14.378 × ln 2)	10

1. Bits per element for 0.1% is −ln(0.001)/(ln 2)^2 ≈ 14.378.
2. Multiplying by the design count gives m ≈ 1.4378 × 10^9 bits, which is ≈ 179.7 MB — comfortably under the 256 MB budget.
3. The optimal k is round(14.378 · ln 2) = round(9.966) = 10 hash functions.
4. At the design point (n = 100M), the achieved error is the target 0.1%.
5. Overrun analysis: keeping m and k fixed but pushing n to 125M raises the error to about 0.28%, and at 150M to about 0.64% — the load ratio kn/m climbed, so more bits are set and the error grew super-linearly past the design capacity.

Output:

Actual n	Load kn/m	False positive rate
100,000,000 (design)	~0.693	~0.10%
125,000,000	~0.867	~0.28%
150,000,000	~1.040	~0.64%

Why this works — concept by concept:

• Bits-per-element formula — m/n = −ln p / (ln 2)^2 turns a target error directly into a bit budget. For 0.1% that is ~14.4 bits, so 100M keys need ~180 MB regardless of key length.
• Optimal k — k = (m/n)·ln 2 ≈ 10 puts the array at the 50%-full sweet spot where each hash has an independent coin-flip chance of hitting a 0 for a non-member, minimising the error for that m.
• Capacity is real — the sizing holds only at the design n. Because p = (1 − e^{−kn/m})^k rises with n, overrunning the count degrades the error fast: 1.5× the keys turned 0.1% into 0.64%, over 6× worse.
• The fix for growth — if n may grow, either size m for the maximum expected count up front, or use a scalable bloom filter (section 3) that adds capacity while bounding the compounded error.
• Cost — O(k) hashing per operation (10 modular additions via double hashing) and O(m) = ~180 MB of memory. The exact set of 100M 40-byte keys would cost several gigabytes, so the bloom is ~20× smaller at 0.1% error.

HASHING
Topic — hash-table
Hashing and hash-function distribution problems

Practice →

OPTIMIZATION Topic — optimization Space–time trade-off and sizing problems

Practice →

---

3. Variants — counting and scalable bloom filters

Deletion via counters, unbounded growth via a stack of filters, and the cuckoo alternative

The mental model in one line: the plain bloom filter's two hard limitations — it cannot delete and it has a fixed capacity — are each solved by a named variant: the counting bloom filter replaces every bit with a small counter so elements can be removed by decrementing, and the scalable bloom filter chains a geometric series of ordinary filters with tightening error targets so the set can grow without ever breaching a bounded compounded false positive rate. Knowing which variant answers which limitation, and what each costs, is the difference between "I'd use a bloom filter" and a defensible design.

Why a plain bloom cannot delete.

• Shared bits. A single 1 bit may have been set by many elements. Clearing the k bits of one element to delete it would also clear bits that other elements rely on — instantly creating false negatives, which violates the core contract.
• The consequence. A plain bloom filter is append-only. Its error rises monotonically with inserts and it can never shrink. For any workload with churn (a sliding window, an expiring cache, a "seen in the last hour" set) you need deletion, which means a different variant.

Counting bloom filters — bits become small counters.

• The structure. Replace each bit with a c-bit counter (commonly 4 bits). Insert increments the k counters; delete decrements them; query tests whether all k counters are non-zero.
• The space cost. A 4-bit counter is 4× the memory of a single bit, so a counting bloom filter costs roughly 4× a plain one for the same m. That is the price of deletion.
• Counter overflow. A 4-bit counter saturates at 15. If a position is set more than 15 times, it must stick at 15 (saturating arithmetic) — decrementing a saturated counter would risk a false negative, so saturated counters are conventionally frozen. Choose c so overflow is astronomically unlikely: at optimal k, counters are Poisson-distributed with mean ln 2 ≈ 0.69, and 4 bits gives overflow odds around 10^{−15} per counter.
• Delete safety. Only delete elements you know were inserted. Decrementing counters for a never-inserted element corrupts the filter and can create false negatives for real members.

Scalable bloom filters — a geometric stack.

• The idea. Maintain a list of ordinary bloom filters. Insert always goes into the newest (active) filter. When the active filter reaches its capacity (its slice fills to the target error), freeze it and append a new, larger filter with a tighter target error. Query checks every filter and returns "maybe" if any says "maybe".
• Bounding the compounded error. If filter i targets p_0 · r^i for a ratio r ∈ (0,1) (commonly 0.8–0.9), the overall error across the stack is bounded by p_0 / (1 − r) — a finite number no matter how many filters accumulate. Tightening each successive filter is what keeps the sum convergent.
• The growth factor. Each new filter is sized larger than the last (a growth factor s, often 2), so the number of filters grows only logarithmically with the total element count. Query cost is O(number of filters) hash-and-test passes — small because the count is logarithmic.

The cuckoo filter — the modern alternative.

• What it is. A cuckoo filter stores a short fingerprint of each element in a cuckoo hash table with two candidate buckets per element. It supports deletion natively (remove the fingerprint), and for target error rates below about 3% it is more space-efficient than a bloom filter.
• Why it is often preferred. Lookups touch only two buckets (two cache lines), giving better locality than a bloom filter's k scattered bit probes; and deletion is exact rather than requiring 4× counters.
• The trade-off. Inserts can fail when buckets are full (requiring a resize), and the space advantage reverses at very high error rates. For churny, latency-sensitive membership sets, cuckoo filters are the current default; bloom filters remain simplest for append-only sets.

Worked example — deleting from a counting bloom filter

Detailed explanation. Build a tiny counting bloom filter, insert two elements that share a bit position, delete one, and confirm the other still tests present — the exact scenario a plain bloom filter cannot handle without breaking.

• Structure. m = 8 counters, k = 2 hashes.
• Elements. "x" → positions {1, 4}; "y" → positions {4, 6}. They collide at position 4.
• Operation. Insert both, then delete "x", then query "y".

Question. After deleting "x", does "y" still test present, and what does the shared counter at position 4 look like?

Input.

Op	Element	Positions	Counter effect
add	x	1, 4	+1 each
add	y	4, 6	+1 each
del	x	1, 4	−1 each
query	y	4, 6	test > 0

Code.

class CountingBloom:
    def __init__(self, m, k, hashfn):
        self.counts = [0] * m
        self.m, self.k, self.hashfn = m, k, hashfn

    def _pos(self, item):
        return self.hashfn(item, self.m, self.k)

    def add(self, item):
        for i in self._pos(item):
            if self.counts[i] < 15:          # saturating 4-bit counter
                self.counts[i] += 1

    def delete(self, item):
        for i in self._pos(item):
            if 0 < self.counts[i] < 15:       # never touch a saturated counter
                self.counts[i] -= 1

    def __contains__(self, item):
        return all(self.counts[i] > 0 for i in self._pos(item))

# positions: x -> {1,4}, y -> {4,6}
cb = CountingBloom(8, 2, lambda it, m, k: {"x": [1, 4], "y": [4, 6]}[it])
cb.add("x"); cb.add("y")
print(cb.counts)          # [0,1,0,0,2,0,1,0]  position 4 shared -> 2
cb.delete("x")
print(cb.counts)          # [0,0,0,0,1,0,1,0]  position 4 still 1
print("y" in cb)          # True  -> y survives x's deletion

Step-by-step explanation.

1. Inserting "x" increments counters 1 and 4; inserting "y" increments 4 and 6. Position 4 is shared, so its counter reaches 2 — it records that two elements depend on it.
2. Deleting "x" decrements counters 1 and 4. Counter 1 drops to 0 (no one else needs it), counter 4 drops to 1 (still needed by "y").
3. Querying "y" tests counters 4 and 6: both are > 0, so "y" still tests present. The deletion of "x" did not create a false negative for "y".
4. This is exactly what a plain bloom filter cannot do: clearing bit 4 to delete "x" would have wiped a bit "y" needs. The counter records how many elements share the position, so decrement-to-zero happens only when the last dependent is removed.
5. The saturating guards (< 15 on add, 0 < c < 15 on delete) protect against overflow corruption: once a counter hits its max it is frozen, because a decremented-from-saturation counter could under-count and eventually false-negative.

Output.

Stage	counts array	"y" present?
after add x, y	[0,1,0,0,2,0,1,0]	yes
after delete x	[0,0,0,0,1,0,1,0]	yes
shared counter (pos 4)	2 → 1	still protects y

Rule of thumb. Use a counting bloom filter only when you genuinely need deletes; it costs ~4× the memory of a plain filter. Always saturate counters at their max and never delete an element you did not provably insert — both mistakes silently reintroduce false negatives.

Worked example — bounding error with a scalable bloom filter

Detailed explanation. Show how a scalable bloom filter keeps a bounded compounded error as the element count blows past any single filter's capacity, by chaining filters with a tightening ratio.

• Ratio. r = 0.9 (each new filter targets 0.9× the previous filter's error).
• Base error. p_0 = 0.01 for the first filter.
• Bound. Compounded error ≤ p_0 / (1 − r).

Question. With p_0 = 0.01 and r = 0.9, what is the guaranteed upper bound on the overall false positive rate, and what error does each of the first four filters target?

Input.

Filter i	Target error p_0·r^i
0	0.01
1	0.009
2	0.0081
3	0.00729

Code.

p0, r = 0.01, 0.9

# Per-filter target errors (each new filter is tighter)
targets = [p0 * r**i for i in range(4)]
print([f"{t:.5f}" for t in targets])   # ['0.01000','0.00900','0.00810','0.00729']

# Overall error is bounded by the sum of a geometric series: p0 / (1 - r)
bound = p0 / (1 - r)
print(f"compounded FPR bound = {bound:.3%}")   # 10.000%

# Tighter ratios give tighter overall bounds
for r_try in (0.5, 0.8, 0.9):
    print(f"r={r_try}  ->  bound = {p0/(1-r_try):.2%}")

Step-by-step explanation.

1. The active filter starts at p_0 = 0.01. When it fills, the next filter targets 0.01 · 0.9 = 0.009, the next 0.0081, and so on — each successive filter is stricter, so it contributes less error.
2. A query returns "maybe" if any filter says "maybe", so the overall error is at most the sum of the per-filter errors: p_0 · (1 + r + r^2 + …) = p_0 / (1 − r).
3. With r = 0.9, that bound is 0.01 / 0.1 = 0.10, i.e. the overall error never exceeds 10% no matter how many filters accumulate. The tightening series is what makes the infinite sum converge.
4. A smaller r gives a tighter bound (r = 0.5 → 2% bound) but forces each new filter to be much stricter and therefore larger; r closer to 1 saves memory but loosens the bound. r = 0.8–0.9 is the common compromise.
5. The number of filters grows logarithmically with total elements (because each is larger than the last by a growth factor), so query cost stays small — a handful of hash-and-test passes even for billions of elements.

Output.

Ratio r	Compounded FPR bound
0.5	2.00%
0.8	5.00%
0.9	10.00%

Rule of thumb. Use a scalable bloom filter when you cannot predict the final element count. Pick p_0 and r so that p_0/(1−r) is your acceptable ceiling; a tighter r costs more memory per growth step but guarantees a lower overall error.

Data engineering interview question on adding deletes to a dedup filter

A senior interviewer might ask: "Your streaming pipeline uses a plain bloom filter to dedup events over a rolling 24-hour window, but events older than 24 hours must be forgotten so their keys can recur. The plain filter never forgets and its error keeps climbing. Redesign the filter to support expiry, and justify the memory and correctness trade-offs of your choice."

Solution Using time-partitioned counting or rotating bloom filters

# Approach: a ring of per-hour bloom filters (rotating window).
# Each hour gets its own plain bloom; membership = OR across the last 24;
# expiry = drop the oldest filter. No counters needed, no delete corruption.

from collections import deque

class RotatingBloomWindow:
    def __init__(self, hours, make_bloom):
        self.hours = hours
        self.ring = deque(maxlen=hours)      # newest at right
        self.make_bloom = make_bloom
        self.ring.append(make_bloom())

    def rotate(self):                        # call once per hour
        self.ring.append(self.make_bloom())  # maxlen drops the oldest automatically

    def add(self, key):
        self.ring[-1].add(key)               # always write to the current hour

    def __contains__(self, key):
        return any(key in b for b in self.ring)   # seen in ANY of the last N hours

Step-by-step trace.

Hour	Action	Ring contents (oldest→newest)	"k1" seen?
00:00	add k1	[B0{k1}]	yes
01:00	rotate; add k2	[B0{k1}, B1{k2}]	yes
…	… 22 more rotations …	24 filters	yes
24:00	rotate (drops B0)	[B1{k2} … B24{}]	no (expired)

1. Each hour owns a plain bloom filter; add always targets the newest one, so writes are cheap and never corrupt older filters.
2. Membership is an OR across all filters in the ring: a key seen in any of the last 24 hours tests "maybe". This is the dedup window.
3. rotate() runs hourly, appending a fresh empty filter. Because the ring is a deque(maxlen=24), appending the 25th filter automatically evicts the oldest — that is the expiry.
4. After 24 rotations, the hour-0 filter (holding k1) falls out of the ring, so k1 now tests "definitely not" and its key can recur. Expiry happened by dropping a whole filter, not by deleting individual bits.
5. No counting counters are needed: because expiry drops an entire independent filter, there is never a shared-bit deletion, so no false negatives are introduced within any single filter's lifetime.

Output:

Design	Deletes?	Memory	False-negative risk
Plain bloom (no expiry)	no	1×	none, but error grows forever
Counting bloom + per-key TTL	yes	~4×	if you delete un-inserted keys
Rotating ring of 24 plain blooms	window expiry	~24× small filters	none

Why this works — concept by concept:

• Rotating window — partitioning by time turns "delete old keys" into "drop the oldest filter", which is O(1) and cannot corrupt shared bits. Each filter is independent, so eviction is safe.
• OR across the ring — a key is a duplicate if seen in any live hour; the union of the filters is itself a valid bloom-style membership test with a bounded combined error (sum of per-filter errors).
• Sized per hour — each hourly filter is sized for one hour of distinct keys, so total memory is 24 × (hourly size), and you never over-provision one giant filter for a full day.
• Counting bloom alternative — a single counting bloom with per-key TTL also works but costs ~4× and risks corruption if a key is decremented that was never added; the rotating ring avoids both by never deleting individual keys.
• Cost — O(k) per add, O(24·k) per query (24 hash-and-test passes), and O(24 × hourly m) memory. The query fan-out is the price of safe, exact windowed expiry.

DATA STRUCTURES
Topic — data-structures
Counting, scalable, and windowed structure problems

Practice →

HASHING Topic — hash-table Fingerprint and cuckoo-hashing problems

Practice →

---

4. Bloom filters in databases — LSM and SSTable

The bloom filter that skips a disk read — how LSM engines avoid touching SSTables that cannot hold the key

The mental model in one line: an LSM bloom filter is a per-SSTable membership test that a log-structured-merge storage engine consults before reading a file from disk — if the filter says "definitely not", the engine skips that SSTable's random I/O entirely, and since a point lookup may have to check many SSTables across many levels, this single optimisation is what makes LSM key-value stores like RocksDB, Cassandra, and HBase read-efficient for keys that are absent or rare. This is the highest-leverage real-world use of bloom filters, and interviewers love it because it ties the abstract "definitely not" verdict to a concrete, expensive disk seek.

Why LSM point lookups are expensive.

• The LSM shape. An LSM engine buffers writes in an in-memory memtable and periodically flushes them to immutable, sorted files called SSTables. Over time SSTables accumulate across levels (L0, L1, …), each level larger than the last, and compaction merges them.
• The read fan-out. A GET key cannot know which SSTable holds the key (or whether any does). Without help, it must binary-search every candidate SSTable from newest to oldest until it finds the key or exhausts them all. Each SSTable check that misses is a wasted disk read — the essence of read amplification.
• The worst case — absent keys. A lookup for a key that does not exist must, in the naive design, read every level's candidate SSTable to prove absence. Absent-key lookups are common (existence checks, upserts, cache-miss confirmations), so this is not a rare path.

How the bloom filter fixes it.

• One filter per SSTable. When an SSTable is written, the engine builds a bloom filter over all the keys in that file and stores it (usually in a metadata block, cached in memory).
• Check before you read. On GET key, for each candidate SSTable the engine first tests the key against that SSTable's bloom filter. "Definitely not" → skip the file, no disk read. "Maybe" → read the file (and possibly find the key, or discover the false positive).
• The payoff. For an absent key, most SSTables answer "definitely not" and are skipped; only the ~p fraction that false-positive incur a disk read. Read amplification for absent keys drops from "read every level" to "read almost nothing".

RocksDB knobs every data engineer should know.

• bits_per_key. The bloom filter's bits per element, set via the block-based table's filter policy (e.g. NewBloomFilterPolicy(10)). 10 bits ≈ 1% false positive rate is the common default; raise it to cut read amplification further at the cost of memory.
• Whole-key vs prefix. whole_key_filtering builds the filter over full keys for point lookups. A prefix bloom (via a prefix_extractor) builds it over key prefixes so range scans with a common prefix can also be pruned.
• Full vs partitioned filters. A full filter is one bloom per SSTable, loaded whole. A partitioned filter splits the bloom into blocks with a top-level index, so only the relevant block is paged into memory — important when the total filter set is too large to pin in RAM. Newer engines also offer a Ribbon filter, a more space-efficient successor to the classic bloom at the same error rate.

Beyond LSM — bloom filters across the data stack.

• Join pruning / runtime filters. In Spark, Impala, and cloud warehouses, the engine can build a bloom filter over the join keys of the smaller (build) side and broadcast it to pre-filter the larger (probe) side, discarding rows that cannot match before the shuffle. This is the "bloom filter join" or "runtime filter" optimisation.
• Partition and file pruning. Query engines keep bloom filters (or the related min/max and dictionary stats) per data file (Parquet/ORC) so a predicate can skip whole files that cannot contain a value.
• Deduplication and one-hit-wonder caches. CDNs use a bloom filter to avoid caching objects requested only once ("admit to cache only on the second request"), and ingestion pipelines use them to drop already-seen records cheaply.

Worked example — read amplification with and without a bloom filter

Detailed explanation. Quantify the disk reads an absent-key lookup costs in an LSM tree with and without per-SSTable bloom filters, to see why the optimisation is not optional at scale.

• Tree shape. 7 candidate SSTables must be checked for a point lookup.
• Key status. The key is absent (the common existence-check path).
• Filter error. 1% per SSTable bloom.

Question. For 1,000,000 lookups of absent keys against 7 SSTables, how many disk reads happen with and without bloom filters?

Input.

Parameter	Value
SSTables checked per lookup	7
Lookups (all absent keys)	1,000,000
Bloom FPR per SSTable	1%
Disk read cost	~1 random seek each

Code.

sstables_per_lookup = 7
lookups             = 1_000_000
fpr                 = 0.01

# Without bloom: every candidate SSTable is read to prove absence
reads_without = lookups * sstables_per_lookup

# With bloom: only false-positive SSTables are read (expected fpr each)
reads_with = lookups * sstables_per_lookup * fpr

print(f"disk reads without bloom : {reads_without:,}")   # 7,000,000
print(f"disk reads with bloom    : {int(reads_with):,}") #    70,000
print(f"read amplification cut    : {1 - reads_with/reads_without:.1%}")  # 99.0%

Step-by-step explanation.

1. Without bloom filters, proving an absent key is truly absent requires reading all 7 candidate SSTables — 7 million disk seeks for a million lookups.
2. With a 1% bloom per SSTable, each SSTable answers "definitely not" 99% of the time and is skipped. Only the 1% false-positive cases trigger a real read.
3. The expected reads are 1,000,000 × 7 × 0.01 = 70,000 — a 100× reduction, from 7 million seeks to 70 thousand.
4. The false-positive reads are not errors in the result (the SSTable is read, the key is confirmed absent, the lookup returns "not found" correctly) — they are just wasted I/O, and their volume is exactly the false-positive rate.
5. This is why every production LSM engine ships bloom filters on by default: absent-key and rare-key lookups dominate many workloads, and the disk-seek savings are enormous.

Output.

Metric	Without bloom	With 1% bloom
Disk reads (1M absent lookups)	7,000,000	70,000
Reduction	—	99.0%
Extra CPU	none	k hashes per SSTable check
Memory for filters	none	~10 bits/key per SSTable

Rule of thumb. For LSM point-lookup workloads with many absent or rare keys, per-SSTable bloom filters cut disk reads by roughly (1 − fpr) per skipped file. The memory (~10 bits/key at 1%) is almost always worth it; only disable blooms for scan-only workloads where point lookups never happen.

Worked example — configuring and tightening a RocksDB bloom filter

Detailed explanation. Show the RocksDB configuration surface for bloom filters and how raising bits_per_key trades memory for fewer false-positive disk reads.

• Filter policy. NewBloomFilterPolicy(bits_per_key).
• Placement. In the block-based table options.
• Tightening. Move from 10 to 16 bits/key to cut the false-positive read rate.

Question. How does raising RocksDB's bits_per_key from 10 to 16 change the false-positive rate and the filter memory for a 100-million-key column family?

Input.

Parameter	10 bits/key	16 bits/key
Keys	100,000,000	100,000,000
Approx FPR	~1%	~0.05%
Filter memory	~125 MB	~200 MB

Code.

// RocksDB (C++) — attach a bloom filter policy to the table format
#include "rocksdb/table.h"
#include "rocksdb/filter_policy.h"

rocksdb::BlockBasedTableOptions table_opts;
table_opts.filter_policy.reset(
    rocksdb::NewBloomFilterPolicy(16 /* bits_per_key */));
table_opts.whole_key_filtering   = true;   // point-lookup filter over full keys
table_opts.partition_filters     = true;   // page filter blocks on demand
table_opts.cache_index_and_filter_blocks = true;

rocksdb::Options options;
options.table_factory.reset(
    rocksdb::NewBlockBasedTableFactory(table_opts));

import math
# The FPR that bits_per_key implies, at the engine's optimal k
def fpr_for_bits(bits_per_key: float) -> float:
    k = bits_per_key * math.log(2)          # optimal k
    return 0.5 ** k                         # ~ 0.5^k at optimal k

for b in (10, 16):
    print(f"bits_per_key={b}  ->  FPR ≈ {fpr_for_bits(b):.3%}")
# bits_per_key=10  ->  FPR ≈ 0.819%
# bits_per_key=16  ->  FPR ≈ 0.216%

Step-by-step explanation.

1. NewBloomFilterPolicy(16) tells RocksDB to build each SSTable's bloom with 16 bits per key instead of the default 10. RocksDB internally chooses the optimal number of hash probes.
2. At 10 bits/key the implied false-positive rate is roughly 0.8–1%; at 16 bits/key it drops to about 0.2% — a ~4× reduction in wasted disk reads on absent keys.
3. The cost is memory: filter size scales linearly with bits_per_key, so 100M keys go from ~125 MB to ~200 MB of filter data (which you want cached in RAM to avoid reading the filter from disk).
4. partition_filters = true splits the filter so only the needed block is loaded, keeping RAM pressure manageable when the total filter set is large; cache_index_and_filter_blocks pins them in the block cache.
5. whole_key_filtering = true builds the filter for full-key point lookups; if your workload is prefix-scan heavy you would instead configure a prefix_extractor and a prefix bloom.

Output.

bits_per_key	Approx FPR	Filter memory (100M keys)	Extra absent-read reduction
10 (default)	~0.8%	~125 MB	baseline
16	~0.2%	~200 MB	~4× fewer FP reads

Rule of thumb. Tune RocksDB bits_per_key upward only if bloom false positives (visible as bloom_useful / bloom_full_positive stats) are causing measurable read I/O; otherwise the default 10 (~1%) is the right memory/read balance. Always cache index and filter blocks so the bloom check itself never hits disk.

Systems interview question on cutting read amplification

A senior interviewer might ask: "Your RocksDB-backed key-value service has high read latency dominated by disk seeks, and profiling shows most GETs are for keys that do not exist (an existence-check workload). Walk me through why this is slow, how bloom filters fix it, how you would configure them, and how you would verify the fix from the engine's statistics."

Solution Using per-SSTable bloom filters with verified statistics

Diagnosis
---------
  existence-check GET for an ABSENT key must, without blooms, read one
  candidate SSTable per level to prove absence  ->  N random disk seeks
  per lookup, where N = number of levels/SSTables checked.

Fix
---
  1. Enable a bloom filter policy per SSTable (bits_per_key = 10, ~1% FPR).
  2. Cache index + filter blocks so the bloom check never reads disk.
  3. On GET: test the key against each SSTable's bloom FIRST.
        "definitely not" -> skip the file (0 disk seeks)
        "maybe"          -> read the file (found, or a false positive)

Verify from RocksDB statistics
------------------------------
  bloom_filter_useful          -> count of SSTable reads AVOIDED by a bloom
  bloom_filter_full_positive   -> "maybe" verdicts that led to a read
  false-positive ratio ≈ full_true_positive vs full_positive
  read latency p99             -> should drop sharply for absent keys

Step-by-step trace.

GET (absent key)	SSTables	Blooms say	Disk reads
before fix	6 checked	n/a	6
after fix (typical)	6 checked	6× "definitely not"	0
after fix (false positive)	6 checked	5× not, 1× "maybe"	1

1. Before the fix, an absent-key GET reads all 6 candidate SSTables to prove the key is nowhere — 6 disk seeks per lookup, dominating latency.
2. After enabling bloom filters, each SSTable is bloom-tested first. For a truly absent key, all 6 blooms usually say "definitely not", so zero disk reads happen.
3. The occasional false positive (≈1% per SSTable) causes a single wasted read, confirmed absent in that file; the lookup result is still correct.
4. bloom_filter_useful counts every avoided SSTable read — it should climb to roughly 6 × lookups × (1 − fpr), quantifying the benefit directly from the engine.
5. p99 read latency for the existence-check workload collapses because the common path went from 6 seeks to 0; only the rare false-positive path pays for I/O.

Output:

Metric	Before blooms	After blooms
Disk seeks per absent GET	~6	~0 (≈0.06 with 1% FP over 6 files)
Dominant cost	random disk I/O	in-memory bloom checks
p99 read latency	high	sharply lower
Verification signal	—	bloom_filter_useful rising

Why this works — concept by concept:

• Per-SSTable bloom — each file carries a membership test over its own keys, so a "definitely not" is a certificate that the key is not in that file — no need to read it. Absence proofs become memory operations, not disk seeks.
• Cached filter blocks — pinning index and filter blocks in the block cache ensures the bloom check itself never causes I/O; otherwise you would trade a data seek for a filter seek.
• False positives cost I/O, not correctness — a "maybe" that turns out wrong causes one wasted read but never a wrong answer, because the SSTable read authoritatively confirms presence or absence.
• Statistics close the loop — bloom_filter_useful and the full-positive counters let you prove the optimisation is working and tune bits_per_key against real false-positive read volume rather than guessing.
• Cost — O(levels × k) in-memory hash checks per GET plus ~10 bits/key of cached filter memory, in exchange for eliminating O(levels) random disk seeks per absent lookup. On disk-bound workloads that is a 10–100× latency win.

DATA STRUCTURES
Topic — data-structures
Storage-engine and index structure problems

Practice →

OPTIMIZATION Topic — optimization Read-amplification and I/O reduction problems

Practice →

---

5. Building and tuning one in Python

A production-shaped BloomFilter class, sizing helpers, and measuring observed versus predicted error

The mental model in one line: a production-quality bloom filter in Python is about sixty lines — a bit array backed by a bytearray, hash functions reduced to one MurmurHash split by double hashing, and two sizing helpers that turn (n, target p) into (m, k) — and the discipline that separates a toy from a tool is measuring the observed false positive rate against the predicted one after you build it, because a mis-sized filter or a bad hash silently drifts off target. Everything in the earlier sections comes together here as runnable code you can drop into a dedup or pre-filter stage.

The building blocks.

• The bit array. A bytearray(ceil(m/8)) gives m addressable bits; set bit i with arr[i >> 3] |= (1 << (i & 7)) and test it with arr[i >> 3] & (1 << (i & 7)). For serious workloads the bitarray library is faster, but bytearray has zero dependencies.
• The hashing. One mmh3.hash128 call split into two 64-bit lanes, combined by double hashing to yield k positions. Reuse the same digest for insert and query so both cost one hash call.
• The parameters. Store m, k, and the design n on the object so you can compute expected error, detect saturation, and serialise the filter with its shape.

The sizing helpers.

• optimal_m(n, p). ceil(−n·ln p / (ln 2)^2) — bits for n elements at target error p.
• optimal_k(m, n). max(1, round((m/n)·ln 2)) — the error-minimising hash count.
• Design for the max. Always pass the maximum expected n; a filter sized for too few elements exceeds its target error as it fills.

Tuning and verification.

• Predict then measure. Compute the expected error from (m, n, k), then insert n known elements and query a large batch of known non-members, counting how many come back "maybe". Observed and predicted should agree within noise.
• Watch saturation. Track the fraction of set bits; at the design point it should be ~50%. Much higher means you have overrun n and the error is above target.
• Resize by rebuild. A plain bloom cannot grow in place. When load approaches n, allocate a larger filter and re-insert (from source data, or from a scalable-filter chain). Union/intersection are only valid between filters with identical m and k.

Operational notes.

• Serialisation. Persist m, k, n, and the raw bytearray bytes. On load, reconstruct with the same parameters — a filter is meaningless without its shape.
• Union of filters. Two filters with the same m and k can be OR-ed bit-for-bit to get a filter of the union of their sets — useful for merging per-partition filters in a distributed job.
• Thread safety. Inserts are bit-OR, which is idempotent and order-independent, but concurrent writers still need synchronisation on the underlying bytes in CPython for correctness of the read-modify-write on each byte.

Worked example — a minimal but correct BloomFilter class

Detailed explanation. Assemble the full class: constructor sizes m and k from (n, p), add sets bits via double hashing, the in membership test checks them, and a helper reports the current set-bit fraction for saturation monitoring.

• Inputs. capacity (design n) and error_rate (target p).
• Backing store. bytearray.
• Hashing. mmh3.hash128 split into two lanes.

Question. Implement a dependency-light BloomFilter with add, membership test, and a fill_ratio diagnostic.

Input.

Method	Behaviour
constructor (capacity, error_rate)	size m, k; allocate bytearray
add(item)	set k bits
item in bf membership test	test k bits (all set → maybe)
fill_ratio()	fraction of bits set (saturation check)

Code.

import math
import mmh3

class BloomFilter:
    def __init__(self, capacity: int, error_rate: float = 0.01):
        self.n = capacity
        self.p = error_rate
        self.m = max(8, math.ceil(-(capacity * math.log(error_rate)) / (math.log(2) ** 2)))
        self.k = max(1, round((self.m / capacity) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)     # ceil(m/8) bytes
        self.count = 0                               # elements added

    def _indexes(self, item: str):
        item = item if isinstance(item, (bytes, str)) else str(item)
        d = mmh3.hash128(item, signed=False)
        h1, h2 = d & 0xFFFFFFFFFFFFFFFF, d >> 64
        if h2 == 0:
            h2 = 1
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item) -> None:
        for idx in self._indexes(item):
            self.bits[idx >> 3] |= (1 << (idx & 7))
        self.count += 1

    def __contains__(self, item) -> bool:
        return all(self.bits[idx >> 3] & (1 << (idx & 7)) for idx in self._indexes(item))

    def fill_ratio(self) -> float:
        set_bits = sum(bin(b).count("1") for b in self.bits)
        return set_bits / self.m

bf = BloomFilter(capacity=1_000_000, error_rate=0.01)
print(f"m={bf.m:,} bits ({bf.m//8//1000} KB), k={bf.k}")
bf.add("user:42")
print("user:42" in bf, "user:99" in bf)      # True  False (almost surely)

Step-by-step explanation.

1. The constructor sizes m from (capacity, error_rate) and k from (m, capacity), then allocates ceil(m/8) bytes — for 1M keys at 1% that is ~1.2 MB and k = 7.
2. _indexes computes one 128-bit MurmurHash, splits it into two 64-bit lanes, and yields k positions via double hashing — one hash call per operation.
3. add ORs each of the k bits on and bumps count, which lets fill_ratio and saturation checks reason about how full the filter is.
4. The in membership test returns True only if all k bits are set; the all(...) generator short-circuits at the first 0, so a "definitely not" is cheap.
5. fill_ratio popcounts the whole array; at the design load it should read ~0.5 (the optimal-k sweet spot). A reading well above 0.5 is a saturation alarm meaning count has exceeded the design n.

Output.

Call	Result
m, k for (1M, 1%)	9,585,059 bits (~1.2 MB), k=7
"user:42" in bf (added)	True
"user:99" in bf (absent)	False (≈99% of the time)
fill_ratio() after 1 add	~7 / m ≈ 0

Rule of thumb. Keep m, k, and count on the object so the filter can self-report saturation. Back it with bytearray for zero dependencies or bitarray for speed, and always hash once per operation via double hashing — never call the hash function k times.

Worked example — measuring observed versus predicted false positive rate

Detailed explanation. A sized filter is a claim; the empirical test is the proof. Insert n known members, then probe a large disjoint set of known non-members and count "maybe" verdicts — the observed rate should match the formula.

• Design. n = 100,000 at p = 1%.
• Probe. 200,000 known non-members.
• Compare. Observed FP fraction versus (1 − e^{−kn/m})^k.

Question. Build the filter, insert 100k members, probe 200k non-members, and compare the observed false-positive rate to the predicted one.

Input.

Parameter	Value
Members inserted	100,000
Non-members probed	200,000
Target p	1%
Prediction	(1 − e^{−kn/m})^k

Code.

import math

bf = BloomFilter(capacity=100_000, error_rate=0.01)

# Insert 100k known members
for i in range(100_000):
    bf.add(f"member:{i}")

# Probe 200k known NON-members (disjoint namespace)
false_positives = sum(1 for i in range(200_000) if f"absent:{i}" in bf)
observed = false_positives / 200_000

# Predicted FPR from the actual m, k, n
predicted = (1 - math.exp(-bf.k * bf.n / bf.m)) ** bf.k

print(f"m={bf.m:,}  k={bf.k}  fill={bf.fill_ratio():.3f}")
print(f"observed FPR  = {observed:.3%}")
print(f"predicted FPR = {predicted:.3%}")
# typical:
# m=958,506  k=7  fill=0.500
# observed FPR  = 1.02%
# predicted FPR = 1.00%

Step-by-step explanation.

1. The filter is sized for 100k at 1%, giving m ≈ 958,506 bits and k = 7.
2. Inserting exactly the design count of members brings the fill ratio to ~0.5 — the optimal-k half-full state the formula assumes.
3. Probing 200k non-members in a disjoint namespace (absent:* vs member:*) counts genuine false positives, since none of those keys were inserted.
4. The observed rate (~1.02%) matches the predicted rate (1.00%) within sampling noise — confirmation that both the sizing and the double hashing are correct.
5. If observed sharply exceeded predicted, the usual culprits are a weak or mis-split hash, an off-by-one in the bit indexing, or having inserted more than the design n (check fill_ratio — well above 0.5 means saturation).

Output.

Quantity	Value
Fill ratio after 100k inserts	~0.500
Observed FPR (200k probes)	~1.02%
Predicted FPR	~1.00%
Agreement	within noise → filter is healthy

Rule of thumb. Always measure the observed false-positive rate against the predicted one on a disjoint non-member probe set before trusting a bloom filter in production. A fill ratio near 0.5 at the design count and observed ≈ predicted are your two green lights; a fill ratio far above 0.5 means you have overrun capacity.

Python interview question on building and tuning a dedup filter

A senior interviewer might ask: "Build a bloom filter for a streaming pipeline that must dedup roughly 5 million distinct records per hour at a 0.5% false positive rate, using constant memory. Show the sizing, the class, how you would detect when the filter has been overrun, and what you would do when it approaches capacity."

Solution Using a sized BloomFilter with saturation detection and rebuild

import math

class DedupFilter:
    def __init__(self, capacity: int, error_rate: float):
        self.bf = BloomFilter(capacity, error_rate)
        self.capacity = capacity

    def seen(self, key: str) -> bool:
        """Return True if key is a probable duplicate; else record it and return False."""
        if key in self.bf:
            return True                       # "maybe" -> treat as duplicate
        self.bf.add(key)
        return False

    def is_overrun(self) -> bool:
        # Two signals: element count past design n, or fill ratio past ~0.5
        return self.bf.count > self.capacity or self.bf.fill_ratio() > 0.55

# Size for 5M/hour at 0.5%
dedup = DedupFilter(capacity=5_000_000, error_rate=0.005)
print(f"m={dedup.bf.m:,} bits ({dedup.bf.m//8//1_000_000} MB), k={dedup.bf.k}")

for rec_id in stream_of_records():            # pseudo-source
    if not dedup.seen(rec_id):
        emit(rec_id)
    if dedup.is_overrun():
        dedup = DedupFilter(5_000_000, 0.005)  # rotate to a fresh hourly filter

Step-by-step trace.

Step	Value	Reasoning
bits per element	−ln(0.005)/(ln 2)^2 ≈ 11.03	0.5% target
m	5,000,000 × 11.03	~55.2M bits ≈ 6.9 MB
k	round(11.03 × ln 2)	8
overrun signal 1	count > 5,000,000	past design capacity
overrun signal 2	fill_ratio > 0.55	array too saturated
action on overrun	allocate fresh filter	constant memory, reset error

1. Bits per element for 0.5% is −ln(0.005)/(ln 2)^2 ≈ 11.03, so a 5M-key filter needs ~55.2M bits ≈ 6.9 MB — constant, small, predictable.
2. k = round(11.03 · ln 2) = 8 hash probes minimise the error at that size.
3. seen(key) implements dedup with the one-sided contract: a "maybe" is treated as a duplicate (dropped), a "definitely not" is a first sight (emitted and recorded).
4. is_overrun() watches two independent signals — the element count exceeding the design n, and the fill ratio climbing past ~0.55 — either of which means the error has drifted above target.
5. On overrun the pipeline rotates to a fresh filter (the hourly boundary), keeping memory constant and resetting the error to target; a scalable bloom filter is the alternative if the window cannot be rotated.

Output:

Metric	Value
Filter memory	~6.9 MB (constant)
k (hash probes)	8
Duplicate handling	"maybe" → drop; "definitely not" → emit + record
Overrun detection	count > n OR fill_ratio > 0.55
Recovery	rotate to a fresh sized filter

Why this works — concept by concept:

• Sized for the hourly count — sizing m for the maximum 5M distinct keys holds the error at 0.5% for the whole hour; sizing for fewer would let the error climb as the filter fills.
• One-sided dedup — seen maps "maybe" → duplicate and "definitely not" → new, so the only error is occasionally dropping a genuinely new record, never emitting a duplicate. Choose this only where a small drop rate is acceptable, or add an exact-confirm on "maybe".
• Dual overrun signals — element count catches known overrun; fill ratio catches it empirically even if the count estimate is wrong. Together they detect capacity breach before the error blows past target.
• Rotate for constant memory — allocating a fresh filter at the window boundary keeps memory flat and resets the error, which is exactly the rotating-window pattern from section 3 applied to a single stream.
• Cost — O(k) = 8 hash-derived bit ops per record and a fixed ~6.9 MB of memory regardless of key size or stream length. The exact alternative (a growing hash set of 5M keys) would cost far more memory and grow unbounded across hours.

PYTHON
Topic — optimization
Space-efficient sizing and tuning problems

Practice →

PYTHON
Topic — data-structures
Implement-a-data-structure problems in Python

Practice →

---

Cheat sheet — bloom filter recipes

• The membership contract. A bloom filter answers only "definitely not" (certain) or "maybe" (probabilistic). No false negatives, possible false positives. Never describe it as a fast hash set — name the one-sided error first. A "definitely not" is a certificate of absence; a "maybe" is a member or a false positive.
• The two parts. A bit array of m bits plus k hash functions. Insert sets k bits (bitwise OR); query tests k bits (all-1s → "maybe", any-0 → "definitely not"). Memory is independent of element size — a filter over 1 KB log lines costs the same bits per element as one over 8-byte ints.
• The false-positive-rate formula. p ≈ (1 − e^{−kn/m})^k. It rises monotonically with n, so every bloom filter has a design capacity; overrun it and the error climbs past target.
• Optimal k. k = (m/n)·ln 2 ≈ 0.693·(m/n), rounded to an integer. At the optimum the array is ~50% full and p ≈ 0.5^k. Fewer hashes under-fill, more hashes over-saturate.
• Sizing for a target p. m = −(n·ln p)/(ln 2)^2, i.e. m/n ≈ −1.4427·log2(p) bits per element. Memorise: 1% → ~9.6 bits, k=7; 0.1% → ~14.4 bits, k=10; 0.01% → ~19.2 bits, k=13. Each extra 10× of accuracy costs a flat ~4.8 bits per element.
• Double hashing. Never compute k independent hashes. Take one 128-bit MurmurHash, split into h1 (low 64) and h2 (high 64), derive index i as (h1 + i·h2) mod m for i = 0…k−1 (Kirsch–Mitzenmacher). Guard h2 ≠ 0.
• Deletion → counting bloom. Replace bits with small (usually 4-bit) counters; add increments, delete decrements, query tests all-nonzero. Costs ~4× memory. Saturate counters at max and freeze them; never delete a key you did not provably insert (risks false negatives).
• Unknown growth → scalable bloom. Chain filters with tightening error p_0·r^i; overall error is bounded by p_0/(1−r). Pick r (0.8–0.9 common) so the bound is your acceptable ceiling; number of filters grows logarithmically with element count.
• Churn / windowing. For a rolling window, rotate a ring of per-slice plain filters and drop the oldest to expire keys — O(1) expiry, no shared-bit deletion, no false negatives. Query is an OR across the ring.
• Modern alternative → cuckoo filter. Stores fingerprints in a cuckoo hash table; supports deletes natively, better lookup locality (two buckets), and is more space-efficient than bloom below ~3% error. Prefer it for churny, latency-sensitive sets; bloom stays simplest for append-only.
• LSM / SSTable usage. One bloom per SSTable; a "definitely not" skips the file's random disk read, cutting read amplification for absent/rare keys by ~(1 − fpr) per skipped file. RocksDB: NewBloomFilterPolicy(bits_per_key) (default ~10 → ~1%), whole_key_filtering for point lookups, prefix_extractor for prefix scans, partition_filters + cached filter blocks so the check never hits disk.
• Join & file pruning. Warehouses and Spark build a bloom over the small side's join keys and broadcast it to prune the large side before shuffle (runtime/bloom-filter join); per-file blooms in Parquet/ORC skip files that cannot contain a predicate value.
• Verify before trusting. After building, probe a large disjoint set of known non-members and compare observed FP fraction to (1 − e^{−kn/m})^k. A fill ratio ~0.5 at the design count and observed ≈ predicted are your two green lights; fill far above 0.5 means capacity overrun.

Frequently asked questions

What is a bloom filter in one sentence?

A bloom filter is a space-efficient probabilistic data structure that stores set membership in a bit array using k hash functions, answering a membership test with either "definitely not in the set" (always correct) or "possibly in the set" (correct except for a small, tunable false positive rate). It never produces false negatives, so a "definitely not" can be trusted to skip an expensive lookup, disk read, or network call, and it stores bits about elements rather than the elements themselves — making its memory independent of how large each element is. That combination of constant-time queries and roughly 9.6 bits per element at 1% error is why bloom filters appear everywhere from LSM databases to CDN caches to distributed joins.

Why can't a bloom filter have false negatives?

Because inserting an element only ever turns bits on, and a plain bloom filter never turns bits off. Every bit that a genuine member set during insertion is therefore still 1 at query time, so a real member can never produce a 0 bit, and a query only reports "definitely not" when it finds a 0. The one-sided error is a direct consequence of the append-only bit array: the moment you introduce deletion (clearing bits), you risk clearing a bit another element depends on and creating a false negative — which is exactly why deletion requires the counting bloom variant with per-position counters instead of single bits.

How many bits per element do I need?

The bits-per-element cost is −ln(p)/(ln 2)^2 ≈ −1.4427·log2(p), which depends only on the target false positive rate p, not on the element size. The numbers worth memorising are 1% → ~9.6 bits, 0.1% → ~14.4 bits, 0.01% → ~19.2 bits, with each additional 10× of accuracy adding a flat ~4.8 bits per element. So a filter for 100 million keys at 0.1% needs about 180 MB regardless of whether the keys are 8-byte integers or 400-byte URLs. Once you fix m, set the hash count to the optimum k = round((m/n)·ln 2).

Can you delete from a bloom filter?

Not from a plain bloom filter — its bits are shared across elements, so clearing one element's bits could break another element's membership and create a false negative. To support deletion you use a counting bloom filter, which replaces each bit with a small counter (commonly 4 bits): insert increments the k counters, delete decrements them, and query tests that all k are non-zero. This costs roughly 4× the memory of a plain filter and requires that you only ever delete elements you actually inserted. For churny or latency-sensitive sets, a cuckoo filter (which stores fingerprints and supports exact deletion with better locality) or a rotating ring of plain filters for window expiry are often better choices than a counting bloom.

Where are bloom filters used in databases?

The flagship use is in log-structured-merge (LSM) storage engines like RocksDB, LevelDB, Cassandra, HBase, and ScyllaDB, where each immutable SSTable carries a LSM bloom filter over its keys. On a point lookup, the engine tests the key against each SSTable's bloom before reading the file from disk; a "definitely not" lets it skip that file's random I/O entirely, which slashes read amplification for absent and rare keys. Bloom filters also power join pruning (broadcasting a bloom of the small side's join keys to pre-filter the large side in Spark and cloud warehouses), per-file pruning in Parquet/ORC, and one-hit-wonder cache admission in CDNs. In every case the "definitely not" verdict is what converts an expensive operation into a skipped one.

Bloom filter vs hash set vs cuckoo filter — when do I use each?

Use an exact hash set when correctness is absolute and the set fits in memory where you need it — it has zero false positives but stores every element, so it is the largest of the three. Use a bloom filter when the set is too large for an exact structure, a "definitely not" saves real work, and a small false-positive rate of wasted work is acceptable; it is the simplest and most compact option for append-only sets. Use a cuckoo filter when you need the space savings of a probabilistic structure and deletion or better lookup locality — it stores fingerprints, supports exact deletes, touches only two cache lines per query, and beats bloom on space below about 3% error, at the cost of possible insert failures near full load. In short: exactness → hash set; append-only compactness → bloom; deletes and locality → cuckoo.

Practice on PipeCode

• Drill the data-structures practice library → for the probabilistic-structure, set-membership, and storage-engine index problems senior interviewers reach for.
• Rehearse on the hash-table practice library → for the hashing, collision, fingerprinting, and double-hashing fundamentals that bloom filters are built on.
• Sharpen the sizing math on the optimization practice library → for the space–time trade-off, read-amplification, and false-positive-rate tuning scenarios.
• Stack the prerequisites against PipeCode's broader 450+ data-engineering catalogue to anchor the bloom-filter sizing formula against real graded inputs.

Lock in bloom filter muscle memory

Docs explain the bit array. PipeCode drills explain the decision — when a "definitely not" is worth a whole disk read, when the false-positive rate blows past target because you overran capacity, when a counting bloom's 4× memory is justified, and when a cuckoo filter is the better call. Pipecode.ai is Leetcode for Data Engineering — structure-first practice tuned for the production trade-offs senior data engineers actually face.

Practice data-structure problems →
Practice hashing problems →