CODING CHALLENGE · N°34

Bloom Filter

Medium Data StructuresProbabilisticHashing

A tiny bit-array that answers "have I seen this?" using a fraction of the memory of a real set — at the cost of occasional false positives, but never a false negative. It guards databases, CDNs and crawlers from pointless lookups. Build one with double hashing. Provided hashes keep Python and TypeScript in sync. Hidden tests.

The problem

Build a Bloom filter of m bits using k hash functions, insert every item in items, then answer each query in queries: return True if the item is possibly present (all k of its bits are set) or False if it is definitely absent. Derive the k bit positions by double hashing: bit i is (hash32(x) + i·hb(x)) % m for i in 0…k-1. Both hashes are provided. Implement bloom(items, queries, m, k).

EXAMPLE 1

Input bloom(['cat','dog','bird'], ['cat','dog','bird','zebra','fish'], 64, 3)

Output [True, True, True, False, False]

inserted items are always found; these absent ones happen to hit an unset bit

CONSTRAINTS

Use the provided hash32 and hb — the tests depend on the exact bit positions.
No false negatives: every inserted item must return True. Bloom filters can only err the other way.
A false positive is possible (an absent item whose k bits all happen to be set) — that is allowed by design.
An empty filter (no items) must return False for everything.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement bloom(items, queries, m, k): make an m-bit array, set the k double-hashed bits of every item, then for each query return whether all of its k bits are set.

HINTS — 4 IDEAS

A bit array is just a list of 0/1 of length m. Setting a bit twice is fine (idempotent).
The i-th bit position for item x is (hash32(x) + i * hb(x)) % m — this is double hashing, giving k independent-looking positions from two hashes.
Insert: for every item, set all k of its bits to 1.
Query: the item is "possibly present" only if every one of its k bits is already 1; a single 0 proves it was never inserted.

CPython · WebAssembly

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Caching & Performance