MediumDSA6 min read

Implement Fisher-Yates Shuffle (in-place, unbiased)

Q: Implement Fisher-Yates Shuffle (in-place, unbiased)

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** "unbiased" is a claim about a distribution, so it was measured, not asserted. With a seeded PRNG (so the numbers are reproducible), 600,000 shuffles of `[1,2,3]` were counted per permutation for the correct algorithm and two plausible-looking wrong ones; a chi-square test was then repeated over 200 different seeds. ## 1. The problem, restated Produce a permutation of the array where each of the n! orderings has probability exactly 1/n!, in O(n) time, mutating the input. Two shortcuts look right and are not: sorting with a random comparator, and swapping each element with a random index chosen from the whole array. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | In place? | Fisher-Yates is naturally in place; copy first (`[...arr]`) if the caller must not be mutated. | | What is "unbiased"? | Each

854 views

99 of 154

The problem

Problem, as an interviewer would state it: "Create shuffle(array) that returns a uniformly random permutation in O(n) without bias. Do not use sort with Math.random."

Examples:

Code

shuffle([1, 2, 3, 4, 5]); // e.g. [3, 1, 5, 2, 4], every ordering equally likely

Clarifying questions expected:

Must it shuffle in place, or return a new array?
What does "unbiased" mean precisely — every one of the n! permutations equally likely?
Does it need a seedable or injectable random source for testing?

Code / implementation expected: Yes — real, direct measurement of the output distribution for the correct algorithm AND for the two tempting wrong ones.

array
shuffle
fisher-yates

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Medium

How to read this doc: "unbiased" is a claim about a distribution, so it was measured, not asserted. With a seeded PRNG (so the numbers are reproducible), 600,000 shuffles of [1,2,3] were counted per permutation for the correct algorithm and two plausible-looking wrong ones; a chi-square test was then repeated over 200 different seeds.

1. The problem, restated

Produce a permutation of the array where each of the n! orderings has probability exactly 1/n!, in O(n) time, mutating the input. Two shortcuts look right and are not: sorting with a random comparator, and swapping each element with a random index chosen from the whole array.

2. Clarifying questions a strong candidate asks

Question	Why it matters
In place?	Fisher-Yates is naturally

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: measured permutation counts for Fisher-Yates, the whole-array swap loop and the sort shortcut, using a seeded generator so the numbers reproduce

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 99 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextMedium→

Implement _.compact — remove falsy values

Continue