Skip to question
ASIC.FYI

Q210FreeSystemVerilog

Use lower-bound insertion for top-K largest

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

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

Starting point

Question code

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
Reviewed example

Trace one case

Input
K=3; ascending retained queue=[4,7,9]; insert(8)
Expected output
lower_bound(8)=2; retained queue=[7,8,9]

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

What to cover

Requirements

  1. Implement lower_bound(x) over an ascending queue.
  2. Insert every value while fewer than K observations are retained.
  3. Once full, ignore values no greater than the smallest retained value.
  4. Explain why binary search reduces comparisons but queue insertion still costs O(K).
Continue practicing
Q209 · Data StructuresMaintain the K largest stream valuesQ229 · Data StructuresMaintain the top-K most frequent stream valuesQ273 · Data StructuresReturn the first unique value in a stream