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

DescriptionQ210

Page ↗

Q210FWFollow-up to Q209ASIC interview problem

Use lower-bound insertion for top-K largest

TechniquesSystemVerilogTop KBinary searchLower bound

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Keep the bounded top-K queue sorted and use binary search to locate each insertion position.

Class declarationSystemVerilog

class TopKLargestBinary;
  function new(int k, int sentinel = -1);
  function automatic int lower_bound(int x);
  function void push(int x);
  function int get_kth();
  function void snapshot_desc(ref int out[$]);
endclass

Example input and output

Use this case to check your interpretation

Input

K=3; ascending retained queue=[4,7,9]; insert(8)

Output

lower_bound(8)=2; retained queue=[7,8,9]

Explanation

Binary search locates the insertion point, then the smallest of four candidates is removed to restore the K bound.

Requirements (4)

Implement lower_bound(x) over an ascending queue.
Insert every value while fewer than K observations are retained.
Once full, ignore values no greater than the smallest retained value.
Explain why binary search reduces comparisons but queue insertion still costs O(K).