If we just use a hashset (unordered_set), then we can implement both
remove() in O(1) time, by using the
erase() methods. [Refer this link for more details).
The only challenge is with implementing
O(1). Something naive like just
rand() cannot be used on a hashset, so we need to use the
std::advance() method which would inturn result in this being an
Thus, in order to implement
getRandom() as well in O(1), we need to use a different method (of using a hashMap and arraylist) than just using a hashset.
Please let me know if you find something incorrect in this post.