But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a **free** Interview Cake problem every week.

**
You're in!
**

**
Write a function for doing an in-place shuffle of an array.
**

The shuffle must be "uniform," meaning each item in the original array must have the same probability of ending up in each spot in the final array.

Assume that you have a function ICKGetRandom(floor, ceiling) for getting a random integer that is >= floor and <= ceiling.

A common first idea is to walk through the array and swap each element with a random other element. Like so:

#import <Foundation/Foundation.h>
#import <stdlib.h>
NSUInteger ICKGetRandom(NSUInteger floor, NSUInteger ceiling) {
return floor + (NSUInteger)rand() % (ceiling - floor + 1);
}
void ICKNaiveShuffle(NSMutableArray<NSNumber *> *array) {
// for each index in the array
for (NSUInteger firstIndex = 0; firstIndex < array.count; firstIndex++) {
// grab a random other index
NSUInteger secondIndex = ICKGetRandom(0, array.count - 1);
// and swap the values
if (secondIndex != firstIndex) {
NSNumber *temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
}
}

**However, this does not give a uniform random distribution.**

Why? We could calculate the exact probabilities of two outcomes to show they aren't the same. But the math gets a little messy. Instead, think of it this way:

Suppose our array had 3 elements: [a, b, c]. This means it'll make 3 calls to ICKGetRandom(0, 2). That's 3 random choices, each with 3 possibilities. So our total number of possible *sets of choices* is 3*3*3=27. Each of these 27 sets of choices is equally probable.

But how many possible *outcomes* do we have? If you paid attention in stats class you might know the answer is 3!, which is 6. Or you can just list them by hand and count:

a, b, c
a, c, b
b, a, c
b, c, a
c, b, a
c, a, b

But our function has 27 equally-probable sets of choices. 27 is not evenly divisible by 6. So some of our 6 possible *outcomes* will be achievable with more *sets of choices* than others.

We can do this in a single pass. time and space.

A common mistake is to have a mostly-uniform shuffle where an item is less likely to stay where it started than it is to end up in any given slot. Each item should have the same probability of ending up in each spot, including the spot where it starts.

Log in or sign up with one click to get immediate access to free mock interview questions

We'll never post on your wall or message your friends.

Log in or sign up with one click to get immediate access to free mock interview questions

We'll never post on your wall or message your friends.

time and space.

Log in or sign up with one click to get immediate access to free mock interview questions

We'll never post on your wall or message your friends.

Reset editor

Powered by qualified.io

{"id":11831760,"username":"2019-04-25_14:57:51_!4&*f^","email":null,"date_joined":"2019-04-25T14:57:51.240602+00:00","first_name":"","last_name":"","full_name":"","short_name":"friend","is_anonymous":true,"is_on_last_question":false,"percent_done":0,"num_questions_done":0,"num_questions_remaining":46,"is_full_access":false,"is_student":false,"first_payment_date":null,"last_payment_date":null,"num_free_questions_left":3,"terms_has_agreed_to_latest":false,"preferred_content_language":"","preferred_editor_language":"","is_staff":false,"auth_providers_human_readable_list":"","num_auth_providers":0,"auth_email":""}

. . .