### Question

Design a data structure where the following 3 functions at O(1):

```
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
```

### Solution

Array is best for:

- random access

HashMap is best for:

- Searching
- insert
- remove

So the answer is **array + hashmap**:

Insertion can be done by appending to the array and adding to the hash-map.

Deletion can be done by first looking up and removing the array index in the hash-map, then

**swapping the last element with that element in the array**.Get random can be done by returning a random index from the array.

All operations take O(1).

Note how hashmap is used:

insert(value): append the value to array and let i be it’s index in A. Set H[value]=i.

Hashmap stores value’s index in the array - that is to say: **this DS does not support inserting duplicating values**.

Finally, when we delete, we swap the last element to replace the gap. This is an nice idea!

#### follow-up

what if we want to get the top x% number?

Well, heap of course. And note that **Heap size is auto-increasing**:

PriorityQueue is unbounded, it can grow as big as your memory allows, and it will grow automatically when needed. The initialCapacity parameter is just a hint to reserve room for that many elements initially.