Count-Min Sketch

Write codeHard32 minDatabricks and Snowflake style

Your task

Implement a Count-Min Sketch for approximate frequency counting. It has depth rows and width columns of integer counters, all starting at 0. For row r (0-indexed) and item key (a string), the column is c(r, key) = (sum((ord(ch) * (r + 7)) for ch in key) * 2654435761 + r * 0x9E3779B1) % width. To add a key with count n, increment counters[r][c(r,key)] by n for every row r. The estimated frequency of a key is the MINIMUM over all rows of counters[r][c(r,key)] (the min reduces overestimation from collisions). Process operations ["add", key, n] and ["estimate", key]; return the list of estimate results in order. depth and width are positive integers.

Examples

count_min_sketch(depth: int, width: int, ops: list[list]) -> list[int]
Example 1
Inputcount_min_sketch(3, 1000, [["add", "apple", 2], ["add", "apple", 3], ["estimate", "apple"], ["estimate", "banana"]])
Output[5, 0]