Skip to question
ASIC.FYI

Q208FreeSystemVerilog

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.

Starting point

Question code

class RandomizePool;
  function bit insert(int x);
  function bit remove(int x);
  function int get_random();
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
Q142 · Data StructuresImplement a simple least-recently-used cacheQ143 · Data StructuresMake the least-recently-used cache O(1)Q229 · Data StructuresMaintain the top-K most frequent stream values