1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ167

Page ↗

Q167FWFollow-up to Q229ASIC interview problem

Track top-K frequencies in a sliding window

TechniquesSystemVerilogTop KSliding windowFrequency map

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements5 checkpoints

Problem

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

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

window_size=4; stream=[1,2,1,3,2]

Output

current window=[2,1,3,2]; top value=2 with frequency 2

Explanation

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

Requirements (5)

Append each new value to an order queue and increment its count.
When the queue exceeds N, pop the oldest value and decrement its count.
Delete count entries that reach zero.
Use only the current window for get_kth() and snapshot(), including while the window is partially filled.
Break equal-frequency ties by ascending numeric value.