← Create New Paste

Bloom Filters in Interviews: When "Probably Yes" Is Good Enough

3 views
Bloom filters come up in two kinds of interviews: system design rounds, where they are a tool for saving memory and network calls, and data-structure rounds, where you might be asked to implement one or reason about its false-positive rate. Either way, understanding the trade-off they make is what impresses interviewers. What a Bloom filter does A Bloom filter answers the question "have I seen this item before?" using very little memory. It can say "definitely not" or "probably yes". It never gives a false negative, but it can give a false positive. In exchange you store only a bit array, not the items themselves. How it works Start with an array of m bits, all zero, and k independent hash functions. To add an item, hash it k times and set those k bits to 1. To check an item, hash it k times; if any of those bits is 0, the item was never added. If all are 1, it was probably added, though another combination of items may have set those same bits. class Bloom: def __init__(self, m, k): self.bits = bytearray(m); self.m = m; self.k = k def _idx(self, x): h1 = hash(x); h2 = hash(str(x) + "#") return [(h1 + i * h2) % self.m for i in range(self.k)] def add(self, x): for i in self._idx(x): self.bits[i] = 1 def maybe_contains(self, x): return all(self.bits[i] for i in self._idx(x)) The double-hashing trick (h1 + i*h2) is worth mentioning: it gives you k hash functions from two, with almost no loss in accuracy. The math interviewers like With n items, m bits, and k hashes, the false-positive rate is roughly (1 - e^(-kn/m))^k. The best k is about (m/n) * ln 2. A useful rule of thumb: about 10 bits per item with 7 hash functions gives roughly a 1 percent false-positive rate. Being able to quote that from memory and derive it loosely tends to land well. Where they show up in system design - Avoiding expensive lookups: databases like Cassandra, HBase, and RocksDB keep a Bloom filter per SSTable so a read can skip files that definitely do not contain the key. - Web crawlers: track which URLs have already been visited without storing billions of strings. - Caches: avoid caching "one-hit wonders" by only caching items the filter says were seen before. - Username or coupon-code checks: a quick "definitely available" answer before hitting the database. Limitations to raise yourself Standard Bloom filters cannot delete items, because clearing a bit may remove other items too. Counting Bloom filters (small counters instead of bits) or cuckoo filters solve that at a memory cost. They also cannot list their contents, and the false-positive rate grows as you add more items than you sized for, so you need an estimate of n up front or a scalable variant. How to bring it up in an interview Do not lead with a Bloom filter just to sound clever. Introduce it when you hit a concrete problem: "We are doing a disk read for every key lookup, and most keys are absent; a Bloom filter in memory would let us skip about 99 percent of those reads." Then state the false-positive cost and why it is acceptable. If you know this material but freeze when a system design interviewer starts probing trade-offs, Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews, helping you keep your reasoning structured under pressure.
Created Nov 15, 2026 11:03 Expires Nov 15, 2027 11:03