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
Quick Answer: This question evaluates the ability to design a data structure that supports constant-time insertions, removals, and uniform random sampling, testing concepts such as hashing, indexed storage, and randomized selection within the coding and algorithms domain.
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; every element currently in the pool must be equally likely. `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`).
**How your code is graded here**
Because `getRandom` is random, the judge cannot check its output when several elements are present. So the console drives your class through a fixed operation log and every `getRandom` in the tests is issued while the pool holds exactly one element — its result is therefore deterministic. You implement a driver `solution(ops, vals)` that replays the log:
- `ops[i]` is one of `"insert"`, `"remove"`, `"getRandom"`.
- `vals[i]` is the argument for `insert`/`remove`; for `getRandom` it is an ignored placeholder (`0`).
- Return a list of ints: `insert`/`remove` push `1` on success or `0` on a no-op; `getRandom` pushes the element it returns.
Internally you must still implement the real O(1) `RandomizedPool` (a value→index hash map plus a dense array, removing by swapping the target with the last element). A stub that only handles single-element pools will fail the churn tests.
**Example**
```
ops = ["insert", "remove", "insert", "remove", "getRandom", "insert", "getRandom"]
vals = [ 1, 2, 2, 1, 0, 2, 0 ]
insert(1) -> true (pool = {1}) -> 1
remove(2) -> false (2 absent; pool = {1}) -> 0
insert(2) -> true (pool = {1, 2}) -> 1
remove(1) -> true (pool = {2}) -> 1
getRandom() -> 2 (only element) -> 2
insert(2) -> false (2 already present) -> 0
getRandom() -> 2 (only element) -> 2
return [1, 0, 1, 1, 2, 0, 2]
```
Constraints
- -2^31 <= val <= 2^31 - 1
- At most 2 * 10^5 total calls across insert, remove, and getRandom
- getRandom is called only when the pool contains at least one element
- In these graded tests every getRandom is called when the pool holds exactly one element, so its result is deterministic
- All three operations must run in average O(1) time (no O(n) scans or set-to-list rebuilds per call)
Examples
Input: (['insert','remove','insert','remove','getRandom','insert','getRandom'], [1,2,2,1,0,2,0])
Expected Output: [1, 0, 1, 1, 2, 0, 2]
Explanation: The worked example. insert(1)=1, remove(2)=0 (absent), insert(2)=1, remove(1)=1, getRandom on {2}=2, insert(2)=0 (duplicate), getRandom on {2}=2.
Input: (['insert','insert','insert','remove','getRandom'], [-5,-5,10,10,0])
Expected Output: [1, 0, 1, 1, -5]
Explanation: Duplicate insert and negatives: insert(-5)=1, insert(-5)=0 (already present), insert(10)=1, remove(10)=1 leaving {-5}, getRandom on {-5}=-5.
Hints
- Keep a dense array of the current values plus a hash map from value to its index in that array. getRandom is then just a random index into the array.
- To remove in O(1), overwrite the target's slot with the last array element, fix that element's index in the map, pop the last slot, and delete the target from the map. Never shift the array.
- Handle the case where the value being removed is itself the last element: the swap becomes a no-op, then the pop and map-delete still leave a consistent state.
- insert returns false (0) and does nothing when the value is already a key in the map; remove returns false (0) when the value is not a key.