Insert Delete GetRandom O(1)

Idea

The insert() and remove() are pretty straightforward to implement with O(1) time, just use a Hash Map
The difficult part is getting an value randomly from hashmap in O(1) time. Based on what in know it is impossible to get a value randomly from the hashmap in O(1) time
In this case, we need to rely on something else, what data structure allows us to get a value randomly in O(1) time? That is right, array!
But removing a number from array is O(n)! Ho can we solve this? We can make use a replace & pop trick, where we use the last element to replace the element to be deleted. We put the array index of each element as the value in the hashmap