Insert Delete GetRandom O(1)

Problem: Design a data structure that supports all the following operations in average O(1) time: insert(val) - inserts an item val if not already present; remove(val) - removes an item val if present; getRandom() - returns a random element from the current set of elements (each element must have the same probability of being returned).

Constraints: All operations (insert, remove, getRandom) must run in average O(1) time.

Example: insert(1) -> true; insert(2) -> true; remove(1) -> true; insert(2) -> false (already present); getRandom() -> 2.

Approach: Maintain a dynamic array (for O(1) getRandom via random index) plus a hash map from value to its index in the array. To remove in O(1), swap the element to remove with the last element in the array, update the map, then pop the last element -- avoiding an O(n) shift.