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.