Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
In C++, containers supporting insert with O(1) are vector, list, unordered_map, and unordered_set.
Containers remove by value with O(1) are unordered_map, unordered_set.
Container supporting random access is vector.
So, we can use vector AND unordered_set or unordered_map for the three functions. Then unordered_set or unordered_map? We have to use vector to store the values for the sake of random access with O(1). And a hash container (unordered_set, or unordered_map) to remove with O(1). But we need to figure out how to remove the values from the vector with O(1). Here we can build a connection between the hash container with the vector, so unordered_map wins: reference the same value in the vector by the value’s position.
insert and random access can easily being done with O(1) for vector and unordered_map. But for remove, it affects the unordered_map‘s reference in the vector. The instinct is removing the value from the vector by getting its position from unordered_map. But this will decrease the positions of all descending elements in the vector, which affects the references of the unordered_map. The time complexity could be up to linear O(n) if we do position update in the unordered_map, in worst case. So the instinct is O(n) on average for remove. After struggling.. I ended up finding a clever trick to remove with O(1) online: swapping the element to be removed with the last element in the vector, and updating the last element’s value in the unordered_map with the new position. exactly O(1) on average.