Jobs

Interviews

Discussions

Shuffle an Array

Medium

Google

2 views

Topics:

Arrays

Design an algorithm to randomly shuffle an array such that all permutations of the array are equally likely. You need to implement a Solution class with the following methods:

Solution(int[] nums): Initializes the object with the input array nums.
int[] reset(): Resets the array to its original configuration and returns it.
int[] shuffle(): Returns a random shuffling of the array.

Constraints:

1 <= nums.length <= 50
-10^6 <= nums[i] <= 10^6
All elements of nums are unique.
At most 10^4 calls will be made to reset and shuffle.

Example:

Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Returns a random permutation, e.g., [3, 1, 2]
solution.reset();   // Returns the original array [1, 2, 3]
solution.shuffle(); // Returns another random permutation, e.g., [1, 3, 2]

Explain your approach, including the algorithm used, time and space complexity, and how you handle any edge cases. Provide code implementation.

Shuffle an Array

Medium

Google

2 views

Topics:

Arrays

Design an algorithm to randomly shuffle an array such that all permutations of the array are equally likely. You need to implement a Solution class with the following methods:

Solution(int[] nums): Initializes the object with the input array nums.
int[] reset(): Resets the array to its original configuration and returns it.
int[] shuffle(): Returns a random shuffling of the array.

Constraints:

1 <= nums.length <= 50
-10^6 <= nums[i] <= 10^6
All elements of nums are unique.
At most 10^4 calls will be made to reset and shuffle.

Example:

Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Returns a random permutation, e.g., [3, 1, 2]
solution.reset();   // Returns the original array [1, 2, 3]
solution.shuffle(); // Returns another random permutation, e.g., [1, 3, 2]

Explain your approach, including the algorithm used, time and space complexity, and how you handle any edge cases. Provide code implementation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected size range of the input array `nums`?
Can the input array `nums` contain duplicate values, and if so, should the shuffling still ensure all permutations are equally likely?
Are the integers in the array `nums` guaranteed to be within a specific range, such as not exceeding the maximum or minimum value of an integer?
Should the `reset()` method return a new array, or should it modify the original array in-place?
Is the original array `nums` guaranteed to be non-empty?

Brute Force Solution

Approach

The most straightforward way to shuffle something is to consider every possible arrangement. The brute force method for shuffling an array involves generating all possible orderings and then randomly picking one. It's like trying out every single way to arrange the items until you find one you like.

Here's how the algorithm would work step-by-step:

Imagine you have a set of numbered cards you want to shuffle.
First, you create a list of all the possible ways you could arrange those cards.
Think of this as writing down every single order you could possibly put the cards in.
After you have this giant list, you pick one of those arrangements at random.
That randomly selected arrangement is your shuffled set of cards.

Code Implementation

import random
import itertools

def brute_force_shuffle(input_array):
    # Generate all possible permutations of the array
    all_permutations = list(itertools.permutations(input_array))

    # Choose a random permutation from the list.
    # This ensures each arrangement has equal probability.
    random_index = random.randint(0, len(all_permutations) - 1)

    return list(all_permutations[random_index])

Big(O) Analysis

Time Complexity

O(n!) – The brute force shuffle algorithm generates all possible permutations of the input array of size n. Generating all permutations inherently requires exploring n! (n factorial) different arrangements. Therefore, the number of operations grows proportionally to n!, dominating any linear or polynomial factors. Thus, the time complexity is O(n!).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the input array. This involves creating a list to store all these permutations. Since there are N! (N factorial) possible permutations for an array of size N, the auxiliary space required to store this list grows proportionally to N!. Therefore, the space complexity is O(N!).

Optimal Solution

Approach

We want to rearrange items in a collection randomly. The best way to do this is to go through the collection, and for each item, swap it with another randomly chosen item from the collection. This guarantees each arrangement has an equal chance of happening.

Here's how the algorithm would work step-by-step:

Start at the beginning of your collection.
For the current item, pick another item from anywhere in the collection at random, including itself.
Exchange the current item with the randomly picked item.
Move to the next item in the collection.
Repeat the picking and swapping process until you've done it for every item in the collection. Now, your collection is shuffled.

Code Implementation

import random

def shuffle_array(input_array):
    array_length = len(input_array)

    for current_index in range(array_length):
        # Generate a random index within the bounds of the array
        random_index = random.randint(0, array_length - 1)

        # Swap the current element with the element at the random index
        # This ensures each element has a chance to move to any position
        input_array[current_index], input_array[random_index] = input_array[random_index], input_array[current_index]

    # Return the shuffled array
    return input_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n elements in the array. For each element, it generates a random index and performs a swap. Generating the random index and performing the swap are constant time operations. Therefore, the overall time complexity is directly proportional to the number of elements in the array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm shuffles the array in-place. It only requires a temporary variable to facilitate the swapping of elements. The space used for this single variable remains constant regardless of the input array's size, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return null/empty array (depending on problem requirements and language conventions).
Empty array (nums.length == 0)	Return a new empty array or the original empty array; specify behavior in documentation.
Array with a single element (nums.length == 1)	Return a copy of the original array as shuffling is trivial, or return the original array itself.
Array with all identical values	The shuffling algorithm should still produce a permutation, although all permutations will be identical.
Large array size (approaching memory limits)	In-place shuffling algorithms like Fisher-Yates are memory-efficient and suitable for large arrays.
Array containing negative numbers, zeros, and positive numbers	The shuffling algorithm should work correctly regardless of the numerical values in the array.
Calling shuffle multiple times in succession.	Each call to shuffle must produce a new and independent random permutation.
Integer overflow when generating random indices	Use appropriate random number generation functions that avoid integer overflow issues, potentially using long or double.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected size range of the input array `nums`?
Can the input array `nums` contain duplicate values, and if so, should the shuffling still ensure all permutations are equally likely?
Are the integers in the array `nums` guaranteed to be within a specific range, such as not exceeding the maximum or minimum value of an integer?
Should the `reset()` method return a new array, or should it modify the original array in-place?
Is the original array `nums` guaranteed to be non-empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a set of numbered cards you want to shuffle.
First, you create a list of all the possible ways you could arrange those cards.
Think of this as writing down every single order you could possibly put the cards in.
After you have this giant list, you pick one of those arrangements at random.
That randomly selected arrangement is your shuffled set of cards.

Code Implementation

import random
import itertools

def brute_force_shuffle(input_array):
    # Generate all possible permutations of the array
    all_permutations = list(itertools.permutations(input_array))

    # Choose a random permutation from the list.
    # This ensures each arrangement has equal probability.
    random_index = random.randint(0, len(all_permutations) - 1)

    return list(all_permutations[random_index])

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of your collection.
For the current item, pick another item from anywhere in the collection at random, including itself.
Exchange the current item with the randomly picked item.
Move to the next item in the collection.
Repeat the picking and swapping process until you've done it for every item in the collection. Now, your collection is shuffled.

Code Implementation

import random

def shuffle_array(input_array):
    array_length = len(input_array)

    for current_index in range(array_length):
        # Generate a random index within the bounds of the array
        random_index = random.randint(0, array_length - 1)

        # Swap the current element with the element at the random index
        # This ensures each element has a chance to move to any position
        input_array[current_index], input_array[random_index] = input_array[random_index], input_array[current_index]

    # Return the shuffled array
    return input_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return null/empty array (depending on problem requirements and language conventions).
Empty array (nums.length == 0)	Return a new empty array or the original empty array; specify behavior in documentation.
Array with a single element (nums.length == 1)	Return a copy of the original array as shuffling is trivial, or return the original array itself.
Array with all identical values	The shuffling algorithm should still produce a permutation, although all permutations will be identical.
Large array size (approaching memory limits)	In-place shuffling algorithms like Fisher-Yates are memory-efficient and suitable for large arrays.
Array containing negative numbers, zeros, and positive numbers	The shuffling algorithm should work correctly regardless of the numerical values in the array.
Calling shuffle multiple times in succession.	Each call to shuffle must produce a new and independent random permutation.
Integer overflow when generating random indices	Use appropriate random number generation functions that avoid integer overflow issues, potentially using long or double.