Insert Delete GetRandom O(1)

Build RandomizedSet, a set of integers that can also hand back a value picked at random.

• RandomizedSet() creates an empty set.
• insert(val) adds val if the set does not hold it yet. It returns true if val was added, and false if it was already there.
• remove(val) takes val out of the set if it is there. It returns true if val was removed, and false if the set did not hold it.
• getRandom() returns one of the values currently in the set, chosen at random so that every value in the set is equally likely.

Every call must take O(1) time on average, however many values the set holds.

Each example lists the calls in the order they are made (the first one creates the object), then each call's arguments, then what each call returns (null for the constructor).

Example 1

Input:
["RandomizedSet","insert","insert","insert","remove","remove","insert","remove","getRandom"]
[[],[4],[9],[4],[4],[4],[-6],[9],[]]
Output: [null,true,true,false,true,false,true,true,-6]

4 and 9 go in, and a second insert(4) changes nothing. 4 comes out once; a second remove(4) finds nothing. After -6 goes in and 9 comes out, -6 is the only value left, so getRandom must return it.

Example 2

Input:
["RandomizedSet","insert","getRandom","remove","insert","getRandom","insert","remove","getRandom"]
[[],[30],[],[30],[30],[],[8],[30],[]]
Output: [null,true,30,true,true,30,true,true,8]

A value that was removed can be inserted again, and then it is back in the set. Each getRandom here sees a set of one value.

Constraints

• -2³¹ <= val <= 2³¹ - 1
• At most 2 × 10⁵ calls are made in total to insert, remove and getRandom.
• In the tests here, getRandom is only called when the set holds exactly one value, so its answer can be checked exactly. Write it for a set of any size anyway: each value present must be equally likely, in O(1) average time.