Interview : Suggest a data structure which optimizes insertion, deletion and random value generation

Question

Suggest a data structure which can optimize all 3 below operations :

1. Insertion
2. Deletion
3. Return a random value from set of existing values

Assume that you are putting integers/numbers.

Answer 1

Dynamic Array + Hashmap = O(1) for all three operations

• Insertion

Append to the tail of Array O(1), and add a value-index pair to Hashmap O(1).

• Deletion

Find the index by the value in Hashmap O(1), delete by the index in array and swap the last element into the slot O(1), and update the value-index pair for the (used-to-be) last element O(1).

• Return random

Generate a random index for the array O(1).

Answer 2

O(1) in python:

from collections import defaultdict
from random import choice

class DataStructure(list):
    def __init__(self):
        self.values = []
        self.locations = defaultdict(list)

    def add(self, val):
        i = len(self.values)
        self.locations[val].append(i)
        self.values.append(val)
        assert self.values[i] == val

    def delete(self, val):
        locations = self.locations[val]
        if locations:
            i = locations.pop()
            self.values[i] = self.values[-1]
            self.values.pop()

    def random(self):
        return choice(self.values)

ds = DataStructure()

ds.add(3)
ds.add(5)
print ds.random()
print ds.random()
print ds.random()
print ds.random()
ds.delete(5)
print ds.random()
ds.delete(3)

"""
5
3
3
5
3
"""

See Time Complexities of List and Dict operations to Confirm

( Note pop is O(1) since we pop from the end of the list)