How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

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.

Input: ([42], [])

Expected Output: [42]

Explanation: A single-card deck is already shuffled; no random calls are needed.

Input: ([5, 6, 7], [2, 1])

Expected Output: [5, 6, 7]

Explanation: Each selected index is the same as the current position, so both swaps leave the array unchanged.

Input: ([-3, 0, 9, 2], [0, 0, 1])

Expected Output: [9, 0, 2, -3]

Explanation: Swap positions 3 and 0, then positions 2 and 0, then positions 1 and 1.

Input: ([10, 20], [0])

Expected Output: [20, 10]

Explanation: For two cards, selecting index 0 swaps the two elements.

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.

Quick Overview

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.