380. Insert Delete GetRandom O(1)

Practice Insert Delete GetRandom O(1) for free on NudgeCode: Medium, Array & Hash Table pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Design a set of integers that supports each operation in average O(1) time:

• insert(val) adds val if it is not present; returns true if it was added, false if it was already there.
• remove(val) removes val if present; returns true if it was removed, false if it was not there.
• getRandom() returns a uniformly random element of the set (the set is non-empty when this is called).

Each test is a list of operations and their arguments; the expected output lists what each call returns (null for the constructor). So that answers are deterministic, the tests only call getRandom when the set holds exactly one element — but your implementation should still be uniformly random in general.

Example

["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
->  [null,true,false,true,(1 or 2),true,false,2]

Constraints

• -2^31 <= val <= 2^31 - 1
• Up to 2 * 10^5 calls in total