Shuffle array using random integer API
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an array `nums` of length `n` representing a deck of distinct cards.
You **do not** have access to a built-in shuffle function, but you are given the following API:
```python
rand_int(l, r) # returns a uniformly random integer in [l, r], inclusive
```
### Task
Implement a function `shuffle(nums)` that randomly permutes the array **in place** such that **every one of the `n!` permutations is equally likely**.
### Requirements
- You may only use `rand_int(l, r)` as your source of randomness.
- The algorithm should run in `O(n)` time and `O(1)` extra space.
- You may assume `rand_int` itself is perfectly uniform and independent between calls.
Describe your algorithm, argue why the resulting permutation is uniform, and give the time and space complexity.
Quick Answer: This question evaluates understanding of randomized algorithms, uniform probability distributions over permutations, in-place array manipulation, and time/space complexity analysis within the Coding & Algorithms domain.
You are given an array `nums` of length `n` representing a deck of distinct cards. You do not have access to a built-in shuffle function. In the real interview setting, your only source of randomness is `rand_int(l, r)`, which returns a uniformly random integer in the inclusive range `[l, r]`.
Implement the shuffle logic using the Fisher-Yates approach: randomly permute `nums` in place so that every one of the `n!` possible permutations is equally likely.
For deterministic unit testing, this problem provides a second argument, `random_indices`, which simulates the outputs of `rand_int`. The first value in `random_indices` should be used as the result of `rand_int(0, n - 1)`, the second as the result of `rand_int(0, n - 2)`, and so on until `rand_int(0, 1)`. Your function should mutate `nums` in place and return it.
Constraints
- 0 <= len(nums) <= 100000
- All values in nums are distinct integers
- len(random_indices) == max(0, len(nums) - 1)
- For each k, 0 <= random_indices[k] <= len(nums) - 1 - k
- The algorithm must run in O(n) time and use O(1) extra space, not counting the input arrays
Examples
Input: ([1, 2, 3, 4], [1, 1, 0])
Expected Output: [3, 1, 4, 2]
Explanation: Use indices 1, 1, and 0 for ranges [0,3], [0,2], and [0,1]. The swaps produce [1,4,3,2], then [1,3,4,2], then [3,1,4,2].
Input: ([], [])
Expected Output: []
Explanation: An empty deck has only one permutation, so no swaps are performed.
Hints
- Think about filling the array from the end: which card should go into the last unshuffled position?
- After choosing a random index from the remaining prefix, a swap can place that chosen card without needing extra memory.