Design a container supporting insert(x), delete(x) and getRandom() uniformly at random, all in O(1) expected time, with duplicate values allowed. State what each operation does and where the difficulty is.

Design a container supporting insert(x), delete(x) and getRandom() uniformly at random, all in O(1) expected time, with duplicate values allowed. State what each operation does and where the difficulty is.

Approach: Uniform sampling wants a contiguous array, deletion wants a hash map. Store both and make deletion repair the array in constant time.

Keep a dynamic array of the elements plus a hash map from value to the set of indices holding it. getRandom draws a uniform index into the array, which is O(1) and exactly uniform because every element occupies exactly one slot. insert appends and records the new index. delete looks up any index i of x, swaps the array's last element y into slot i, pops the array, then updates the map by removing i from the index set of x and rewriting the stored index of y from the old last position to i. The whole repair is O(1). The difficulty is that a naive delete leaves a hole, and compacting the array is O(n) while tombstones make getRandom non-uniform. Duplicates force the map to hold a set of indices rather than one index, and the swap with last must be careful when x and y are equal or when i is already the last slot, since updating in the wrong order deletes the index just written.

Follow-up: How would you extend it to sample proportional to a weight attached to each element while keeping updates polylogarithmic?

Key concepts: dynamic array, hash map, swap with last, uniform sampling.