Skip to question
ASIC.FYI

Q168FreeSystemVerilog

Estimate stream frequencies with a Count-Min Sketch

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Trade exact counts for bounded memory by implementing a Count-Min Sketch that updates and estimates integer frequencies.

Starting point

Question code

class CountMinSketch #(
  parameter int WIDTH = 128,
  parameter int DEPTH = 4
);
  function void push(int x);
  function int unsigned estimate(int x);
endclass
Reviewed example

Trace one case

Input
push(A) three times; push(B) once; estimate(A)
Expected output
estimate(A) >= 3 and never below the true count 3

Taking the minimum across hash rows limits collision inflation; saturating counters prevent wraparound undercounts.

What to cover

Requirements

  1. Maintain one fixed-width counter row for each distinct row-specific hash salt.
  2. push(x) increments one addressed counter in every row.
  3. estimate(x) returns the minimum addressed counter across rows.
  4. Assume each true per-key frequency is at most 32'hffff_ffff; saturate counters so wraparound cannot create an undercount within that bound.
Continue practicing
Q229 · Data StructuresMaintain the top-K most frequent stream valuesQ166 · Data StructuresReplace top-K sorting with frequency bucketsQ209 · Data StructuresMaintain the K largest stream values