Katkat
Back

Shuffle array using random integer API

GoogleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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, 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.