Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

1. What is this problem about?

The Insert Delete GetRandom O(1) interview question is a classic systems-design-lite task. You are building a class that manages a collection of unique integers. The primary constraint is that insertion, deletion, and picking a random element must all happen in $O(1)$ average time complexity. This requires a creative combination of data structures to bypass the limitations of standard arrays or hash tables.

2. Why is this asked in interviews?

This is one of the most popular questions at Apple, Uber, and Google. It tests your ability to evaluate the time complexity of different data structure operations. It evaluates if you can identify that an array is necessary for $O(1)$ random access, while a hash map is necessary for $O(1)$ search and deletion. It’s a perfect test of Design interview patterns.

3. Algorithmic pattern used

This solution uses the Array and Hash Map combination.

• The Map acts as an index finder: Value -> Position.
• The Array acts as the storage: Position -> Value.
• To keep the array "gap-less" (so random picking remains $O(1)$), you use the "Swap with Tail" strategy during deletion.

4. Example explanation

Suppose we have values {5, 8, 3}. Array: [5, 8, 3]. Map: {5:0, 8:1, 3:2}.

• getRandom(): Pick random index 0, 1, or 2.
• remove(8):
  • 8 is at index 1.
  • Last element is 3 (at index 2).
  • Move 3 to index 1. Array: [5, 3].
  • Update Map: {5:0, 3:1}. 8 is removed.

5. Common mistakes candidates make

• Inefficient random key: Thinking you can get a random key from a Hash Map in $O(1)$. In most languages, this requires iterating or extra space.
• Forgetting the Map Update: Moving an element in the array but not updating its new index in the Hash Map.
• Linear remove: Not using the "pop from end" trick and instead letting the array shift elements ($O(N)$).

6. Interview preparation tip

This problem is all about "The Tradeoff." Arrays are bad at finding elements but great at random access. Maps are great at finding elements but bad at random access. Combining them is a fundamental trick in building efficient Randomized interview pattern structures.