Counting Bloom Increment

Problem

Update a counting Bloom filter with insertions and deletions.

width is the number of counters and num_hashes is the number of hash functions. Inserts increment counters at djb2(seed:item) mod width for each seed; deletions decrement the same counters, never below zero. Unlike a plain Bloom filter, deletions are safe because counts are tracked.

Return the counter list.

Hint

Deleting an item decrements exactly the counters that insertion incremented.

Test cases

case 1

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

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

case 2

in: [4,1,["a","a","b"],["a"]]

expected: [1,1,0,0]

case 3

in: [5,2,[],["x"]]

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

case 4

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

expected: [0,0,0]

Starter codePython

def counting_bloom(width, num_hashes, inserts, deletes):
    # Your code here
    pass

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