Constant-Time Insert, Remove, and Uniform Random Sampling

A data-sampling service maintains a dynamically changing pool of integer example IDs. Examples are continuously added and retired, and the service must repeatedly draw a uniformly random example from the current pool. All three operations must run in average O(1) time.

Implement a class RandomizedPool supporting:

• insert(val) — inserts val into the pool if it is not already present. Returns true if val was inserted, false if it was already present.
• remove(val) — removes val from the pool if it is present. Returns true if val was removed, false if it was not present.
• getRandom() — returns a uniformly random element from the current pool. Each element currently in the pool must have an equal probability of being returned. getRandom is only called when the pool is non-empty.

The pool contains no duplicates: inserting a value that is already present is a no-op (returning false).

Example

pool = RandomizedPool()
pool.insert(1) -> true (pool = {1})
pool.remove(2) -> false (2 not present; pool = {1})
pool.insert(2) -> true (pool = {1, 2})
pool.getRandom() -> 1 or 2, each with probability 1/2
pool.remove(1) -> true (pool = {2})
pool.insert(2) -> false (2 already present; pool = {2})
pool.getRandom() -> 2 (only element)

Constraints

• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 calls in total will be made across insert, remove, and getRandom
• getRandom is called only when the pool contains at least one element
• All three operations must run in average O(1) time — solutions that take O(n) per operation (for example, scanning a list to remove an element, or converting a hash set to a list on every getRandom call) are not acceptable