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

DescriptionQ166

Page ↗

Q166FWFollow-up to Q229ASIC interview problem

Replace top-K sorting with frequency buckets

TechniquesSystemVerilogTop KBucket sortInverse index

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Redesign the exact top-K frequency tracker so a query can walk frequency buckets instead of sorting every distinct key.

Class declarationSystemVerilog

class BucketTopKFrequent;
  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=[2,3,2,3,1]

Output

snapshot=[2,3] with frequencies [2,2]

Explanation

Both winners occupy frequency bucket two, and the ascending-value tie-break places 2 before 3.

Requirements (4)

Keep one exact count and exactly one bucket membership for every value.
On push(x), remove x from its old-frequency bucket and add it to the next bucket.
Walk from the highest frequency downward until K values are collected.
Break ties by ascending numeric value.