DS with insert, delete and getRandomElement in O(1)

Problem Statement

Design a data structure that allows insert, delete and getRandomElement() 
in constant time i.e. O(1).

Solution

Insert and delete in O(1) needs a hashmap and get random element on O(1) suggests some kind of array access.

We can take a HashMap H and an array A with max size. Now HashMap should have key as the element to be inserted and value as the position of the element in the array, also keep a last pointer telling the index of the last element in the array.

Insert is simple, increment last pointer and add the new element at last position and add <element, last> in the hashmap.

Delete is a little tricky, First get the position of element in the array from hashmap, remove the element from hashmap, swap A[pos] and A[last] in array, decrement last pointer and update the position of swapped element in the hashmap.

delete(element){
  int pos =  map.get(element);
  map.remove(element);
  Swap A[pos], A[last];
  last--;
  map.put(A[pos], pos);//update position to new pos
}

getRandomElement() is simple, get a random number between 0 and last(both including) and return A[random number]