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]