Count-Min Conservative Increment

Problem

Apply conservative updates to a Count-Min sketch and return the final counter matrix.

For each item compute one index per row as djb2 of the string seed:item modulo width, then increment only those counters whose current value equals the minimum across the rows. width is the counters per row, depth the number of rows, and seeds holds one seed per row.

Hint

Only counters tied for the smallest row value are allowed to grow.

Test cases

case 1

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

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

case 2

in: [3,1,[7],[]]

expected: [[0,0,0]]

case 3

in: [5,2,[10,20],["x","y","x","x"]]

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

case 4

in: [4,3,[1,2,3],["ab","cd","ab"]]

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

Starter codePython

def cms_conservative_update(width, depth, seeds, items):
    # Your code here
    pass

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