Constant-Time Insert, Remove, and Uniform Random Sampling
Company: xAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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