Skip to question

Q176FreeSystemVerilog

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.

Candidate starting point

Implementation scaffold

// Implement here: Explain why the full predicate is captured before insertion.

typedef int int_queue_t[$];

class TopKLargest;
  int values[$]; // ascending, real observations only
  int k;
  int sentinel;

  function new(int k, int sentinel = -1);
    if (k <= 0) $fatal(1, "k must be positive");
    this.k = k;
    this.sentinel = sentinel;
  endfunction

  function void push(int x);
    int position = 0;
    bit full_before_insert;
    // Implement here: update the state for one new observation.
  endfunction

  function int get_kth();
    // Implement here: return the required kth value or sentinel.
  endfunction

  function int_queue_t snapshot();
    int out[$];
    // Implement here: return the required ordered snapshot.
  endfunction
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
Q182 · Data StructuresUse lower-bound insertion for top-K largestMediumQ214 · Data StructuresMaintain the top-K most frequent stream valuesMediumPQ071 · Data StructuresDynamic arrays and queuesEasyQ219 · Data StructuresQueue methodsEasyPQ094 · Data StructuresImplement a simple least-recently-used cacheMedium