Shuffle an Array

Shuffle an Array

What is this problem about?

The Shuffle an Array interview question asks you to design a class that can: (1) return the original array, and (2) return a randomly shuffled version of the array where every permutation is equally likely. The shuffling must use the Fisher-Yates (Knuth) shuffle algorithm to guarantee uniform distribution. This tests understanding of unbiased random permutation generation.

Why is this asked in interviews?

J.P. Morgan, Uber, Microsoft, Meta, Amazon, LinkedIn, and Google ask this design problem because random shuffling is fundamental in card game simulations, randomized algorithms, Monte Carlo methods, and A/B testing frameworks. The Fisher-Yates shuffle is a specific O(n) algorithm with proven uniform distribution — knowing it versus ad-hoc random approaches demonstrates algorithm knowledge. It also tests class design with state management (preserving the original array).

Algorithmic pattern used

The pattern is Fisher-Yates shuffle with stored original. Constructor: store the original array and a copy for shuffling. reset(): return a copy of the original. shuffle(): for each index i from 0 to n-1, pick a random index j in range [i, n-1], swap arr[i] with arr[j]. After the loop, return the shuffled array. This guarantees every permutation is equally likely with O(n) time per shuffle.

Example explanation

Original: [1, 2, 3].

Shuffle:

• i=0: random j=2, swap → [3, 2, 1].
• i=1: random j=1, swap → [3, 2, 1] (no change).
• i=2: random j=2, swap → [3, 2, 1].

Shuffled: [3, 2, 1].

reset(): return [1, 2, 3].

Another shuffle call might yield [2, 3, 1], [1, 3, 2], etc. — all 6 permutations equally likely.

Common mistakes candidates make

• Picking j from [0, n-1] instead of [i, n-1] — picking from the full range biases against permutations where early elements stay in place.
• Not preserving the original array — if the copy is shuffled in-place without a backup, reset() cannot restore it.
• Using random.sample(arr, len(arr)) — while Python's implementation is correct, interviewers expect you to implement Fisher-Yates explicitly.
• Shuffling by sorting with random keys — this is O(n log n) and biased when multiple elements share the same random key.

Interview preparation tip

For the Shuffle an Array coding problem, the randomized array design interview pattern is the Fisher-Yates algorithm. The two key properties to state: (1) each element is equally likely to end up in any position, (2) it runs in O(n) time. Meta and Nvidia interviewers ask why picking j from [i, n-1] instead of [0, n-1] matters — know the proof: the first range gives n! equally likely outcomes; the second gives n^n outcomes which isn't divisible by n! for most n. Practice the algorithm by hand on a 4-element array to internalize the swap pattern.