Bloom Filter

Bloom Filter

Design a Bloom filter — a compact, probabilistic set that answers membership with no false negatives and occasional false positives.

Requirements

• The filter has m bits (all initially 0) and k hash functions, both fixed at construction.
• Exact hash family — identical in every language. For a key string, treat each character as its ASCII code c. Hash function i (for i = 0, 1, …, k-1) uses base B_i = 31 + 100 * i:

  h = 0
  for each character code c in key (left to right):
      h = (h * B_i + c) mod m
  position_i = h            // already in [0, m)
  

  Reduce mod m after every step, using 64-bit integers, so C++/Java/Python/JS all compute bit-for-bit identical positions (no overflow, no drift).
• add(key) sets the bits at position_0 … position_{k-1}.
• mightContain(key) returns true iff all those k bits are currently set.
• The filter may report a false positive (an unadded key whose k bits were all set by other keys) but never a false negative — a key you added always reports true.
• Keys are whitespace-free tokens (lowercase letters and digits in the tests).

API to implement

Implement the class BloomFilter. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | add <key> | — | Add key to the filter by setting the k bits it hashes to. | | mightContain <key> | boolean | Return true iff all k of key's bit positions are set. A true may be a false positive; a false is always correct (no false negatives). |

Input format

The first line contains Q, the number of operations. The second line contains the constructor arguments: m — the number of bits; k — the number of hash functions. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

4
64 3
mightContain apple
add apple
mightContain apple
mightContain mango

false
true
false

5
128 4
add cat
add dog
mightContain cat
mightContain dog
mightContain fox

true
true
false