Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Shuffle an Array

Explore how to implement a shuffle algorithm that randomly rearranges an integer array with equal probability for all permutations. Understand the method that divides the array into shuffled and un-shuffled parts, performing swaps to ensure fairness. Gain insight into the logic, complexity, and practical testing of this array manipulation technique.

We'll cover the following...

Statement

Given an integer array nums, write an algorithm to shuffle the array randomly. All permutations of the array should be equally likely.

Implement three functions of the Solution class:

  • Initializes the object with the integer array nums.
  • Resets the array to its original configuration and returns it.
  • Returns a random shuffling of the array.

Example

Sample input

[2, 4, 5]

Expected output

Permutation  |  Occurrences | Frequency
[2, 4, 5]    |    150 times | 16.67%
[2, 5, 4]    |    150 times | 16.67%
[4, 2, 5]    |    150 times | 16.67%
[4, 5, 2]    |    150 times | 16.67%
[5, 2, 4]    |    150 times | 16.67%
[5, 4, 2]    |    150 times | 16.67%

Ideally, each permutation of the array should have an equal chance of appearing. With an input array of 33 elements, the number of possible permutations of size 33 ...