Bloom Filter

Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.

Build a filter that can quickly answer one question: "could this item be here?" It uses far less memory than storing every item in a list or a set, but it pays for that with one strange trade. It will never say no for an item you added. But sometimes it will say yes for an item you never added at all. That second part is allowed on purpose, as long as it does not happen too often. Implement New(m, k), Add(data), and Contains(data) -> bool using your language's names. m is how many bits your filter uses. k is how many different spots you check (and set) for every item.

bits (m = 10): [0][0][1][0][0][0][0][1][0][0]
                      ^ bit 2            ^ bit 7
Add("cat") sets bit 2 and bit 7.
Contains("cat") checks bit 2 and bit 7. Both are 1, so it answers yes.
Contains("dog") might also check bit 2 and bit 7 and find them both set,
even though "dog" was never added. That is allowed, sometimes.

One rule to know before you start: m will not always be a nice round number like a power of two. If you pick a bit position with a shortcut such as hash & (m-1), that only gives the right spread of positions when m is a power of two. Use a true remainder (%) instead, every time. Standard library only. Build the bit array yourself. Your filter receives one call at a time. For help with the ideas, read the notes.

Where it is used

• Cassandra keeps a Bloom filter for each data file on disk. Before it opens a file to look for a row, it asks the filter, and it skips every file where the answer is "definitely not here".
• RocksDB, when you turn its Bloom filter on, checks the filter of each file first and skips reading the file's data when the filter rules the key out.
• PostgreSQL offers a Bloom index that quickly rules out rows. The filter can say yes by mistake, so PostgreSQL checks every row it finds against the real data.

A filter that says no for an item that was added is the one answer these systems cannot survive: they would skip the file that holds the data and report it as missing.

Stages

bf1: hello: add one item, find it (very easy)

Add one item, then check that it is there. Example: Add("cat"), then Contains("cat") -> true.

The tester will verify: an item you added is reported present.

bf2: every item you add is found (easy)

Add a handful of items, then check each one. Example: Add("a"), Add("b"), Add("c"), then Contains("a") -> true, Contains("b") -> true, Contains("c") -> true.

The tester will verify: every item you added comes back as present, with zero exceptions.

bf3: many items, never losing one (medium)

Add hundreds of items, then check every one of them again. None of them may come back missing. Here m is 10,007 bits, which is not a power of two, so a shortcut bit mask gives the wrong spots. Also make sure your k checks really land on k different spots, not the same spot picked more than once.

The tester will verify: every one of the hundreds of added items is still found. A single miss fails the stage.

bf4: how often it says yes by mistake (medium)

Now check items you never added. The filter is allowed to say maybe present for some of them, even though they were never added. That is on purpose, but only within a range, not too often and not too rarely. Here the filter holds 625 items in 10,007 bits with 5 checks per item, and the test asks 20,000 items that were never added. About 6 to 139 of those 20,000 should come back as present. Fewer than that is wrong too. It usually means your filter is secretly storing every item exactly (like a plain set) instead of allowing the occasional mistake a real filter is built to allow.

The tester will verify: zero added items missing, and between about 6 and 139 of the 20,000 never-added items reported present.

bf5: the same check, with less room (hard)

Same two checks as bf4, but with more items in a smaller bit array, so mistakes happen more often and the allowed range is tighter. Here the filter holds 900 items in 6,007 bits with 5 checks per item, and the test asks the same 20,000 never-added items. About 407 to 1,304 of those 20,000 should come back as present this time.

The tester will verify: zero added items missing, and between about 407 and 1,304 of the 20,000 never-added items reported present.

bf6: answer speed (L2, hard)

Keep Contains fast even when your filter holds thousands of items. Keep every answer correct too. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct. How many memory allocations you use is also shown, but it never decides a pass or a fail.

Rules

• Standard library only. Build the bit array yourself.
• Your answers must be the same every time for the same sequence of calls.
• Print nothing you don't have to. The last line you print belongs to the tester.
• m is not a power of two on any stage. Always use a true remainder, never a bitmask shortcut.
• Don't pack all k checks into one small block of bits, such as a single 64-bit word, to make things faster. That trades away the accuracy these stages check. Spread your checks across the full m bits, or don't block them at all.

Read the Bloom Filter notes in the wiki