Insert Delete GetRandom O(1)
Implement insertDeleteGetRandom
Design a data structure that supports insert(val), remove(val), and getRandom() — each in average O(1) time. getRandom() returns an element chosen at random (with equal probability) from among the elements currently stored.
To make this testable with a single function call, this version takes a fixed sequence of operations, replaying them in order and returning the result of every operation as an array — insert/remove return 1 for success or 0 for failure, and getRandom returns the selected value. Since a real getRandom() is non-deterministic, each getRandom call here instead takes an explicit randomIndex naming which position in the current set to return.
Example 1:
Input: ops = ["insert","insert","insert","remove","getRandom","insert","getRandom","remove"], args = [[10,0],[20,0],[10,0],[20,0],[0,0],[30,0],[0,1],[10,0]]
Output: [1,1,0,1,10,1,30,1]
Example 2:
Input: ops = ["insert","getRandom"], args = [[5,0],[0,0]]
Output: [1,5]
Example 3:
Input: ops = ["insert","insert","remove"], args = [[7,0],[7,0],[9,0]]
Output: [1,0,0]
+ 6 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ number of operations ≤ 10 - ●
Each operation is "insert", "remove", or "getRandom" - ●
0 ≤ val ≤ 200 - ●
getRandom's randomIndex is always a valid index into the current set at that point (0 ≤ randomIndex < current size) - ●
insert and remove use val (randomIndex is unused/0); getRandom uses randomIndex (val is unused/0)
ops =
["insert", "insert", "insert", "remove", "getRandom", "insert", "getRandom", "remove"]
args =
[[10,0], [20,0], [10,0], [20,0], [0,0], [30,0], [0,1], [10,0]]