Skip to question

Q132FreeSystemVerilog

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.

Candidate starting point

Implementation scaffold

typedef int int_queue_t[$];

class BucketTopKFrequent;
  int count_by_value[int];
  bit member_by_frequency[int][int];
  int max_frequency = 0;
  int k;
  int sentinel;

  function new(int k, int sentinel = -1);
    if (k <= 0) $fatal(1, "k must be positive");
    this.k = k;
    this.sentinel = sentinel;
    max_frequency = 0;
  endfunction

  function void push(int x);
    int old_frequency;
    int new_frequency;
    // Implement here: update the state for one new observation.
  endfunction

  function int_queue_t snapshot();
    int out[$];
    // Implement here: return the required ordered snapshot.
  endfunction

  function int get_kth();
    int out[$];
    // Implement here: return the required kth value or sentinel.
  endfunction
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.
  5. K is positive. For each distinct value, the total number of push calls is at most 2,147,483,647 during the lifetime of this tracker, so its exact signed 32-bit frequency is representable.
Continue practicing
Q214 · Data StructuresMaintain the top-K most frequent stream valuesMediumPQ145 · Data StructuresTrack top-K frequencies in a sliding windowMediumQ078 · Streaming AlgorithmsReport the top-K opcode frequenciesMediumQ150 · Data StructuresEstimate stream frequencies with a Count-Min SketchMedium