Sign in
Skip to solution
mediumSystem Design

What is a Bloom filter and when is it useful?

93 views
01

Understand the problem

Explain Bloom filters.

bloom-filter
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Step 1: Outline use cases and constraints

Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.

Use cases

We'll scope the problem to handle only the following use cases

  • User needs to understand bloom-filter to make architecture deci

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Bloom filter (add / contains)
Run Playground
import hashlib

class BloomFilter:
    def __init__(self, size=1000, k=3):
        self.size = size
        self.k = k
        self.bits = [0] * size
    def _positions(self, item):
        for i in range(self.k):
            h = hashlib.md5((str(i) + item).encode()).hexdigest()
            yield int(h, 16) % self.size
    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos] = 1
    def contains(self, item):
        return all(self.bits[pos] for pos in self._positions(item))

bf = BloomFilter()
for name in ["ada", "grace", "linus"]:
    bf.add(name)

print("ada  ->", bf.contains("ada"))    # True  (was added)
print("alan ->", bf.contains("alan"))   # False (definitely not present)
# 'True' can be a false positive; 'False' is always correct.
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 42 of 99 decoded in the System Design track. One more won't hurt.

Back to track