1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ168

Page ↗

Q168FWFollow-up to Q229ASIC interview problem

Estimate stream frequencies with a Count-Min Sketch

TechniquesSystemVerilogCount-Min SketchHashingApproximation

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

push(A) three times; push(B) once; estimate(A)

Output

estimate(A) >= 3 and never below the true count 3

Explanation

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

Requirements (4)

Maintain one fixed-width counter row for each distinct row-specific hash salt.
push(x) increments one addressed counter in every row.
estimate(x) returns the minimum addressed counter across rows.
Assume each true per-key frequency is at most 32'hffff_ffff; saturate counters so wraparound cannot create an undercount within that bound.