Coding interview: How do you implement a uniform in-place array shuffle?

Problem and context

Implement reset() to restore the original order and shuffle() to return a uniformly random permutation. The question tests randomized algorithms, in-place swaps, random-number boundaries, and testability; the same pattern appears in sampling, drawing lots, and test fixtures.

What the interviewer is testing

• Choosing Fisher–Yates instead of repeatedly swapping arbitrary random positions.
• Sampling index i only from the portion that has not been fixed.
• Distinguishing inclusive and half-open random APIs to avoid bias or overflow.
• Keeping an immutable baseline so reset() is unaffected by shuffles.
• Explaining O(n) time, O(1) extra space, and uniformity.
• Discussing seeded PRNGs, empty arrays, duplicate values, and statistical test limits.

Clarifying questions to ask

• Should shuffle() return a new array or mutate and return the working array?
• Must reset() return a defensive copy so callers cannot mutate internal state?
• Is the random source injectable, or is a cryptographically secure source required?
• Are duplicate values allowed, and are equal values at different positions distinct permutations?
• Do we need thread safety, reproducible seeds, or cryptographic unpredictability?
• Does the input require streaming or constant auxiliary space?

30-second answer framework

“I keep an original snapshot and a working array. For i from the last index down to one, I sample a uniform j in [0, i] and swap a[i] with a[j]. Each pass fixes one position, so the running time is O(n) and auxiliary space is O(1). reset() returns a copy of the snapshot; the random source can be injected for reproducibility and statistical tests.”

Step-by-step deep dive

Step 1: Isolate state. Copy the input into original and working; reset() copies original again so external references cannot change the baseline.

Step 2: Define the random bound. Let i decrease from n - 1 to 1. With a half-open API call randomInt(i + 1) to obtain 0..i; with an inclusive API pass 0 and i explicitly.

Step 3: Swap in place. Swap working[i] and working[j]; position i is now fixed and no same-sized temporary array is created.

Step 4: Explain uniformity. The first fixed position has n equally likely choices, the next has n-1, and so on, yielding n! equally likely choice paths. The random source must be uniform over each candidate index.

Step 5: Handle duplicates. The algorithm is uniform over element positions. Repeated values can make several position permutations display as the same value sequence; visible sequences are not the same as position permutations.

Step 6: Implement reset. Return a copy of original and rebuild working; exposing the internal array would let callers alias and corrupt the baseline.

Step 7: Verify and state complexity. Use a fixed seed for reproducibility, enumerate small-array frequencies for approximate uniformity, and test empty and one-element arrays. Each shuffle is O(n) time and O(1) auxiliary space; the stored snapshot itself uses O(n) state.

Model answer

“I maintain original and working arrays. shuffle iterates i = n-1..1, draws uniform j ∈ [0,i], and swaps the two entries; reset returns a copy of original and rebuilds working. Repeatedly swapping arbitrary random positions can rewrite earlier positions and produces biased permutations. Fisher–Yates samples only the unfixed prefix, so every positional permutation is equally likely. It runs in O(n) time and needs no extra array beyond the state snapshot. I would inject the random source for seeded tests and replace it with a CSPRNG when the outcome affects security or fairness.”

Common mistakes

• Sample [0,n-1] every round → fixed positions are changed again → use [0,i].
• Compute floor(random * i) → index i is never selected → use i + 1 as the half-open bound.
• Swap arbitrary random pairs n times → permutations are not guaranteed uniform → fix one position per Fisher–Yates step.
• Return the same internal reference from reset → callers can corrupt the baseline → return a defensive copy.
• Treat a PRNG as secure randomness → draw results may be predictable → choose a CSPRNG for the threat model.

Follow-up questions and responses

Follow-up 1: Why can the loop run forward instead?

The forward form fixes i by sampling from [i,n-1]; the proof is symmetric. The invariant is that each choice comes only from the unfixed region.

Follow-up 2: How do you prove uniformity?

Position n-1 has n equally likely choices, position n-2 has n-1, and so on. Every complete choice path therefore has probability 1/n!.

Follow-up 3: How do you test randomness?

Run many trials on a small array, compare permutation frequencies with a tolerance, and use a fixed seed to verify reproducibility. A finite sample is evidence, not a proof.

Follow-up 4: When is ordinary pseudo-randomness insufficient?

Use a system CSPRNG when a draw, token, or shuffle affects security or entitlements. Seedable PRNGs are appropriate for simulations, games, and tests.

Follow-up 5: What if the input is a linked list?

Converting to an array costs O(n) space. Node swaps can preserve storage but random access becomes expensive, so the constraints should be renegotiated.

Follow-up 6: How do you handle concurrent calls?

Give each instance isolated state and lock mutations, or return immutable snapshots. A caller must not observe a partial swap while another thread resets.

Follow-up 7: Does the Java standard library use this idea?

Oracle documents a backward traversal that swaps a random element into the current position; with a fair source, all permutations occur with equal likelihood.