Insert Delete GetRandom O(1)

Design a container that supports inserting a value, removing a value, and fetching a uniformly random value from the current contents, with every operation running in average O(1) time.

Implement a class RandomizedSet with the following members:

• RandomizedSet() — initializes the container as empty.
• insert(val) — inserts val into the container if it is not already present, and returns true. If val is already present, does nothing and returns false.
• remove(val) — removes val from the container if it is present, and returns true. If val is not present, does nothing and returns false.
• getRandom() — returns a value currently in the container, chosen uniformly at random among all elements present at that moment. This method is only ever called when the container is non-empty, and it must run in average O(1) time as well.

The container never stores duplicate values — think of it as backing a mathematical set. Each element, when present, must have an equal chance of being returned by getRandom(), regardless of insertion or removal history.

Examples

Example 1:

Input:

["RandomizedSet", "insert", "insert", "insert", "remove", "getRandom", "insert", "getRandom"]
[[], [7], [13], [7], [13], [], [21], []]

Output:

[null, true, true, false, true, 7, true, <7 or 21>]

Explanation:

• insert(7) adds 7 and returns true.
• insert(13) adds 13 and returns true.
• insert(7) finds 7 already present, so it returns false and changes nothing.
• remove(13) removes 13 and returns true, leaving only {7}.
• getRandom() must now return 7, the only element left.
• insert(21) adds 21, giving {7, 21}.
• getRandom() returns either 7 or 21, each with probability 1/2.

Example 2:

Input:

["RandomizedSet", "remove", "insert", "remove", "remove"]
[[], [5], [5], [5], [5]]

Output:

[null, false, true, true, false]

Explanation:

• remove(5) is called on an empty set, so nothing is removed and it returns false.
• insert(5) adds 5 and returns true.
• remove(5) removes 5 and returns true, leaving the set empty.
• remove(5) is called again on the now-empty set, so it returns false.

Constraints

• Values are 32-bit signed integers, each within the range -2^31 to 2^31 - 1.
• Up to 2 * 10^5 calls to insert, remove, and getRandom combined will be made.
• getRandom is guaranteed to be called only when the container currently holds at least one element.