RandomizedSet — Insert, Delete, GetRandom in O(1)

Problem

Design a data structure that supports:

• insert(val) — inserts val if not present, returns true/false
• remove(val) — removes val if present, returns true/false
• getRandom() — returns a random element with equal probability

All three must run in average O(1) time.

Constraints

• -2^31 ≤ val ≤ 2^31 - 1
• Up to 2 × 10^5 calls
• getRandom is called only when at least one element exists

Hint

Think about what combination of data structures gives you O(1) for all three operations.