381. Insert Delete GetRandom O(1) - Duplicates allowed
Asked at LinkedIn
Difficulty
Hard
Time
O(1) average per operation
Space
O(n)
Pattern
Array
Companies
1
Problem
Design a class called RandomizedCollection that stores a multiset of integers. A multiset is like a list: the same value can appear many times, and each copy is a separate item.
Your class must support three operations. insert(val) adds one copy of val and returns true if this is the first copy of that value, otherwise false. remove(val) deletes one copy of val and returns true if a copy existed, otherwise false. getRandom() returns a value picked at random from the current multiset, where a value with k copies must be returned with probability k / n (here n is the total number of items).
All three operations must run in average O(1) time. getRandom is only called when the multiset is not empty.
A multiset with random access
Constraints
- ●
-2^31 <= val <= 2^31 - 1 - ●
At most 2 * 10^5 total calls to insert, remove and getRandom - ●
getRandom is only called when the multiset has at least one item
Examples
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []][null, true, false, true, 2, true, 1]["RandomizedCollection", "insert", "remove", "remove"]
[[], [5], [5], [5]][null, true, true, false]Asked At
1 companies| 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).
Remove by swapping with the last slot
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
O(1) average per operation timeimport 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 runs in O(1) average per operation time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.