Bloom Filter · bossfight.dev

The Name Guard watches the gate of a city of a billion citizens. All day, newcomers ask the same thing: "Is my name taken?" The guard has no room to remember a billion names, so it keeps a row of m lamps instead, all dark at first. When a name is registered, the guard hashes it k ways and lights those k lamps. When someone asks about a name, it hashes that name the same k ways and looks:

any of those lamps still dark → the name is definitely not taken;
all of them lit → the name might be taken. Other names may have lit those lamps between them, so this can be a false alarm.

Build the guard's memory, a class BloomFilter:

BloomFilter(m, k): a row of m bits, all 0, and k positions per word.
add(word): set the word's k bits to 1.
might_contain(word): True if all of the word's k bits are 1, otherwise False.

The hashes are fixed, so every language gets the same answers, false alarms included. Letters count by their ASCII code ('a' = 97, 'b' = 98, ...):

P = 998244353
h1(word):  h = 0, then for each letter c from left to right:  h = (h * 65537 + code(c)) mod P
h2(word):  h = 0, then for each letter c from left to right:  h = (h * 12345 + code(c)) mod P
position i, for i = 0, 1, ..., k - 1:   (h1 + i * h2) mod m

A word's positions may repeat (with m = 1 they are all 0). That's fine: lighting a bit twice leaves it lit.

g = BloomFilter(16, 3)
g.add("ana")               # h1 = 363855759, h2 = 808642530: bits 15, 1, 3
g.add("bob")               # bits 14, 11, 8
g.add("cyd")               # bits 7, 0, 9
g.might_contain("bob")     # True
g.might_contain("dan")     # False   its bits are 5, 1, 13: bit 5 is dark
g.might_contain("eve")     # True    its bits 14, 15, 0 were lit by bob, ana and cyd

"eve" was never added, yet the answer is True: that's a false alarm, and the tests expect exactly the answers the bits give. So keeping the words in a set doesn't work. It's also the memory the guard can't afford.

1 <= m <= 10^6, 1 <= k <= 10; words are 1 to 20 lowercase letters a–z.
Up to 10^5 calls. Each call should cost O(length of the word + k), whatever was added before.
In C++ and Java, do the hash arithmetic in 64-bit integers (long long, long): h * 65537 and i * h2 don't fit in 32 bits.