Bloom Filter Query

Problem

Insert items into a Bloom filter and report membership queries.

The filter has num_bits bits and num_hashes hash functions using the same djb2 scheme as the insert problem. A query returns True only when every one of its hash bits is set, so false positives are possible but false negatives are not.

Return the list of query results.

Hint

Any zero bit immediately proves the item was never inserted.

Test cases

case 1

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

expected: [true,true,false]

case 2

in: [10,1,["x"],["x","y"]]

expected: [true,false]

case 3

in: [16,3,[],["z"]]

expected: [false]

case 4

in: [8,2,["ab","cd"],["ab","ac"]]

expected: [true,false]

Starter codePython

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

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