Randomized design problems have an unusual property: a solution can be subtly wrong in a way that still looks right. A biased shuffle still returns a permutation. A skewed picker still returns valid indices. The tests pass, the output looks plausible, and the distribution is wrong.

So these problems are really about two things:

1. Composing structures for $O(1)$ random access — a hash map gives lookup, but only a dense array gives uniform random choice.
2. Being able to argue that a distribution is uniform — because “it looks random” is not a proof, and the classic off-by-one here silently destroys uniformity.

What you’ll learn

• The swap-with-last trick: $O(1)$ deletion from an array, which is what makes $O(1)$ random selection possible.
• Prefix sums plus binary search for weighted picking.
• Fisher-Yates, why the loop bound is inclusive, and a concrete demonstration of what goes wrong when it is not.
• Reservoir sampling — picking uniformly from a stream of unknown length.
• Three real LeetCode problems solved in the browser: 380, 528, 384.

The cue

Trick 1 — swap with last

To pick uniformly at random in $O(1)$ you need a dense array — contiguous, no holes — so that random.randrange(len(arr))random.randrange(len(arr)) is a valid index.

But deleting from the middle of an array is $O(n)$ because everything shifts. The trick: you do not care about order, so overwrite the hole with the last element and shrink.

import random
 
 
class RandomizedSet:
    def __init__(self):
        self.values = []          # dense array -> O(1) uniform random choice
        self.index = {}           # value -> its position in `values`
 
    def insert(self, val):
        if val in self.index:
            return False
        self.index[val] = len(self.values)
        self.values.append(val)
        return True
 
    def remove(self, val):
        if val not in self.index:
            return False
        i = self.index[val]
        last = self.values[-1]
        self.values[i] = last          # move the last element into the hole
        self.index[last] = i           # UPDATE ITS RECORDED POSITION
        self.values.pop()
        del self.index[val]
        return True
 
    def getRandom(self):
        return random.choice(self.values)

import random
 
 
class RandomizedSet:
    def __init__(self):
        self.values = []          # dense array -> O(1) uniform random choice
        self.index = {}           # value -> its position in `values`
 
    def insert(self, val):
        if val in self.index:
            return False
        self.index[val] = len(self.values)
        self.values.append(val)
        return True
 
    def remove(self, val):
        if val not in self.index:
            return False
        i = self.index[val]
        last = self.values[-1]
        self.values[i] = last          # move the last element into the hole
        self.index[last] = i           # UPDATE ITS RECORDED POSITION
        self.values.pop()
        del self.index[val]
        return True
 
    def getRandom(self):
        return random.choice(self.values)

All three operations are $O(1)$ average, with $O(n)$ space.

Trick 2 — prefix sums plus binary search

For weights [1, 3][1, 3], index 1 must be picked three times as often. Build the cumulative weights and throw a dart at the total:

import bisect
import random
 
 
class WeightedPicker:
    def __init__(self, w):
        self.prefix = []
        total = 0
        for x in w:
            total += x
            self.prefix.append(total)     # e.g. [1, 3] -> [1, 4]
        self.total = total
 
    def pickIndex(self):
        target = random.random() * self.total     # uniform in [0, total)
        return bisect.bisect_right(self.prefix, target)

import bisect
import random
 
 
class WeightedPicker:
    def __init__(self, w):
        self.prefix = []
        total = 0
        for x in w:
            total += x
            self.prefix.append(total)     # e.g. [1, 3] -> [1, 4]
        self.total = total
 
    def pickIndex(self):
        target = random.random() * self.total     # uniform in [0, total)
        return bisect.bisect_right(self.prefix, target)

The prefix array turns weights into adjacent intervals on a number line: index 0 owns [0, 1)[0, 1), index 1 owns [1, 4)[1, 4). A uniform dart lands in each interval with probability proportional to its width — which is exactly the weight. bisect_rightbisect_right finds which interval contains the dart.

Construction $O(n)$, each pick $O(\log n)$, space $O(n)$.

Trick 3 — Fisher-Yates, and the bias trap

To shuffle uniformly, walk from the end and swap each position with a random earlier-or-equal position:

import random
 
 
def shuffle(a):
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)      # INCLUSIVE of i -- element may stay put
        a[i], a[j] = a[j], a[i]
    return a

import random
 
 
def shuffle(a):
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)      # INCLUSIVE of i -- element may stay put
        a[i], a[j] = a[j], a[i]
    return a

For reset()reset(), keep an untouched copy of the original and return a copy or reassign, being careful not to hand back a list that later shuffles will mutate.

Reservoir sampling

When the input is a stream of unknown length you cannot pick an index up front. Reservoir sampling keeps one candidate and replaces it with decreasing probability:

import random
 
 
def pick_one(stream):
    chosen = None
    for count, item in enumerate(stream, start=1):
        if random.randrange(count) == 0:      # probability 1/count
            chosen = item
    return chosen

import random
 
 
def pick_one(stream):
    chosen = None
    for count, item in enumerate(stream, start=1):
        if random.randrange(count) == 0:      # probability 1/count
            chosen = item
    return chosen

Why it is uniform: item kk is chosen at step kk with probability $1/k$, and then survives every later step j > kj > k with probability $1 - 1/j = (j-1)/j$. Multiplying:

$\frac{1}{k} \cdot \frac{k}{k+1} \cdot \frac{k+1}{k+2} \cdots \frac{n-1}{n} = \frac{1}{n}$

The terms telescope, so every item ends with probability exactly $1/n$ — without ever knowing nn. That is the argument to give; it generalises to keeping kk samples by replacing a random reservoir slot with probability $k/count$.

The variant map

Practice — real LeetCode problems

LC 380 — Insert Delete GetRandom O(1) · Medium

Problem. Implement a set with insert(val)insert(val), remove(val)remove(val) (both returning whether the set changed) and getRandom()getRandom() returning a uniformly random element. All three must be $O(1)$ average.

Constraints. -2^31 <= val <= 2^31 - 1-2^31 <= val <= 2^31 - 1, up to 2 * 10^52 * 10^5 calls, and getRandomgetRandom is only called when the set is non-empty.

Examples. insert(1)insert(1) gives TrueTrue, remove(2)remove(2) gives FalseFalse, insert(2)insert(2) gives TrueTrue, getRandom()getRandom() gives 11 or 22, remove(1)remove(1) gives TrueTrue, insert(2)insert(2) gives FalseFalse

LC 528 — Random Pick with Weight · Medium

Problem. Given an array ww where w[i]w[i] is the weight of index ii, implement pickIndex()pickIndex() returning index ii with probability w[i] / sum(w)w[i] / sum(w).

Constraints. 1 <= len(w) <= 10^41 <= len(w) <= 10^4, 1 <= w[i] <= 10^51 <= w[i] <= 10^5, and pickIndexpickIndex may be called up to 10^410^4 times.

Examples. w = [1]w = [1] always gives 00 · w = [1, 3]w = [1, 3] gives 00 about 25% of the time and 11 about 75%

LC 384 — Shuffle an Array · Medium

Problem. Implement shuffle()shuffle() returning a uniformly random permutation of the array, and reset()reset() returning the original configuration. All permutations must be equally likely.

Constraints. 1 <= len(nums) <= 501 <= len(nums) <= 50, values in [-10^6, 10^6][-10^6, 10^6], up to 10^410^4 calls.

Examples. For [1,2,3][1,2,3]: shuffle()shuffle() returns some permutation, reset()reset() returns [1,2,3][1,2,3], and over many calls each of the 6 permutations appears about equally often.

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Removing the only element (LC 380) — last == vallast == val; verify the map is left clean and the structure still works afterwards.
• Remove then re-insert — catches stale index entries.
• Removing a value that is already last — the swap is a no-op but the map updates must still be right.
• Single weight (LC 528) — [1][1] must always return 00.
• Very uneven weights — [1, 100000][1, 100000]; index 0 is rare but must remain reachable.
• Single-element array (LC 384) — the shuffle loop body never runs; still valid.
• Two-element array — the smallest case where bias is observable.
• Duplicate values when shuffling — permutations are indistinguishable, so count distinct arrangements carefully if testing.
• resetreset aliasing — never return the internal original list by reference.

Recap

• Uniform random choice needs a dense array. Swap-with-last makes deletion $O(1)$ without holes — and you must update the moved element’s recorded index.
• A hash map alone cannot do this: sets have no $O(1)$ uniform choice.
• Weighted picks: prefix sums turn weights into adjacent intervals; a uniform dart plus binary search selects proportionally. Keep the target/bisect conventions consistent.
• Fisher-Yates with an inclusive bound. randint(0, i - 1)randint(0, i - 1) is the classic bug and produces only 2 of 6 permutations on a 3-element array — while still always returning a valid permutation.
• Reservoir sampling handles unknown-length streams; the telescoping product is the uniformity proof.
• Randomized bugs are invisible to validity checks. Test distributions, and be ready to argue uniformity rather than assert it.

Next: Design Trackers and Feeds — time-windowed counters, merged feeds, and the systems-flavoured end of design questions.