Question

link

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:

1. random access

HashMap is best for:

1. Searching
   1. insert
   2. remove

So the answer is array + hashmap:

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

2. 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.

3. Get random can be done by returning a random index from the array.

4. 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.