A rollout service kept the user ids currently in a canary cohort. Product needed three calls: add a member, drop a member, pick one uniform id to receive the experimental payload. The first version was a HashSet. Insert and remove were expected O(1). getRandom walked the iterator to a random offset. Ten thousand ids in staging looked fine. A million live canary members turned every pick into a linear walk, and the sampler lagged the request.

RandomizedSet asks for insert, delete, and getRandom, all expected O(1). A hash table already gives membership. An array already gives list.get(k) for free. A set does not give “the k-th member” as an index. Walking buckets to skip k uses the set and still pays linear time per pick.

This is an interview writeup, not a hashing lecture. The hash-table post owns buckets and collisions. The array post owns contiguous slots. Contains Duplicate only needs membership. Two Sum hashes a value to an index and never moves it. LRU Cache is the same design family — two structures, one identity — but recency, not a uniform pick. Here we only care about storing where each value sits in a dense list so a random index is a get, and a delete does not shift the tail.

The problem

Implement a RandomizedSet. insert(val) adds val if it is new and returns true (a duplicate returns false); remove(val) drops val if it is present and returns true (a miss returns false); getRandom() returns one current member, each equally likely. The usual prompt forbids duplicates.

insert(7)     →  true
insert(4)     →  true
insert(9)     →  true
insert(7)     →  false     already present
remove(4)     →  true
getRandom()   →  7 or 9, each with chance 1/2
remove(4)     →  false
insert(12)    →  true
getRandom()   →  7, 9, or 12, each with chance 1/3

Note: Uniform means every current member, not every value ever inserted. After remove(4), 4 is not in the draw. If they allow duplicates, that is a different structure — say so before you reuse this map.

Scan to delete, or walk the set to pick

A HashSet makes insert and remove expected O(1). getRandom still has to choose an offset and advance the iterator that far — correct, and linear in the live size.

class RandomizedSetScan {
    final Set<Integer> members = new HashSet<>();
    final Random rng = new Random();

    boolean insert(int val) {
        return members.add(val);
    }

    boolean remove(int val) {
        return members.remove(val);
    }

    int getRandom() {
        int skip = rng.nextInt(members.size());
        int i = 0;
        for (int v : members) {
            if (i++ == skip) {
                return v;
            }
        }
        throw new IllegalStateException("empty");
    }
}

The other honest brute is an ArrayList alone: getRandom is list.get(rng.nextInt(size)), but remove scans for the value and list.remove(i) shifts every later slot. At a million canary ids you paid a walk for a question an index map answers in expected constant time: where does this value sit, so I can overwrite that slot from the tail?

Array of values, map of value to index

Keep an ArrayList of the live members and a HashMap from value to that list index. Insert appends and records the new index; delete swaps the target with the last element, pops the tail, and rewrites the swapped value’s index; getRandom is list.get of a uniform nextInt.

Walk insert 7, insert 4, insert 9, then remove 4 — 9 moves into 4’s slot.

insert 7
  list [7]
  map  {7:0}

insert 4
  list [7, 4]
  map  {7:0, 4:1}

insert 9
  list [7, 4, 9]
  map  {7:0, 4:1, 9:2}

remove 4
  4 sits at index 1; last value is 9
  write 9 into index 1, pop the tail
  list [7, 9]
  map  {7:0, 9:1}     4 dropped; 9's index rewritten from 2 to 1

The Java is that class. Random.nextInt and ThreadLocalRandom.current().nextInt are both legal draws; the field below is java.util.Random.

class RandomizedSet {
    final List<Integer> vals = new ArrayList<>();
    final Map<Integer, Integer> idx = new HashMap<>();
    final Random rng = new Random();

    boolean insert(int val) {
        if (idx.containsKey(val)) {
            return false;
        }
        idx.put(val, vals.size());
        vals.add(val);
        return true;
    }

    boolean remove(int val) {
        Integer at = idx.get(val);
        if (at == null) {
            return false;
        }
        int last = vals.size() - 1;
        int tail = vals.get(last);
        vals.set(at, tail);
        idx.put(tail, at);
        vals.remove(last);
        idx.remove(val);
        return true;
    }

    int getRandom() {
        if (vals.isEmpty()) {
            throw new IllegalStateException("empty");
        }
        return vals.get(rng.nextInt(vals.size()));
    }
}

Time is expected O(1) per insert, remove, and getRandom — one map lookup, an append or a swap-and-pop, one get by index. Space is O(n) for the list and the map. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Rewrite the swapped value’s map index. If you pop 4 and leave 9 mapped to the old tail slot, the next remove(9) writes into a hole that no longer exists. Deleting the last element is a no-swap special case, or swap-with-self is fine if you still pop. The code puts tail → at then idx.remove(val), so a last-element delete (tail == val) still drops the key. Remove-then-put would write that key back.

Note: The usual prompt promises getRandom is not called on an empty set. In production you would reject; at the board, ask, then throw.

What interviewers usually poke next

  • Duplicates allowed. Then it is not a RandomizedSet. Map each value to a list (or bag) of indices. Insert always appends. Delete picks one stored index, swap-with-last, and repairs both values’ index lists. Confirm before you reuse the one-slot map.
  • Thread safety. This HashMap and this ArrayList are not concurrent. Two threads racing insert and remove can desync the list from the map. Say you would lock the structure, or that a concurrent design is a different problem.
  • Why HashSet.iterator() is not O(1) random. The iterator walks backing buckets. Skipping k steps is O(k). Hashing does not give a dense 0 .. n-1 index, so there is no get(k) on a set.
  • ArrayList.remove(i) without the swap. Removing a middle slot shifts the tail and is linear. Swap-with-last then remove(last) is the whole point of the map.

You are done with this problem when you can say, out loud, why a set cannot pick the k-th member in O(1), why delete must swap-with-last instead of shifting, and why the swapped value’s map index must be rewritten.