Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

1. What is this problem about?

The Insert Delete GetRandom O(1) interview question asks you to design a data structure that supports three operations in constant average time:

1. insert(val): Inserts an item to the set if not already present.
2. remove(val): Removes an item from the set if present.
3. getRandom(): Returns a random element from the set with equal probability.

2. Why is this asked in interviews?

This is a flagship question for Design interview patterns. Companies like Google, LinkedIn, and Salesforce ask this to see if you can combine multiple data structures to cover each other's weaknesses. A Hash Map is great for $O(1)$ insert/delete but can't do getRandom in $O(1)$. An Array is great for getRandom but $O(N)$ for deletion. The "Hard" part is making them work together.

3. Algorithmic pattern used

This problem follows the Hash Map + Dynamic Array pattern.

• The Array: Stores the actual values. This allows $O(1)$ random access using an index.
• The Hash Map: Stores Value -> Index in Array. This allows $O(1)$ lookups to find where a value is in the array.
• The Swap Trick (Deletion): To delete a value in $O(1)$ from an array, swap it with the last element in the array, update the map for that last element, and then pop the last element.

4. Example explanation

1. insert(10): Array = [10], Map = {10: 0}.
2. insert(20): Array = [10, 20], Map = {10: 0, 20: 1}.
3. remove(10):
   • Find index of 10 in map: 0.
   • Last element is 20 (index 1).
   • Move 20 to index 0: Array = [20, 20].
   • Update map for 20: {20: 0}.
   • Pop last: Array = [20].
4. getRandom(): Generate random index 0. Return 20.

5. Common mistakes candidates make

• $O(N)$ Deletion: Using list.remove(value) in Java or Python, which involves a linear search. You must use the map to find the index and the "swap with last" trick.
• Incorrect Map Update: Forgetting to update the index of the element that was moved during deletion.
• Probability: Using a Hash Map alone and trying to get a random key, which is usually $O(N)$ or not uniformly random in many language implementations.

6. Interview preparation tip

Master the "Swap and Pop" technique. It is the only way to delete from an array in $O(1)$ while maintaining a contiguous structure. This is a vital Array interview pattern for high-performance data structures.