A count-min sketch estimates item frequencies in a stream with a fixed-size counter grid. Hash collisions may make an estimate too large, but the estimate never falls below the true count.
Design a CountMinSketchEstimator class:
CountMinSketchEstimator() creates a stateless estimator.int[] estimate(int width, int depth, string[] items, string[] queries) records the stream and returns one estimate per query.
Use the unsigned 32-bit polynomial hash h = (h * 31 + charCode) & 0xFFFFFFFF. The sketch has depth rows and width columns. In row r, an item maps to:
Recording an item increments its counter in every row. Its estimate is the minimum of the addressed counters across all rows. Build a fresh sketch on every call.
Example 1:
Input:
Output:
Explanation: The row minima are 3, 2, 1, and 0, matching the true frequencies in this case.
Example 2:
Input:
Output:
Explanation: Each occurrence increments one cell per row; the minimum queried counters recover the shown estimates.
Constraints
1 <= width <= 10^41 <= depth <= 20width * depth <= 2 * 10^50 <= items.length, queries.length <= 10^4- Every item is a nonempty printable ASCII string of length at most
100. - At most
100 calls are made to estimate.
Estimate Frequencies with Count-Min Sketchmedium