A data structure with insert/remove/random in O(1)

Design a data structure that offers the following operations in O(1) time:
insert
remove
contains
get random element

Hints:
Consider a data structure composed of a hashtable H and an array A.
The hashtable keys are the elements in the data structure, and the values are their positions in the array.

Login to see Answer and Coaching Session More interview questions