mediumCodingMidSenior
Insert, delete and get-a-uniformly-random-member all have to be O(1). What breaks when you delete from the middle?
Uniform sampling needs a gapless array you can index, so a deletion cannot leave a hole and cannot shift the tail. You overwrite the hole with the last element and shrink by one, which costs a fixed amount of work but silently moves another member, so the map from value to index must be corrected for the element that moved and not only for the one removed.
6 min readUpdated 2026-08-15
Answer
Short answer
Use a dense array for uniform getRandom and a hash map from value to array index for O(1) lookup. On delete, swap the removed slot with the last element, shrink the array, and update the moved element's index before removing the deleted value from the map. The key invariant is that every live value occupies exactly one gapless array position, so random indices remain uniform.
Was this answer helpful?
Likely follow-ups
- Support duplicate values, so a value inserted three times must be returned three times before it is gone. What changes?
- Make get-a-random-member return values weighted by an integer weight instead of uniformly. What is the new bound?
- Remove the requirement for O(1) deletion but add ordered iteration. What structure now?
- Two threads insert and sample concurrently. Which of your invariants is the first to break?
Related questions
- A cache must evict the least recently used entry and every operation has to be O(1). Which two structures do you need, and why is one of them not enough?mediumAlso on hash-map and amortised-complexity5 min
- Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.hardAlso on arrays5 min
- Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?hardAlso on arrays5 min
- Count the subarrays whose elements sum to k, where the values may be negative.mediumAlso on hash-map4 min