If we just use a hashset (unordered_set), then we can implement both `insert()`

and `remove()`

in O(1) time, by using the `insert()`

and `erase()`

methods. [Refer this link for more details).

The only challenge is with implementing `getRandom()`

in `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 `O(n)`

method.

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.

Thanks,

BatCoder.