Consider the following function, where `random()` returns an independent value uniformly distributed in `[0, 1)` on every call: ```javascript function shuffle(a) { for (let i = 0; i < a.length; i++) { const j = Math.floor(random() * (i + 1)); const temp = a[i]; a[i] = a[j]; a[j] = temp; } return a; } ``` Explain what the function does. Can it be used to shuffle an array, and are all permutations equally likely? Give a correctness argument rather than relying only on experiments. ### Constraints & Assumptions - The input elements may be treated as distinct when reasoning about permutations. - `random()` is unbiased and calls are independent. - Mutation of the input array is allowed. ### Clarifying Questions to Ask - Is the random-number source truly uniform over the stated interval? - Is an in-place result acceptable? - Does the caller require reproducibility from a seed? ### What a Strong Answer Covers - The invariant after processing index `i` - Why choosing from exactly `0..i` matters - A probability argument for uniformity - Time and space complexity - Practical caveats about random-number generation and test strategy ### Follow-up Questions - What goes wrong if `j` is instead chosen from the entire array on every iteration? - How would you test the implementation without expecting a specific permutation? - How would you expose deterministic seeding for tests?