Insert Delete GetRandom O(1) - Duplicates allowed
Asked at LinkedIn
Problem
Insert Delete GetRandom O(1) - Duplicates allowed asks you to design a multiset that supports insert, remove, and returning a random element, all in average O(1) time, where each element is returned with probability proportional to how many copies it has. It extends the classic array-plus-hash-map design to handle duplicates.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all LinkedIn questions → |
How to Think About It
An array makes getRandom trivial: pick a random index. The challenge is deleting from the middle of the array in O(1).
Classic trick: to remove index i, move the last element into slot i and pop the end. Order in the array does not matter, so this is fine.
Key insight for duplicates: map each value to a set of indices where it appears in the array. Remove any one index for the value, then fix up the index set of the moved last element.
Careful ordering during remove: add i to the last value's index set before discarding the old last index. If the removed element is itself the last one, adding then discarding correctly leaves no stale index.
Because every copy occupies its own array slot, a uniform random index automatically gives each value a probability proportional to its count.
Optimal Approach
State: vals (array) and idx (value -> set of indices).
insert(val): add len(vals) to idx[val], append val. Return true if val now has exactly one index.
remove(val): if idx[val] is empty, return false. Pop any index i from idx[val]. Let last = vals[-1]. Set vals[i] = last, add i to idx[last], discard len(vals) - 1 from idx[last], pop vals. Return true.
getRandom(): return vals[random index].
Time: O(1) average for every operation. Space: O(n).
What Trips People Up in Real Interviews
Mapping each value to a single index, as in the no-duplicates version. With duplicates you need a set (or list) of indices per value.
Discarding the last index before adding i. When the removed element is the last element, that order leaves a stale index pointing past the end of the array.
Using a list of indices and removing an arbitrary one from the middle — that is O(k). A hash set keeps it O(1).
Returning the wrong boolean from insert. It is true only when the value was not already present.
Solution Code
import random
from collections import defaultdict
class RandomizedCollection:
def __init__(self):
self.vals = []
self.idx = defaultdict(set)
def insert(self, val):
self.idx[val].add(len(self.vals))
self.vals.append(val)
return len(self.idx[val]) == 1
def remove(self, val):
if not self.idx[val]:
return False
i = self.idx[val].pop()
last = self.vals[-1]
self.vals[i] = last
self.idx[last].add(i)
self.idx[last].discard(len(self.vals) - 1)
self.vals.pop()
return True
def getRandom(self):
return random.choice(self.vals)Frequently Asked Questions
What is the Insert Delete GetRandom O(1) - Duplicates allowed problem?
Insert Delete GetRandom O(1) - Duplicates allowed asks you to design a multiset that supports insert, remove, and returning a random element, all in average `O(1)` time, where each element is returned with probability proportional to how many copies it has. It extends the classic array-plus-hash-map design to handle duplicates.
How do you solve Insert Delete GetRandom O(1) - Duplicates allowed?
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) - Duplicates allowed?
Insert Delete GetRandom O(1) - Duplicates allowed is asked at LinkedIn. It is a hard difficulty problem.
What are common mistakes on Insert Delete GetRandom O(1) - Duplicates allowed?
- Mapping each value to a single index, as in the no-duplicates version. With duplicates you need a set (or list) of indices per value.
- Discarding the last index before adding `i`. When the removed element is the last element, that order leaves a stale index pointing past the end of the array.
- Using a list of indices and removing an arbitrary one from the middle — that is `O(k)`. A hash set keeps it `O(1)`.
- Returning the wrong boolean from `insert`. It is true only when the value was not already present.