What is a Bloom filter and when is it useful? | Interview Question

Q: What is a Bloom filter and when is it useful?

**Target Audience:** Beginners to system design — you know what a hash function and a set are; the probability is worked through step by step. **Difficulty:** Medium **Verified with:** Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Error rates and sizes come from running the example; the **Verified** section quotes the full output. ## 1. Why This Even Matters — A Story First A nightclub bouncer has a guest list of 10,000 names, but no time to read it for every person in the queue. So the organiser gives the bouncer a card with 100,000 tiny boxes. For every guest, the organiser ran their name through seven different scrambling rules, each pointing to one box, and ticked those seven boxes. When someone arrives, the bouncer applies the same seven rules to their name and looks at thos

The problem

Question presented to candidate: "What is a Bloom filter? Explain how it works, what kind of mistakes it can make, how you would size one, and give me a couple of places in a real system where you would use it."

What a strong answer should cover:

The structure: a bit array of m bits and k hash functions; add sets k bits, a lookup checks the same k bits
The guarantee: no false negatives ("not present" is always right), tunable false positives ("maybe present" can be wrong)
The maths: false-positive rate about (1 - e^(-kn/m))^k; optimal k = (m/n) ln 2; about 9.6 bits per item for 1%, independent of item size
What it cannot do: no deletes (unless counting or cuckoo filters), no listing members, and the error rate climbs fast when you insert more than it was sized for
Real uses: LSM-tree databases skipping files that cannot hold a key (Cassandra keeps one per SSTable), guarding a cache or database from lookups of keys that do not exist, crawlers checking seen URLs; Redis 8 ships Bloom filters built in
The trade-off in one line: memory and speed for a small, known chance of an unnecessary expensive lookup

Code / implementation expected: Optional — a short implementation (bit array plus double hashing) or the sizing formula; the example builds one and measures its error rate.

bloom-filter

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners to system design — you know what a hash function and a set are; the probability is worked through step by step. Difficulty: Medium Verified with: Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output).

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Error rates and sizes come from running the example; the Verified section quotes the full output.

1. Why This Even Matters — A Story First

A nightclub bouncer has a guest list of 10,000 names, but no time to read it for every person in the queue. So the organiser gives the bouncer a card with 100,000 tiny boxes. For every guest, the organiser ran their name through seven different scrambling rules, each pointing to one box, and ticked those seven b

The solution is hidden so you can try first

11 min read · 10 sections

Read the code

A Bloom filter from scratch: sizing, false positives measured vs predicted, overfilling, choosing k

Open in playground

// A Bloom filter from scratch: sizing, no false negatives, measured vs predicted
// false-positive rate, what overfilling does, and the effect of k.

function fnv1a(s) { // 32-bit FNV-1a
  let h = 2166136261;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 16777619) >>> 0; }
  return h;
}
function djb2(s) { // 32-bit djb2, used as the second hash
  let h = 5381;
  for (let i = 0; i < s.length; i++) h = (Math.imul(h, 33) + s.charCodeAt(i)) >>> 0;
  return h;
}

class Bloom {
  constructor(m, k) { this.m = m; this.k = k; this.bits = new Uint8Array(Math.ceil(m / 8)); }
  positions(s) { // double hashing: index_i = (h1 + i * h2) mod m
    const h1 = fnv1a(s), h2 = djb2(s) | 1;
    const out = [];
    for (let i = 0; i < this.k; i++) out.push((h1 + i * (h2 >>> 0)) % this.m);
    return out;
  }
  add(s) { for (const p of this.positions(s)) this.bits[p >> 3] |= 1 << (p & 7); }
  has(s) { return this.positions(s).every((p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0); }
}

const pct3 = (count, of) => { // count / of as a percentage with 3 decimals, integer maths only
  const x = Math.round((count * 100000) / of);
  return Math.floor(x / 1000) + "." + String(x % 1000).padStart(3, "0") + "%";
};
const predicted = (m, k, n) => (100 * Math.pow(1 - Math.exp((-k * n) / m), k)).toFixed(3) + "%";

const n = 10000, p = 0.01;
const m = Math.ceil((-n * Math.log(p)) / (Math.LN2 * Math.LN2));
const k = Math.round((m / n) * Math.LN2);
let keyBytes = 0;
for (let i = 0; i < n; i++) keyBytes += ("user:" + i).length;
console.log(`Sizing for n=${n}, target p=${p}: m=${m} bits (${Math.ceil(m / 8)} bytes), k=${k}`);
console.log(`  the keys themselves are ${keyBytes} bytes of text, before any hash-table overhead`);

const f = new Bloom(m, k);
for (let i = 0; i < n; i++) f.add("user:" + i);
let missing = 0;
for (let i = 0; i < n; i++) if (!f.has("user:" + i)) missing++;
const TESTS = 100000;
function fpCount(filter) {
  let c = 0;
  for (let j = 0; j < TESTS; j++) if (filter.has("visitor:" + j)) c++;
  return c;
}
const fp = fpCount(f);
console.log("\nAfter adding 10000 members");
console.log(`  members reported absent (false negatives): ${missing}`);
console.log(`  non-members reported present: ${fp} of ${TESTS} = ${pct3(fp, TESTS)} (predicted ${predicted(m, k, n)})`);
console.log(`  as a guard in front of a database: ${TESTS - fp} of ${TESTS} lookups for missing keys never reach it`);

console.log("\nOverfilling the same filter (m and k fixed)");
for (const total of [20000, 40000]) {
  const g = new Bloom(m, k);
  for (let i = 0; i < total; i++) g.add("user:" + i);
  const c = fpCount(g);
  console.log(`  ${String(total).padStart(5)} items: false positives ${pct3(c, TESTS).padStart(7)} (predicted ${predicted(m, k, total)})`);
}

console.log("\nChoosing k for the same m and n");
for (const kk of [1, 3, 7, 12, 20]) {
  const g = new Bloom(m, kk);
  for (let i = 0; i < n; i++) g.add("user:" + i);
  const c = fpCount(g);
  console.log(`  k=${String(kk).padStart(2)}: false positives ${pct3(c, TESTS).padStart(7)} (predicted ${predicted(m, kk, n)})`);
}

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.