# Insert, Delete, GetRandom O(1)

## Original Problem

1 | # Design a data structure that supports all following operations in average O(1) time. |

## Approach

The first reactions are always to build a hash map ds, but the thing about hash map is that hashing values are unique to the data stored, mening there is no way to generate a hashing value correspond to a data without knowing what the data is.

Therefore, we must use a ds with index support to get a random data out of the data set, like linked list! But the removal will be an O(n) process.

Now itâ€™s obvious we need hash map for the fast lookup time, and list for its indexing support. For this problem we must use both.

A list where all data is stored, and a hashmap to store the corresponding location(index) of that data in the list array.

To delete, we can simply find the index of the data using hashmap, and swap it with the last value in the list array, and pop it off. Constant actions = Constant time complexity

## Implmentation

1 | import random |