Daily bit(e) of C++ | O(1) randomized container
Daily bit(e) of C++ #245, Common interview problem: O(1) randomized container.
Today, we will look at a common C++ interview problem: O(1) randomized container.
Implement a data structure that provides the following O(1) operations:
insert one copy of a value (multiple copies allowed)
remove one copy of a value
get a random value with uniform distribution (taking into account the number of copies)
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/oYYT359df.
Solution
Our main constraint is the get operation. To get a random value with uniform distribution, our only realistic option is picking an index into a random-access container.
This then dictates our approach for the rest of the operations, with the remove operation being the complicated one. Removing a value from the middle of a random-access container is an O(n) operation.
However, since we will only access the values using the random-get operation, we don’t care about the order of elements, so we can use the swap-erase trick of swapping the to-be erased element with the last element in the container and only then erasing it, which is an O(1) operation.
To achieve all this, we will need to keep track of the mapping of elements to their indexes using unordered containers.
