316. Insert Delete GetRandom O(1)
Design a container RandomizedSet that stores distinct integers and supports all three of these operations in average O(1) time:
insert(val)— addvalif it is absent. Returntrueif it was added,falseif it was already stored.remove(val)— deletevalif it is present. Returntrueif it was deleted,falseif it was not there.get_random()(getRandomin C++/Java) — return one of the currently stored values, each with equal probability. It is only ever called while the set is non-empty.
The tension: a hash set gives O(1) insert/remove but no O(1) uniform random pick; a plain array gives O(1) random pick but O(n) delete. The point of the problem is to get both at once.
Your class is driven by a scripted sequence of operations. The driver prints the boolean returned by each insert/remove. Random output can't be compared directly, so each get_random is validated instead of diffed: the driver prints ok when the value you return is currently stored, and bad otherwise. Uniformity itself isn't graded — but a genuinely O(1) get_random essentially forces the intended design.
Example 1:
Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()
Output: [true, false, true, ok, true, false, ok]
Explanation: insert(1) adds 1. remove(2) fails — 2 was never stored. insert(2) makes the set {1, 2}, so getRandom may return either, and both are valid (ok). After remove(1) the set is {2}; inserting 2 again returns false, and the final getRandom must return 2.
Example 2:
Input: insert(5), insert(5), remove(5), remove(5), insert(5)
Output: [true, false, true, false, true]
Explanation: The second insert fails (5 is already stored) and the second remove fails (5 is already gone); re-inserting after a successful remove succeeds again.
Constraints:
- -2³¹ ≤ val ≤ 2³¹ - 1
- At most 2 × 10⁵ operations in one script.
- getRandom is only called while the set is non-empty.
- Every operation must run in O(1) average time.
Hints:
Store the values in a dynamic array so getRandom is just 'pick a random index'. The hard part is remove: deleting from the middle of an array is O(n) — unless you don't care about order.
Keep a hash map from value → its array index. To remove a value, overwrite its slot with the array's last element, update that moved element's map entry, then pop the last slot. Every step is O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()
Expected output: [true, false, true, ok, true, false, ok]