Shuffle deck fairly

This interview question pairs two classic algorithmic tasks centered on randomness: fairly shuffling a fixed set of items, and fairly sampling from a stream whose length is not known in advance. The first part asks you to reason about how to generate a truly uniform permutation of a deck using only basic random number primitives, something that often appears in discussions of simulations, games, and Monte Carlo methods. The second part shifts to a streaming setting, common in large-scale data processing, where you must design a one-pass procedure that gives every position in a file the same chance of being chosen despite not knowing how long the file is.

Solving it draws on discrete probability, permutations, and careful reasoning about conditional probabilities as new items are encountered. Candidates are expected to recognize when uniformity fails, and to argue rigorously that their procedure assigns exactly equal probability to all outcomes. Interviewers look for a clean algorithm, attention to edge cases and implementation feasibility, and a proof-style explanation that tracks how probabilities evolve step by step rather than relying on intuition alone.

What it tests

The core structure behind both problems is uniform random selection from a set whose size may or may not be known in advance. The mathematical principle is that to achieve true uniformity, each possible outcome (ordering or selection) must have exactly the same probability, which requires careful control over how randomness is introduced and applied. For shuffling, this means ensuring that every permutation is reachable with equal likelihood, not just that every card is moved randomly. For sequential selection, it means that the probability of keeping any particular item must adjust dynamically as more items are seen, so that at the end, each has the same chance. This uniformity is preserved by either assigning independent random values (which breaks ties with probability zero in the continuous case) or by using a process that updates probabilities as the set grows (as in reservoir sampling).