How to Solve Insert Delete getRandom O(1)


Insert Delete getRandom O(1) Introduction
Insert Delete getRandom O(1) Introduction
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.
Insert Delete getRandom O(1) Problem
Insert Delete getRandom O(1) Problem
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 itemval
into the set if not already present; returnstrue
if the item was not present,false
otherwise.remove(string val)
Removes an itemval
from the set if present; returnstrue
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.
Example Inputs and Outputs
Example 1
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')
: insertsa
into the set. Returnstrue
as it is inserted successfully.remove('b')
: removesb
from the set. Returnsfalse
as it does not exist in the set.insert('b')
: insertsb
into the set. Returnstrue
as it is inserted successfully.getRandom()
: returns eithera
orb
randomly.remove('a')
: removesa
from the set. Returnstrue
as it is removed successfully.insert('b')
: insertsb
into the set. Returnsfalse
as it already exists in the set.getRandom()
: returnsb
as it is the only item in the set.
Constraints
- At most 2 * 10^5 calls will be made to
insert
,remove
, andgetRandom
. - There will be at least one element in the data structure when getRandom is called.
Insert Delete getRandom O(1) Solutions
Insert Delete getRandom O(1) Solutions
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.
- Hashmap
- add a key:
O(1)
- read a given key:
O(1)
- delete a given key:
O(1)
- read a random key:
O(N)
- get all the keys in the hashmap:
O(N)
- get a random key from the keys:
O(1)
- get all the keys in the hashmap:
- add a key:
- Array
- add an item to the end of the array:
O(1)
- read the value without providing an index:
O(N)
- delete an item from the end of the array:
O(1)
- delete an item from the middle of the array:
O(N)
- need to create a new array and copy all the items from the old array (except the item to be deleted) into the new array:
O(N)
- need to create a new array and copy all the items from the old array (except the item to be deleted) into the new array:
- get a random item:
O(1)
- get a random index within the range of the array length:
O(1)
- read the value for the random index:
O(1)
- get a random index within the range of the array length:
- add an item to the end of the array:
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)
.
Approach 1: Hashmap + Array
As shown in the diagram above, we will use two objects to store the strings:
- An array to store all the strings we currently have.
- A hashmap, with the key as the string and value as the index of the string in the array, so that we can keep track of the positions of the strings inside the array.
For add
operations, we can:
- Check if the string exists in the hash map or not; return
false
if we already have the string. - Append the string to the end of the array. The index of the newly-added string will be
array_length - 1
. In our example, we appendf
to the end of the array and the new array length is6
, which meansf
is stored at index5
. - Add the string into the hashmap with the key as the string itself, and the value as the index. In our example, we add
f
into the hashmap with a value of5
.
For delete
operations, we can:
- Get the index of the string to be deleted from the hashmap. In our example, we are deleting
b
and we retrieve the array-index ofb
from the hashmap, which is1
. - We can then swap the string to be deleted with the last element in the array. In our example, we move
b
to the end of the array, and move the last element (f
) to index1
in the array. - Next, we need to update the keys in the hashmap with their new array index values. In our example, we need to update
b
to point at5
andf
to point at1
. - Lastly, we pop the last element from the array and delete the key from the hashmap.
For getRandom
operations, we can:
- Get the length of the array, knowing the last index of the array is
array_length - 1
. - Generate a random number (
randomIdx
) in the range between0
(the first index) and the last index (inclusive). - Return the element stored at the random index in the array.
Insert Delete getRandom O(1) Python Solution - Hashmap + Array
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/Space Complexity
-
Time complexity:
O(1)
for all the operations. -
Space complexity:
O(N)
- The hashmap takes
O(N)
- The array list takes
O(N)
- The hashmap takes
Practice the Insert Delete getRandom O(1) Problem With Our AI Interviewer
Practice the Insert Delete getRandom O(1) Problem With Our AI Interviewer
Watch These Related Mock Interviews

About interviewing.io
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.