Insert Delete GetRandom O(1)

Problem

Design a data structure RandomizedSet supporting three operations, each in average O(1) time:

• insert(val): add val if it is not already present; return True if it was added, False otherwise.

• remove(val): remove val if present; return True if it was removed, False otherwise.

• getRandom(): return one of the currently stored values, chosen uniformly at random. This is only called when the set is non-empty.

• Values are 32-bit signed integers.

• Expect on the order of a few hundred thousand operations in total, in any mix.

Examples

• insert(7) → True; insert(7) → False; remove(3) → False; insert(3) → True; remove(7) → True; insert(7) → True; getRandom() → 3 or 7, each with probability 1/2.
• insert(40), insert(50), insert(60), insert(70); remove(70) → True (removing the element at the end of the array); remove(70) → False; the set is now {40, 50, 60}.
• insert(-9) → True; remove(-9) → True; insert(-9) → True; getRandom() → -9. A value can be re-added after removal.

Hints

1. A hash set gives O(1) insert and remove but cannot pick a uniformly random element in O(1). An array can pick a random index but cannot remove an arbitrary element in O(1). Combine them.
2. Removing from the middle of an array is O(n) only because of shifting. What if the element you remove is always the last one?
3. Keep an array of values plus a map from value to its index. To remove, swap the target with the last element, update the map for the moved element, then pop.