Skip to question

Q042FreeSystemVerilog

Return the first unique value in a stream

Difficulty
Easy
Topic
Data Structures
Language
SV
Interview prompt

Question

Process a stream of integers and return the earliest value whose current occurrence count is exactly one.

Candidate starting point

Implementation scaffold

class FirstUnique;
  int count[int];
  int order[$];

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

  function bit first_unique(output int x);
    // Implement here: discard duplicate heads and report the oldest unique value.
  endfunction
endclass
Reviewed example

Trace one case

Input
push sequence=[2,3,2,4,3]
Expected output
first unique after each push=[2,2,3,3,4]

Duplicated values remain in the order queue until they reach its head, where lazy cleanup exposes the earliest surviving singleton.

What to cover

Requirements

  1. Track whether each value has appeared zero times, once, or at least twice; duplicate state may saturate at two and must never become unique again.
  2. Append a value to the order queue only on its first occurrence.
  3. Lazily remove duplicated values from the queue head.
  4. first_unique(x) returns 0 when no unique value remains and leaves x unspecified in that case.
Continue practicing
Q154 · Data StructuresExpiring Key-Value StoreHardQ214 · Data StructuresMaintain the top-K most frequent stream valuesMediumP