Insert Delete GetRandom O(1)

Problem Design a set-like data structure supporting insert, remove and getRandom, each in average O(1) time, where getRandom returns any currently-held element with uniform probability.

Input / Output

• Input: a sequence of calls — insert(val), remove(val), getRandom().
• Output: insert returns true if val was not already present; remove returns true if val was present; getRandom returns one stored element chosen uniformly at random.

Constraints

• All three operations must be average O(1); amortised is acceptable for insert, since the backing array grows.
• The structure holds distinct values only — no duplicates.
• getRandom is only called when the structure is non-empty.
• Every stored element must be equally likely; a design that skews toward recently inserted elements is a bug even if the timing is right.

Example

• insert(1) → true; insert(2) → true; insert(2) → false (already present); getRandom() → 1 or 2 with probability 1/2 each; remove(1) → true; getRandom() → 2 every time.