1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ208

Page ↗

Q208FWASIC interview problem

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

TechniquesSystemVerilogAssociative arraySwap-deleteRandom sampling

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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

Class declarationSystemVerilog

class RandomizePool;
  function bit insert(int x);
  function bit remove(int x);
  function int get_random();
endclass

Example input and output

Use this case to check your interpretation

Input

insert(4), insert(9), remove(4), get_random()

Output

insert results=1,1; remove result=1; get_random()=9

Explanation

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

Requirements (4)

insert(x) returns 1 only when x was absent and inserted.
remove(x) returns 1 only when x was present and removed.
get_random() chooses uniformly among the currently stored values.
Return -1 from get_random() when the pool is empty; callers must treat that value as an API sentinel.