Skip to question
ASIC.FYI

Q166FreeSystemVerilog

Replace top-K sorting with frequency buckets

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Redesign the exact top-K frequency tracker so a query can walk frequency buckets instead of sorting every distinct key.

Starting point

Question code

class BucketTopKFrequent;
  function new(int k, int sentinel = -1);
  function void push(int x);
  function int get_kth();
  function int[$] snapshot();
endclass
Reviewed example

Trace one case

Input
K=2; stream=[2,3,2,3,1]
Expected output
snapshot=[2,3] with frequencies [2,2]

Both winners occupy frequency bucket two, and the ascending-value tie-break places 2 before 3.

What to cover

Requirements

  1. Keep one exact count and exactly one bucket membership for every value.
  2. On push(x), remove x from its old-frequency bucket and add it to the next bucket.
  3. Walk from the highest frequency downward until K values are collected.
  4. Break ties by ascending numeric value.
Continue practicing
Q229 · Data StructuresMaintain the top-K most frequent stream valuesQ167 · Data StructuresTrack top-K frequencies in a sliding windowQ168 · Data StructuresEstimate stream frequencies with a Count-Min Sketch