Design a set with O(1) insert, delete and getRandom

01The design, in the six-step framework

1. Requirements and use cases

A classic that Google still asks in phone screens, often as "design a data structure" rather than by its LeetCode name, so the candidate has to find the two-structure trick alone.

• A caller inserts a value; the call reports whether it was new.
• A caller removes a value; the call reports whether it was present.
• A caller asks for a uniformly random element among those present.
• All three operations run in O(1) average time.
• Follow-up: allow duplicates, with the random pick weighted by multiplicity.

Out of scope: ordering, iteration order guarantees, thread safety unless asked. Non-functional constraints: O(1) for every operation including the random pick, which rules out anything that needs a scan; memory linear in the number of elements; and the randomness source must be injectable so tests are deterministic.

2. Core entities and relationships

• RandomizedSet: the public object; owns a list of values and a map from value to its index in the list.
• Random: the injected source of randomness; the standard library instance in production, a seeded one in tests.
• RandomizedMultiset: the duplicates variant; the map holds a set of indexes per value.

The set composes the list and the map; they are two views of one collection, and the class's only job is to keep them in step. The list gives random access by index, which is what getRandom needs; the map gives O(1) position lookup, which is what remove needs. Neither alone suffices. The multiset is a separate class, not a flag on the set, because its invariant differs (indexes per value) and keeping both in one class doubles every branch. That choice is KISS: two small classes beat one clever one.

3. Interfaces and key methods

import random
from typing import Generic, Hashable, Optional, TypeVar

V = TypeVar("V", bound=Hashable)


class RandomizedSet(Generic[V]):
    def __init__(self, rng: Optional[random.Random] = None) -> None:
        """rng is injected so tests can seed it."""

    def insert(self, value: V) -> bool:
        """True if value was not present."""

    def remove(self, value: V) -> bool:
        """True if value was present; O(1) by swapping with the last element."""

    def get_random(self) -> V:
        """Uniform over present values; raises IndexError when empty."""

    def __len__(self) -> int: ...
    def __contains__(self, value: object) -> bool: ...

Invariants: index[v] == i exactly when values[i] == v; the list has no gaps; and every value appears at most once. Uniformity follows from the list having no gaps: randrange(len(values)) picks every present value with equal probability.

4. Design patterns and the choices behind them

Swap-with-last deletion

The force is O(1) removal from a list, which normally shifts everything after the removed slot. Moving the last element into the hole and popping the tail is O(1) and keeps the list gap-free. The map must then be updated for the moved element, which is the one step people forget. The rejected alternative is leaving a tombstone in the list; it breaks uniformity (tombstones can be picked) and makes get_random a retry loop with no bound. This is the same "two structures pointing at each other" idea as the LRU structure, with a list in place of a linked list because random access matters here.

Injected randomness

The force is testability. random.random() as a global makes the random pick untestable except statistically. Passing a random.Random instance lets a test seed it and assert exact outputs, and lets production share one generator. This is the smallest example of designing for unit tests.

Why uniformity is a correctness property here

The force is that "random" is easy to get subtly wrong. The requirement is that every present element is chosen with probability exactly 1 / n. With a gap-free list, randrange(n) gives that directly, and the proof is one line. Any design that picks a random slot and retries on a hole has an unbounded worst case and, if the retry is done carelessly (for example by stepping to the next occupied slot), skews probability towards elements after large holes. Interviewers often ask for this argument out loud, so the invariant "no gaps" is worth stating as the reason uniformity holds, not just as an implementation detail.

P(pick v) = 1 / len(values) for every v present, because every index in [0, n) holds exactly one present value

Hashability only

Values need hash and equality, nothing more. The API returns booleans from insert and remove because the callers in the original problem want to know whether anything changed; raising instead would force try/except around the most common path.

5. Core flow and code

Flow for remove(5) when values = [3, 5, 8]:

1. Look up 5 in the map: index 1.
2. Take the last value, 8, and write it into slot 1; update index[8] = 1.
3. Pop the tail and delete 5 from the map. The list is now [3, 8], still gap-free.

When the removed element is itself the last one, step 2 writes the value onto its own slot and updates its own index, which is harmless; no special case is needed.

import random
from typing import Dict, Generic, Hashable, List, Optional, Set, TypeVar

V = TypeVar("V", bound=Hashable)


class RandomizedSet(Generic[V]):
    def __init__(self, rng: Optional[random.Random] = None) -> None:
        self.values: List[V] = []
        self.index: Dict[V, int] = {}
        self.rng = rng or random.Random()

    def insert(self, value: V) -> bool:
        if value in self.index:
            return False
        self.index[value] = len(self.values)
        self.values.append(value)
        return True

    def remove(self, value: V) -> bool:
        i = self.index.pop(value, None)
        if i is None:
            return False
        last = self.values[-1]
        self.values[i] = last
        if last != value:                 # moved element keeps its map entry correct
            self.index[last] = i
        self.values.pop()
        return True

    def get_random(self) -> V:
        if not self.values:
            raise IndexError("get_random on empty set")
        return self.values[self.rng.randrange(len(self.values))]

    def __len__(self) -> int:
        return len(self.values)

    def __contains__(self, value: object) -> bool:
        return value in self.index


class RandomizedMultiset(Generic[V]):
    """Duplicates allowed; get_random is weighted by multiplicity because every copy occupies a slot."""

    def __init__(self, rng: Optional[random.Random] = None) -> None:
        self.values: List[V] = []
        self.positions: Dict[V, Set[int]] = {}
        self.rng = rng or random.Random()

    def insert(self, value: V) -> bool:
        new = value not in self.positions
        self.positions.setdefault(value, set()).add(len(self.values))
        self.values.append(value)
        return new

    def remove(self, value: V) -> bool:
        slots = self.positions.get(value)
        if not slots:
            return False
        i = slots.pop()
        last_i = len(self.values) - 1
        last = self.values[last_i]
        if i != last_i:
            self.values[i] = last
            self.positions[last].remove(last_i)
            self.positions[last].add(i)
        self.values.pop()
        if not slots:
            del self.positions[value]
        return True

    def get_random(self) -> V:
        return self.values[self.rng.randrange(len(self.values))]


if __name__ == "__main__":
    s: RandomizedSet[int] = RandomizedSet(random.Random(7))
    assert s.insert(3) and s.insert(5) and s.insert(8) and not s.insert(5)
    assert s.remove(5) and s.values == [3, 8] and s.index == {3: 0, 8: 1}
    assert s.remove(8) and not s.remove(8) and len(s) == 1   # removing the tail
    assert s.get_random() == 3
    m: RandomizedMultiset[str] = RandomizedMultiset(random.Random(1))
    m.insert("a"); m.insert("a"); m.insert("b")
    assert m.remove("a") and m.remove("a") and not m.remove("a") and m.get_random() == "b"

6. Extensions, concurrency and what interviewers probe

• The moved element. Forgetting to update the map entry of the element swapped into the hole is the single most common bug; the test asserts the map after a middle removal for that reason.
• Removing the last element. The code handles it without a branch; be ready to explain why writing a value onto itself is fine.
• Duplicates. The multiset keeps a set of slots per value so any copy can be removed in O(1); the random pick is automatically weighted because each copy holds a slot.
• Weighted picks with explicit weights are a different structure (prefix sums and binary search, O(log n)); see the frequency container.
• Thread safety. One lock around the three methods; the swap-and-pop is two writes that must not interleave with a read.
• What to test first. Insert three, remove the middle, check both structures; then a seeded sequence of random picks over a known list.

02Where this question was reported

• LeetCode Discuss · LeetCode 380 (Medium), Google-tagged, freq 46.4; duplicates-allowed variant also tagged
• Land the Lab · 'Set with constant-time insert, delete and get random'
• spacecomplexity.ai · Sample onsite problem: structure with insert/delete/getRandom in O(1)