Skip to question
ASIC.FYI

Q229FreeSystemVerilog

Maintain the top-K most frequent stream values

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Process a stream of integers and report the K most frequent distinct values seen so far.

Starting point

Question code

class TopKFrequent;
  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=[4,4,2,7,2,4]
Expected output
snapshot=[4,2]; frequencies=[3,2]; get_kth()=2

Exact counts place 4 first and 2 second; value 7 has only one occurrence.

What to cover

Requirements

  1. push(x) increments the exact frequency of x.
  2. get_kth() returns the Kth-most-frequent value or the sentinel when fewer than K distinct values exist.
  3. snapshot() returns up to K values in descending frequency order.
  4. Equal-frequency tie order may be implementation-defined, but snapshot order must still be nonincreasing by frequency.
Continue practicing
Q167 · Data StructuresTrack top-K frequencies in a sliding windowQ166 · Data StructuresReplace top-K sorting with frequency bucketsQ143 · Data StructuresMake the least-recently-used cache O(1)