Woodstock Blog

a tech blog for general algorithmic interview questions

[Google] Data Structure of Insert, Remove, GetRandom



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

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


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!


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.