Skip to question
ASIC.FYI

Q167FreeSystemVerilog

Track top-K frequencies in a sliding window

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Report the exact top-K frequencies using only the last N pushed values; a value leaving the window must stop contributing.

Starting point

Question code

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

Trace one case

Input
window_size=4; stream=[1,2,1,3,2]
Expected output
current window=[2,1,3,2]; top value=2 with frequency 2

The first 1 expires before the final snapshot, so only counts from the last four pushes participate.

What to cover

Requirements

  1. Append each new value to an order queue and increment its count.
  2. When the queue exceeds N, pop the oldest value and decrement its count.
  3. Delete count entries that reach zero.
  4. Use only the current window for get_kth() and snapshot(), including while the window is partially filled.
  5. Break equal-frequency ties by ascending numeric value.
Continue practicing
Q229 · Data StructuresMaintain the top-K most frequent stream valuesQ166 · Data StructuresReplace top-K sorting with frequency bucketsQ168 · Data StructuresEstimate stream frequencies with a Count-Min Sketch