The Insert Delete getRandom O(1) problem involves implementing a class that enables the insertion, deletion, and retrieval of a random element in constant time. Solving this design task requires a strong understanding of the operational time complexities for arrays and hash maps.
Design and implement an efficient sampler that can handle the following operations in constant time:
RandomizedSet()
initializes the RandomizedSet object.insert(string val)
Inserts an item val
into the set if not already present; returns true
if the item was not present, false
otherwise.remove(string val)
Removes an item val
from the set if present; returns true
if the item was present, false otherwise.getRandom()
Returns a random element from the current set of elements.Implement the functions of the class such that each function works in average O(1)
time complexity.
Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], ['a'], ['b'], ['b'], [], ['a'], ['b'], []]
Output: [null, true, false, true, 'b', true, false, 'b']
Explanation:
RandomizedSet
: initialize the objectinsert('a')
: inserts a
into the set. Returns true
as it is inserted successfully.remove('b')
: removes b
from the set. Returns false
as it does not exist in the set.insert('b')
: inserts b
into the set. Returns true
as it is inserted successfully.getRandom()
: returns either a
or b
randomly.remove('a')
: removes a
from the set. Returns true
as it is removed successfully.insert('b')
: inserts b
into the set. Returns false
as it already exists in the set.getRandom()
: returns b
as it is the only item in the set.Constraints
insert
, remove
, and getRandom
.When writing code to store data we have lots of data structures to choose from: arrays / lists, trees, graphs, hashmaps, linked lists, sets, etc. And different data structures have different time complexities for various operations, so depending on what we are trying to achieve, the “right” data structure to use will change. In this problem, we need to achieve O(1)
for insert
, remove
and getRandom
. Because of this requirement, let’s focus on two widely used data structures that have certain O(1)
operations: hashmaps and arrays.
O(1)
O(1)
O(1)
O(N)
O(N)
O(1)
O(1)
O(N)
O(1)
O(N)
O(N)
O(1)
O(1)
O(1)
Back to our problem at hand, based on the time complexities above we can use a hashmap to achieve O(1)
inserts and deletes, but a hashmap alone will not be sufficient for getting a random element. Likewise, we can use an array to get a random element but cannot use an array alone for O(1)
reads and deletes. Since there is no limitation on space usage, we can combine both data structures in our implementation:
Use a hashmap to memorize the positions for all the items in the array to achieve O(1)
read and delete.
Use an array to get a random element with O(1)
.
As shown in the diagram above, we will use two objects to store the strings:
For add
operations, we can:
false
if we already have the string.array_length - 1
. In our example, we append f
to the end of the array and the new array length is 6
, which means f
is stored at index 5
.f
into the hashmap with a value of 5
.For delete
operations, we can:
b
and we retrieve the array-index of b
from the hashmap, which is 1
.b
to the end of the array, and move the last element (f
) to index 1
in the array.b
to point at 5
and f
to point at 1
.For getRandom
operations, we can:
array_length - 1
.randomIdx
) in the range between 0
(the first index) and the last index (inclusive).from random import randint
class RandomizedSet(object):
def __init__(self):
# Key is the string, value is the index of the string inside the array
# Use this hashmap to keep track of the position of the string in the array
self.item_to_index = {}
# The array of strings we have inserted
self.item_arr = []
def insert(self, item):
# Only insert if the string does not already exist
if item in self.item_to_index:
return False
# Append this new string to the end of the array
index = len(self.item_arr)
self.item_to_index[item] = index
self.item_arr.append(item)
return True
def remove(self, item):
# Only remove if the string exists
if item not in self.item_to_index:
return False
# Swap the string to be removed to the end of the array
index = self.item_to_index[item]
last_item = self.item_arr[-1]
self.item_to_index[last_item] = index
self.item_arr[index] = last_item
self.item_arr.pop()
del self.item_to_index[item]
return True
def getRandom(self):
# Randomly pick an index available
index = randint(0, len(self.item_arr) - 1)
return self.item_arr[index]
1from random import randint
2
3class RandomizedSet(object):
4
5 def __init__(self):
6 # Key is the string, value is the index of the string inside the array
7 # Use this hashmap to keep track of the position of the string in the array
8 self.item_to_index = {}
9
10 # The array of strings we have inserted
11 self.item_arr = []
12
13 def insert(self, item):
14 # Only insert if the string does not already exist
15 if item in self.item_to_index:
16 return False
17
18 # Append this new string to the end of the array
19 index = len(self.item_arr)
20 self.item_to_index[item] = index
21 self.item_arr.append(item)
22
23 return True
24
25 def remove(self, item):
26 # Only remove if the string exists
27 if item not in self.item_to_index:
28 return False
29
30 # Swap the string to be removed to the end of the array
31 index = self.item_to_index[item]
32 last_item = self.item_arr[-1]
33 self.item_to_index[last_item] = index
34 self.item_arr[index] = last_item
35 self.item_arr.pop()
36 del self.item_to_index[item]
37
38 return True
39
40 def getRandom(self):
41 # Randomly pick an index available
42 index = randint(0, len(self.item_arr) - 1)
43 return self.item_arr[index]
44
Time complexity: O(1)
for all the operations.
Space complexity: O(N)
O(N)
O(N)
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
Interview prep and job hunting are chaos and pain. We can help. Really.