Count-Min Estimate

Problem

Estimate item frequencies from a Count-Min sketch.

Build the sketch from items exactly as in the update problem, then for each query return the minimum counter over all rows at djb2(seed:query) mod width. Count-Min estimates never underestimate a true count.

Return the list of estimates.

Hint

Taking the minimum over rows cancels most of the collision noise.

Test cases

case 1

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

expected: [2,1,0]

case 2

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

expected: [0]

case 3

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

expected: [2,0]

case 4

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

expected: [3,3]

Starter codePython

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

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