Random Song Shuffle Function
Filed under Amazon
Free read 2 of 3Define the input as an array of songs and the requirement to shuffle without replacement.
The question
Design a shuffle function to play unique songs from a list without repetition. Once all songs are played, the cycle repeats. Optimize for O(1) extra space.
Constraints
- Songs must be unique in each cycle
- Must support O(1) extra space
- Must be efficient in time
Approach
Define the input as an array of songs and the requirement to shuffle without replacement.
Use the Fisher-Yates algorithm to shuffle the array in-place, ensuring O(1) space.
Maintain a pointer to the current index; when the pointer reaches the end, re-shuffle the entire array.
Time complexity is O(N) for the shuffle, space complexity is O(1) as we modify the input array.
Tips
- What they are testing: Verify that the shuffle is truly random and that no song repeats until the full list is exhausted.
- Common mistake: Using extra space (like a hash set) to track played songs, which violates the O(1) space constraint.
Follow-ups
- Improve algorithm so a played song repeats only after all others are played.
- Do it without using extra space O(1).
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.