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

DescriptionQ229

Page ↗

Q229FWASIC interview problem

Maintain the top-K most frequent stream values

TechniquesSystemVerilogTop KFrequency mapLazy sorting

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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

Class declarationSystemVerilog

class TopKFrequent;
  function new(int k, 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

K=2; stream=[4,4,2,7,2,4]

Output

snapshot=[4,2]; frequencies=[3,2]; get_kth()=2

Explanation

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

Requirements (4)

push(x) increments the exact frequency of x.
get_kth() returns the Kth-most-frequent value or the sentinel when fewer than K distinct values exist.
snapshot() returns up to K values in descending frequency order.
Equal-frequency tie order may be implementation-defined, but snapshot order must still be nonincreasing by frequency.