## Get a free weekly practice problem!

Keep that axe sharp.

### You only have free questions left (including this one).

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.

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

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

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

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

size_t getRandom(size_t floor, size_t ceiling) { static random_device rdev; static default_random_engine generator(rdev()); static uniform_real_distribution<double> distribution(0.0, 1.0); double value = distribution(generator); return static_cast<size_t>(value * (ceiling - floor + 1)) + floor; } void naiveShuffle(vector<int>& theVector) { // for each index in the array for (size_t firstIndex = 0; firstIndex < theVector.size(); ++firstIndex) { // grab a random other index size_t secondIndex = getRandom(0, theVector.size() - 1); // and swap the values if (secondIndex != firstIndex) { swap(theVector[firstIndex], theVector[secondIndex]); } } }

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 vector had 3 elements: [a, b, c]. This means it'll make 3 calls to getRandom(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.

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

1. It's easy and quick. No "reset password" flow. No password to forget.
2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

1. It's easy and quick. No "reset password" flow. No password to forget.
2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

time and space.