Shuffle an Array
Asked at Uber
Problem
Design a class that shuffle an array of integers and returns it to its original configuration. The shuffle operation must generate all permutations with equal probability. Implement the shuffle using Fisher-Yates algorithm.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Store the original array for reset operations
Implement Fisher-Yates shuffle for uniform random permutation
Iterate from last element to first, swapping with random index
Ensure random index is within valid range for each position
Reset simply restores the original array copy
Optimal Approach
Store a copy of the original array. For shuffle, iterate from the last element to the first. For each position i, generate a random index j where 0 <= j <= i, then swap elements at positions i and j. This Fisher-Yates algorithm guarantees uniform random permutation in O(n) time. Reset simply restores the saved original array.
What Trips People Up in Real Interviews
Clarify that shuffle must produce each permutation with equal probability
Explain Fisher-Yates gives O(n) time with uniform distribution
Discuss why copying the array for reset is necessary
Mention the importance of using inclusive random range correctly
Consider thread-safety concerns if asked about concurrent access
Solution Code
import random
class Solution:
def __init__(self, nums):
self.nums = nums
self.original = nums[:]
def reset(self):
self.nums = self.original[:]
return self.nums
def shuffle(self):
arr = self.nums[:]
for i in range(len(arr) - 1, 0, -1):
j = random.randint(0, i)
arr[i], arr[j] = arr[j], arr[i]
self.nums = arr
return arrFrequently Asked Questions
What is the Shuffle an Array problem?
Design a class that shuffle an array of integers and returns it to its original configuration. The shuffle operation must generate all permutations with equal probability. Implement the shuffle using Fisher-Yates algorithm.
How do you solve Shuffle an Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Shuffle an Array?
Shuffle an Array is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Shuffle an Array?
- Clarify that shuffle must produce each permutation with equal probability
- Explain Fisher-Yates gives O(n) time with uniform distribution
- Discuss why copying the array for reset is necessary
- Mention the importance of using inclusive random range correctly
- Consider thread-safety concerns if asked about concurrent access