1. Prompt
An ad system has N candidates, with each weight representing a relative chance of selection. Initialization is followed by millions of single-item draws, so each draw should be close to O(1) while batch weight updates remain possible. Design an alias table and cover zero weights, floating-point error, and random-number boundaries.
2. Constraints and clarifications
- Start with one draw with replacement; sampling without replacement and single-weight updates are extensions.
- Weights are non-negative and their sum must be positive; a zero-weight item must never be selected.
- The sampler may use a uniform integer and a uniform real in
[0, 1). - Rebuilding in
O(N)after a weight batch is acceptable, but an old table cannot represent new weights.
3. Core approach
Scale each weight to pi = wi * N / sum(w), whose average is 1. Maintain prob and alias arrays of length N. A bucket returns itself with probability prob[i]; otherwise it jumps to alias[i]. During preprocessing, put values below 1 in small and values above 1 in large; pair one from each side, fill the small bucket, and return the leftover capacity to the large bucket until all buckets are complete.
Sampling first chooses a bucket uniformly, then compares one uniform real with prob[i]. The total area assigned to each original item equals its normalized probability, so its long-run frequency is proportional to its weight.
4. Reference implementation
build(weights):
n = len(weights)
scale = n / sum(weights)
scaled = [w * scale for w in weights]
prob = array(n)
alias = array(n)
small, large = [], []
for i, value in enumerate(scaled):
(small if value < 1 else large).append(i)
while small and large:
s = small.pop()
l = large.pop()
prob[s] = scaled[s]
alias[s] = l
scaled[l] -= 1 - scaled[s]
(small if scaled[l] < 1 else large).append(l)
for i in small + large:
prob[i] = 1
alias[i] = i
return prob, alias
sample(prob, alias, rng):
i = rng.uniform_int(0, len(prob))
return i if rng.uniform01() < prob[i] else alias[i]5. Complexity and correctness
Preprocessing takes O(N) time and space. Each sample needs one uniform bucket choice, one comparison, and at most one array lookup, so it is O(1). Clamp prob into [0, 1] after residual floating-point error; define the integer range as half-open so the last bucket is not missed.
Validation requires more than a few draws. Generate enough samples, compare each observed frequency with w_i / sum(w), and use confidence intervals or a chi-squared test to detect significant bias. Replace a rebuilt table atomically so a sampler never observes a mixed version.
6. Follow-ups and traps
- Alias tables suit static or batch-updated distributions. For frequent single-weight changes, a Fenwick tree or segment tree may be a better fit.
- Overflowing the total before normalization breaks ratios; use wider precision or scale first.
- “O(1)” excludes rebuild cost and does not make the random-number generator free.
- A zero total defines no distribution. Reject it instead of returning every item uniformly.
7. Further reading
Compare prefix sums with binary search, Fenwick trees, reservoir sampling, and alias tables: prefix structures support dynamic updates with O(log N) sampling, reservoirs suit streams, and alias tables trade O(N) preprocessing for high-throughput O(1) draws.
8. Interview scoring points
Can build the small and large buckets
The candidate should explain scaling weights to average capacity 1 and moving leftover capacity between a small and a large bucket.
Can prove the sampling probability
They should show how uniform bucket selection plus one alias jump gives each item its target total area rather than merely reciting code.
Can handle numeric and boundary cases
They should cover zero weights, zero total, floating-point clamping, half-open random ranges, and atomic table replacement.
Can choose the right data structure
They should compare batch rebuild cost with dynamic updates and know when to use a Fenwick tree or prefix sums instead of alias tables.