Back to DSA sheet
Insert Delete Get Random O(1)
MediumArraysDesign a structure supporting insert(val) (false if already present), remove(val) (false if absent), and getRandom() returning a uniformly random current element, all in average O(1).
Input format (stdin): the first line has q. Each next line is 'insert x', 'remove x', or 'getRandom'. For insert/remove print true/false. To keep getRandom deterministic for testing, this harness prints the element at the current last index instead of a random one.
Examples
Input: 5
insert 1
remove 2
insert 2
getRandom
remove 1
Output: true
false
true
2
true
Operations return their booleans; getRandom prints a current element.
Constraints
- -2^31 <= val <= 2^31 - 1
- getRandom is only called when non-empty
Sheets
NeetCode 250
insert-delete-get-random-o-1.cpp1 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.