Skip to question

Q169FreeSystemVerilog

Insert, remove, and sample in average O(1)

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Design a set-like data structure for integers that supports insertion, removal, and uniformly random sampling, with every operation taking average O(1) time.

Candidate starting point

Implementation scaffold

class RandomizePool;
  int index_by_value[int];
  int values[$];

  function bit insert(int x);
    // Implement here: insert one absent value and maintain its index.
  endfunction

  function bit remove(int x);
    int idx;
    int last_value;
    // Implement here: remove the value and repair the reverse index.
  endfunction

  function int get_random();
    int pick;
    // Implement here: return a uniformly sampled live value or the specified empty sentinel.
  endfunction
endclass
Reviewed example

Trace one case

Input
insert(4), insert(9), remove(4), get_random()
Expected output
insert results=1,1; remove result=1; get_random()=9

After swap-removal only 9 remains, so uniform sampling has exactly one possible result.

What to cover

Requirements

  1. insert(x) returns 1 only when x was absent and inserted.
  2. remove(x) returns 1 only when x was present and removed.
  3. get_random() chooses uniformly among the currently stored values.
  4. Return -1 from get_random() when the pool is empty; callers must treat that value as an API sentinel.
Continue practicing
Q195 · Data StructuresAssociative-array traversalEasyQ094 · Data StructuresImplement a simple least-recently-used cacheMedium