Shuffle array using random integer API

Q: Shuffle array using random integer API

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

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.

Shuffle array using random integer API

Overview

Task

Requirements

Comments (0)