Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1) is a classic data structure design problem (LeetCode 380) that requires implementing a class with insert, remove, and getRandom operations, all averaging O(1) time. It matches the tags Array, Hash Table, Math, Design, and Randomized, and appears in LinkedIn interviews as noted in various coding platforms.[11][16]

Full Problem Statement

Implement the RandomizedSet class:

• RandomizedSet(): Initializes the RandomizedSet object.
• bool insert(int val): Inserts val into the set if it doesn't exist already; returns true if insertion succeeded, false otherwise.
• bool remove(int val): Removes val from the set if present; returns true if removal succeeded, false otherwise.
• int getRandom(): Returns a random element from the current set of elements (guaranteed at least one element exists). Each element should have an equal probability of being returned.[12][13][11]

All operations must run in average O(1) time complexity.[16][11]

Input/Output Examples

Example 1:

Input: ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]<br> [[],[1],[2],[2],[],[1],[2],[]]

Output: [null,true,false,true,"2",true,false,"2"]

Explanation:

• RandomizedSet() initializes the object.
• insert(1) → returns true (1 inserted).
• remove(2) → returns false (2 not present).
• insert(2) → returns true (2 inserted).
• getRandom() → returns 2 (either 1 or 2 randomly; here 2).
• remove(1) → returns true (1 removed).
• insert(2) → returns false (2 already present).
• getRandom() → returns 2 (only element).[11][12]

Constraints

• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.[12][16][11]