Insert, delete and get-a-uniformly-random-member all have to be O(1). What breaks when you delete from the middle?

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.

The sampling requirement picks the structure

Two of the three operations are what a hash set already does. Insert and delete in expected constant time, no ordering, no duplicates. So read the third requirement first, because it is the only one that constrains anything.

Uniform sampling means every member has the same chance of being returned. The cheap way to get that is to draw an integer in the range zero to size, exclusive, and use it as a position. Which requires storage where every position from zero to size minus one holds a member, and where indexing is a single address calculation.

A hash set gives neither. Walking it to a random offset is O(n). Choosing a random bucket and then an element inside it is O(1) but not uniform, because buckets hold different numbers of elements, so members sharing a crowded bucket are drawn less often than a member sitting alone in its own.

So you need an array with no gaps, plus a map from value to that value's position in the array so that deletion does not have to search for it. The array serves sampling, the map serves locating, and the interesting part of the question is what happens when those two have to be kept in step.

Deleting from the middle, and the two things you may not do

Removing a member from position i when i is not the last position leaves the array in a state the sampling argument forbids, and both obvious repairs are disallowed.

Leaving a hole breaks uniformity and correctness together: a drawn index may land on a vacancy, and the array's length no longer equals the member count. Shifting everything after i down by one closes the hole but touches up to n elements, so the deletion is O(n), and it also moves every one of those elements, invalidating that many map entries.

The repair that respects both bounds is to overwrite position i with whatever is in the last position, then shrink the array by one. One element moves, one entry needs correcting, and the array stays gapless.

private final List<Integer> values = new ArrayList<>();
private final Map<Integer, Integer> index = new HashMap<>();   // value -> its position in `values`

boolean insert(int value) {
    if (index.containsKey(value)) return false;
    index.put(value, values.size());
    values.add(value);                       // appends at the end - amortised O(1)
    return true;
}

boolean remove(int value) {
    Integer i = index.get(value);
    if (i == null) return false;
    int last = values.get(values.size() - 1);
    values.set(i, last);
    index.put(last, i);                      // the moved element's new home - the line most often missing
    values.remove(values.size() - 1);
    index.remove(value);                     // must follow the put above, not precede it
    return true;
}

int getRandom() {
    return values.get(random.nextInt(values.size()));   // uniform over positions, so uniform over members
}

The line that is missing and the order that is wrong

Two distinct defects live in that removal, and interviewers watch for them separately because they fail in different ways.

The first is omitting index.put(last, i) entirely. The array is now correct and the map is not: the moved element still claims the position it used to occupy, which is the position now beyond the end or occupied by someone else. Nothing throws. The next remove of that moved value writes the tail element over a position that does not belong to it, and the collection quietly starts losing and duplicating members. This is the classic version of the bug because the array looks right when you print it.

The second is subtler and only fires on one input. Suppose the value being removed is the one already at the last position. Then i is the final index and last equals value. With the order above, index.put(last, i) rewrites the entry to the value it already had and index.remove(value) then deletes it. Correct.

Reverse those two lines and the same input breaks. index.remove(value) deletes the entry, then index.put(last, i) puts it straight back, pointing at a position that the following shrink has just removed. The map now claims a member the array does not hold, getRandom can never return it, and the next attempt to remove it indexes past the end of the array. One input, one line ordering, and the failure surfaces somewhere else entirely.

Say the general rule rather than memorising the sequence: correct the moved element first, then delete the removed one, because when they are the same element the deletion has to win.

Stating the bounds honestly

Insertion is amortised O(1), not worst case. A dynamic array appends in constant time until it is full, and the append that triggers a resize copies every element, which is O(n) for that one call. Doubling the capacity makes the average constant over any sequence of appends, and saying "amortised" is the difference between a correct claim and an approximately correct one.

Deletion and sampling are O(1) worst case on the array side. Both depend on the hash map, which is expected constant time rather than worst case, so the whole structure is best described as expected constant time per operation with insertion additionally amortised.

The randomness deserves one sentence too. Uniformity over members follows from uniformity over indices, so it inherits whatever the generator gives you. random.nextInt(bound) in Java rejects and redraws to distribute evenly across the range. Writing random.nextInt() % size instead introduces modulo bias, which makes the lower indices marginally more likely whenever the size does not divide the generator's range - a defect that no test of the data structure would catch.

What the structure quietly destroyed

Swap-and-pop reorders the array. After the first deletion, position order has nothing to do with insertion order, and there is no way to recover it.

That is usually fine, because the array exists only to be indexed at random. It matters the moment somebody iterates the structure and depends on what they see, or serialises it and compares two runs, or writes a test that asserts an order. Naming the property you gave up is the part of the answer that reads as engineering rather than as puzzle-solving.

Duplicates change the shape more than they look like they should

The natural extension is to allow a value to be present several times. The map's value becomes a set of positions rather than one position, and removal picks any position from that set. Sampling stays untouched.

The awkward part is the swap. When the tail element moves into position i, you must remove exactly i from the moved value's position set and insert the new one, and if the moved value and the removed value are the same the two edits act on the same set in an order that matters again. A hash set gives O(1) expected removal of a specific position, so the bound survives; the invariant maintenance roughly doubles in length, which is why this is a separate question rather than a footnote.

Note also that sampling now returns values in proportion to their multiplicity. If the requirement was uniform over distinct values, the whole approach has to change.

The array exists so that a random index is a random member, and every difficulty in this problem comes from the fact that keeping it gapless moves an element you were not asked to touch.

---

© 2026 Preptima. Originally published at preptima.com.