Practice/Google/Song Shuffler

Song Shuffler

CodingMust

Problem

Implement a function that randomly shuffles an array of items in-place. Your algorithm must guarantee that every possible permutation of the array has an equal probability of occurring. This property is known as being "uniformly random" or "unbiased."

For example, if you shuffle a 3-element array, all 6 possible orderings (3! = 6) must have exactly a 1/6 chance of being the result.

Requirements

1. Modify the input array in-place and return it
2. Ensure uniform randomness: each of the n! possible permutations must have probability 1/n!
3. The algorithm should work for arrays of any size, including edge cases like empty arrays or single-element arrays
4. Use a reliable source of randomness for generating random indices

Constraints

• 0 ≤ array length ≤ 10,000
• Array elements can be of any type (numbers, strings, objects, etc.)
• Time complexity should be O(n) where n is the array length
• Space complexity should be O(1) (excluding the input array)
• Must shuffle in-place (do not create a new array)

Examples

Example 1:

Input: [1, 2, 3] Output: [2, 3, 1] (or any other valid permutation) Explanation: There are 6 possible outputs: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] Each should occur with probability 1/6

Example 2:

Input: ["apple", "banana", "cherry", "date"] Output: ["date", "apple", "cherry", "banana"] (or any other valid permutation) Explanation: There are 24 possible permutations (4!), each equally likely

Example 3:

Input: [7] Output: [7] Explanation: A single element has only one permutation

Example 4:

Input: [] Output: [] Explanation: An empty array remains empty