Skip to question
ASIC.FYI

Q209FreeSystemVerilog

Maintain the K largest stream values

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Continuously process integers and retain the K largest values seen so far, including duplicate occurrences.

Starting point

Question code

class TopKLargest;
  function new(int k, int sentinel = -1);
  function void push(int x);
  function int get_kth();
  function int[$] snapshot();
endclass
Reviewed example

Trace one case

Input
K=3; stream=[4,9,1,9,7]
Expected output
snapshot=[9,9,7]; get_kth()=7

Duplicate observations are retained, and the bounded structure discards 4 and 1 as smaller than the final top three.

What to cover

Requirements

  1. Keep at most K real stream values rather than pre-filling the structure with sentinels.
  2. get_kth() returns the Kth largest value or the sentinel before K values have arrived.
  3. snapshot() returns retained values in descending order.
  4. Reject nonpositive K.
Continue practicing
Q210 · Data StructuresUse lower-bound insertion for top-K largestQ229 · Data StructuresMaintain the top-K most frequent stream valuesQ168 · Data StructuresEstimate stream frequencies with a Count-Min Sketch