Skip to question

Q145FreeSystemVerilog

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.

Candidate starting point

Implementation scaffold

// Implement here: Explain why the full predicate is captured before insertion.

typedef int int_queue_t[$];

class SlidingTopKFrequent;
  int window[$];
  int count[int];
  int sorted[$];
  int k;
  int window_size;
  int sentinel;
  bit dirty;

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

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

  function void rebuild();
    // Implement here: refresh the cached ranking when dirty.
  endfunction

  function int get_kth();
    // Implement here: return the required kth value or sentinel.
  endfunction

  function int_queue_t snapshot();
    int out[$];
    // Implement here: return the required ordered snapshot.
  endfunction
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
Q214 · Data StructuresMaintain the top-K most frequent stream valuesMediumPQ132 · Data StructuresReplace top-K sorting with frequency bucketsMediumQ150 · Data StructuresEstimate stream frequencies with a Count-Min SketchMediumQ182 · Data StructuresUse lower-bound insertion for top-K largestMediumQ042 · Data StructuresReturn the first unique value in a streamEasy