Algorithm1 Practice1 Interview

Fisher-Yates Shuffle

GuideCode Labs

Generate an unbiased permutation by swapping each position with a uniformly chosen remaining one. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Fisher-Yates Shuffle when the prompt's constraints and required operations match this shape: Generate an unbiased permutation by swapping each position with a uniformly chosen remaining one.

On this page · Choose Uniformly from the Unshuffled Prefix

Checking your account…

Choose Uniformly from the Unshuffled Prefix

Fisher-Yates processes positions from the end toward the front. For position i, it chooses uniformly from every index zero through i that has not yet been finalized.

Swap One Final Position per Step

Swap the chosen item into position i, then never touch that suffix position again. The remaining prefix contains exactly the items still available for earlier positions.

Trace Fisher-Yates Swaps

Reference

def shuffle_trace(values,draws):
    values=values.copy();trace=[]
    for offset,index in enumerate(range(len(values)-1,0,-1)):
        chosen=draws[offset];values[index],values[chosen]=values[chosen],values[index];trace.append([index,chosen,values.copy()])
    return trace

Practice

Implement shuffle_trace(values,draws). Moving right to left, draws provides j in [0,i]; return [i,j,state] after each swap.

def shuffle_trace(values,draws):
    pass

Public tests

Finalize one suffix position each step

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Inclusive Random Bounds Correctly

The draw must include both zero and i. Excluding i or choosing from the entire array each time makes permutation probabilities unequal.

Shuffle with Deterministic Draws

Reference

def shuffled(values,draws):
    output=values.copy()
    for offset,index in enumerate(range(len(output)-1,0,-1)):
        chosen=draws[offset];output[index],output[chosen]=output[chosen],output[index]
    return output

Practice

Implement shuffled(values,draws). Return a shuffled copy using supplied inclusive draws.

def shuffled(values,draws):
    pass

Public tests

Keep the caller input unchanged

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Separate In Place and Copying Contracts

Classic Fisher-Yates mutates in place with O(1) auxiliary space. Copy first when caller input must remain unchanged, and inject the random source or draws for deterministic tests.

Explain It in an Interview

Say: “At step i, each remaining item has equal probability of taking final position i. One uniform inclusive draw and swap finalizes it.” State O(n) time, mutation policy, RNG quality, and why repeated arbitrary swaps are biased.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Fisher-Yates Shuffle proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Fisher-Yates Shuffle complete workflow	`O(n)`	`O(n)`	Copy the input and perform the supplied Fisher-Yates swap for every shrinking suffix boundary.

Space

O(n) for the focused Simulate Fisher-Yates Shuffling implementation.

Assumptions

At boundary i, the supplied choice selects one of exactly i+1 remaining candidates for position i. The swap fixes that position and never revisits it, yielding the specified permutation without mutating input.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Fisher-Yates Shuffle invariant before coding and preserve it after every update, traversal step, or recursive return.
The processed prefix or sample has the target distribution for all items seen so far.
The random index range includes every and only currently eligible choice.
Protect the caller input with a copy. Preserve this claim after every transition.
Swap each shrinking suffix boundary with one valid prefix position. Preserve this claim after every transition.

When To Use Or Avoid Fisher-Yates Shuffle

Use It When

Use Fisher-Yates Shuffle when this precondition is stated or can be proved: Each random choice is uniform over the documented candidate range and uses an unbiased random source.
Use it when this maintained state removes repeated work: The processed prefix or sample has the target distribution for all items seen so far.

Choose Another Tool When

Avoid Fisher-Yates Shuffle when this precondition is absent: Each random choice is uniform over the documented candidate range and uses an unbiased random source.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Each random choice is uniform over the documented candidate range and uses an unbiased random source.

Avoid

def fisher_yates(values, choices):
    pass

Use instead

def fisher_yates(values, choices):
    shuffled = list(values)
    for offset, index in enumerate(range(len(shuffled) - 1, 0, -1)):
        choice = choices[offset]
        shuffled[index], shuffled[choice] = shuffled[choice], shuffled[index]
    return shuffled

Where you will hit this: Simulate Fisher-Yates Shuffling(opens in a new tab)

Breaking the state transition

Returns the input order and ignores deterministic swap choices.

Prevent it: Preserve this proof obligation: Induction shows each eligible item or permutation retains the required equal probability after every update.

Avoid

def fisher_yates(values,choices):
    return list(values)

Use instead

def fisher_yates(values, choices):
    shuffled = list(values)
    for offset, index in enumerate(range(len(shuffled) - 1, 0, -1)):
        choice = choices[offset]
        shuffled[index], shuffled[choice] = shuffled[choice], shuffled[index]
    return shuffled

Where you will hit this: Simulate Fisher-Yates Shuffling(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

def fisher_yates(values,choices):
    return list(values)

Use instead

def fisher_yates(values, choices):
    shuffled = list(values)
    for offset, index in enumerate(range(len(shuffled) - 1, 0, -1)):
        choice = choices[offset]
        shuffled[index], shuffled[choice] = shuffled[choice], shuffled[index]
    return shuffled

Where you will hit this: Shortest Subarray With OR at Least K(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…