Insert Delete GetRandom O(1)
Asked at Apple, Uber
Problem
Design a data structure that supports insert, delete, and getRandom operations, all in O(1) average time. This problem tests your ability to combine a hash map with an array to achieve constant-time operations.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Key insight: use an array for O(1) random access and a hash map for O(1) lookups. The hash map stores each value's index in the array. The array stores the actual values.
Insert: append the value to the array. Store its index in the hash map. Both are O(1).
Delete: this is the tricky part. You cannot leave a gap in the array. Swap the element to delete with the last element, then remove the last element. Update the hash map for the swapped element. This avoids shifting and keeps it O(1).
Visual walkthrough for operations: insert(1), insert(2), insert(3), remove(2), getRandom:
After insert(1): array=[1], map={1:0}
After insert(2): array=[1,2], map={1:0, 2:1}
After insert(3): array=[1,2,3], map={1:0, 2:1, 3:2}
Remove(2): swap index 1 with index 2. array=[1,3,2] then pop. array=[1,3]. map={1:0, 3:1}
getRandom: return array[random(0,1)]. Array has 2 elements.
Why the swap trick works: instead of deleting from the middle (which leaves a gap), you move the last element into the gap and delete the last element. The hash map for the moved element is updated to its new index.
Optimal Approach
Use an array vals and a hash map index_map mapping each value to its index in the array.
Insert(val): append val to vals, store its index in index_map. O(1).
Remove(val): get the index from index_map. Swap vals[index] with vals[-1]. Update index_map for the swapped element. Pop the last element. Remove val from index_map. O(1).
GetRandom(): return vals[random(0, len(vals)-1)]. O(1).
Walkthrough with insert(1), insert(2), remove(1), getRandom:
- insert(1): vals=[1], index_map={1:0}
- insert(2): vals=[1,2], index_map={1:0, 2:1}
- remove(1): index=0. Swap vals[0] with vals[1]: vals=[2,1]. Pop: vals=[2]. Update index_map: {2:0}. Remove 1: {2:0}
- getRandom: vals=[2], return 2.
Time: all O(1) average. Space: O(n) for array and hash map.
What Trips People Up in Real Interviews
Forgetting to update the hash map after the swap. When you move the last element into the deleted position, you must update its index in the hash map. Otherwise, future deletes will use a stale index.
Deleting from the wrong position. Always swap with the LAST element, not an arbitrary element. Swapping with a middle element does not avoid the gap problem.
Using a HashSet instead of a HashMap. You need the index mapping for O(1) delete. A HashSet cannot tell you where the element is in the array.
Not handling the case where the element to delete IS the last element. In that case, no swap is needed, just pop and remove from the map. The swap logic should check for this.
getRandom must be truly uniform. Each element in the array should have equal probability. Since you always maintain a contiguous array, random_index = random(0, len-1) gives uniform distribution.
Solution Code
import random
class RandomizedSet:
def __init__(self):
self.vals = []
self.index_map = {}
def insert(self, val):
if val in self.index_map:
return False
self.index_map[val] = len(self.vals)
self.vals.append(val)
return True
def remove(self, val):
if val not in self.index_map:
return False
idx = self.index_map[val]
last = self.vals[-1]
self.vals[idx] = last
self.index_map[last] = idx
self.vals.pop()
del self.index_map[val]
return True
def getRandom(self):
return random.choice(self.vals)Frequently Asked Questions
What is the Insert Delete GetRandom O(1) problem?
Design a data structure that supports insert, delete, and getRandom operations, all in `O(1)` average time. This problem tests your ability to combine a hash map with an array to achieve constant-time operations.
How do you solve Insert Delete GetRandom O(1)?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Insert Delete GetRandom O(1)?
Insert Delete GetRandom O(1) is asked at Apple, Uber. It is a medium difficulty problem.
What are common mistakes on Insert Delete GetRandom O(1)?
- Forgetting to update the hash map after the swap. When you move the last element into the deleted position, you must update its index in the hash map. Otherwise, future deletes will use a stale index.
- Deleting from the wrong position. Always swap with the LAST element, not an arbitrary element. Swapping with a middle element does not avoid the gap problem.
- Using a `HashSet` instead of a `HashMap`. You need the index mapping for `O(1)` delete. A `HashSet` cannot tell you where the element is in the array.
- Not handling the case where the element to delete IS the last element. In that case, no swap is needed, just pop and remove from the map. The swap logic should check for this.
- getRandom must be truly uniform. Each element in the array should have equal probability. Since you always maintain a contiguous array, `random_index = random(0, len-1)` gives uniform distribution.