Count-Min Sketch Update

Problem

Update a Count-Min sketch and return the final counter matrix.

width is the number of counters per row and depth is the number of rows; seeds gives one hash seed per row. Each item increments the counter djb2(seed:item) mod width in every row, where seed and item are joined by a colon.

Return the matrix as a list of rows.

Hint

Every item updates exactly one counter per row, chosen by that row's seed.

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"]]

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

case 4

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

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

Starter codePython

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

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