Bloom Filter Insert

Problem

Simulate inserting items into a Bloom filter and return the final bit array.

The filter has num_bits bits and uses num_hashes independent hash functions. Hash number seed is djb2 of the string "seed:item" (seed and item joined by a colon) reduced modulo num_bits, and each hash sets one bit. Inserting the same item twice changes nothing.

Return the bit list after all insertions.

Hint

Each of the k hashes sets a single bit, so repeated items set the same bits again.

Test cases

case 1

in: [8,2,["a","b"]]

expected: [1,1,1,0,0,0,0,0]

case 2

in: [10,1,[]]

expected: [0,0,0,0,0,0,0,0,0,0]

case 3

in: [1,3,["x"]]

expected: [1]

case 4

in: [8,2,["a","a"]]

expected: [1,1,0,0,0,0,0,0]

Starter codePython

def bloom_insert(num_bits, num_hashes, items):
    # Your code here
    pass

4 test cases · run your code against them in the editor