[Solution]Problem 28: Perfect Shuffling for a Deck of Cards[Facebook/Meta]
Shuffling, Logic, Math, Arrays
Problem
This problem was asked by Facebook/Meta.
Given a function that generates perfectly random numbers between 1 and k (inclusive), where k is an input, write a function that shuffles a deck of cards represented as an array using only swaps.
It should run in O(N) time.
Hint: Make sure each one of the 52! permutations of the deck is equally likely.
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Step 1: Breaking things down
Facebook/Meta loves its logic/math problems. These problems have a lot of variance in what they ask and the kinds of topics they require you to know. However, there is always a first step that subscribers of the most woke newsletter in coding will be familiar with. And that is breaking things down.
Given—> We are given a deck of cards to shuffle. We are also given a function that will generate random numbers for us. This is a huge relief since Random Number Generation is not an easy task. You can make a lot of money creating good random generators. If you’re not sure where to go, this might be an interesting domain.
Expected—> A perfect shuffler. Any algorithm we design has to be provably uniform. This already hints to us that we will have to spend our time on algorithm analysis over coding. I know some of you are scared of math, but the kind we do for this question will be crucial. And you know that I won’t do anything without explaining it thoroughly.
Other important information—> We can only shuffle the deck using swaps. This might seem trivial but it provides an interesting hint. Since we can use only swaps, we have a direction on how to use the random number generator. We can use it generate indexes to swap at.
This might seem like a waste of time. Why are we wasting time doing this? Two reasons, young Paduan. Firstly, when it comes to harder problems, this process will help you see important hints and insights hidden in the problem. For an example of this, look at our solution for the 2SAT problem. It is one of the hardest problems you will be asked about, not only because it covers challenging topics, but also because the link/transition between these topics is not easy. A thorough breakdown will help you greatly with such problems.
Second, it gives you feedback. When you break problems down into various components you’re allowing for more detailed feedback. This allows you to identify where exactly you failed (or struggled). Remember the harder problems like 2SAT? The best way to learn from them is to have detailed feedback. The more you practice breaking things down, the better you get at this. To learn more about this, read The 4 step method my students use to maximize Leetcode Problems and ace their FAANG Interviews.
Step 2: Naive Algorithm
Let’s get into looking at the solution for this problem. For math/algorithm-heavy questions, it’s best to go for a simple, naive algorithm and then build up from there. This is because simple solutions can be great for getting an intuition for more complex optimization. It’s also much better than sitting there in silence (or with lots of umms). Our simple solution can look something like this:
Iterate through the whole array with an index var i.
Generate a random index
jbetween 0 andn - 1Swap
A[i]andA[j]
This looks like it should generate a pretty reasonable shuffle. This is pretty close to how we shuffle cards IRL (we take batches instead of a single card). But is it truly uniform? For that, we’ll have to do the math.
Step 3: Algorithm Analysis
Coming up with that naive algorithm should not have taken you more than 5-10 minutes. The tricky part is seeing if it is uniform. For that, let’s take a simple case. Imagine we had a simple deck of 3 cards—> [1,2,3].
We make 3 swaps (the length of the array). For each swap, we can choose any of the 3 cards. Therefore, the total possibilities for the swaps we make are 3^3=27.
What about the number of outcomes? Let’s say we pick card 3 to be our first choice. Then we have only 2 cards to be the second card, and finally only 1 card for the final card. Thus overall, we have 3!=6 (3 factorial) possible outcomes. This is basic permutations and combinations, a topic that will be crucial in your interviews and tech journeys.
The more astute among you may have noticed something interesting. 6 does not divide 27 perfectly. By definition, this means we have a remainder. Thus, certain permutations of [1,2,3] will be selected more often than the others. This is an example of the pigeonhole principle, a deceptively useful concept in logic, discrete math, and computer science.
If you want to work on your coding skills, write the simulations for the shuffling with 3 cards and find out which permutations are biased. Once you do, tag me on LinkedIn with a detailed description of your code, how you did it, and your logic. The best ones will receive a shoutout on my social media.
Step 4: Generalizing to n cards
We haven’t done anything too complicated. Not all effective math or logic needs to be convoluted. Often, effective Math is about recognizing the right aspects. But it is crucial that you understand what we’ve done before I proceed.
Let’s see extend what we came up with to a general case. This might give us hints to improve our solution and come up with the final answer.
For an array of n cards-
The total number of possible swaps=n. Total cards that can be swapped at one time = n (n values for index j). Therefore total possibilies= n^n.
The total number of permutations for a deck with n permutations= n!.
For there to be a uniform distribution, n^n/n! has to be 0. How can we prove it either way?
Let’s break it down by cases. This is another great technique we use all the time to solve problems in this newsletter.
Case 0: n== 0 or 1
In these special cases, our decks can’ really be shuffled. Make sure you ask your interviewer how you want to proceed.
Case 1: n is odd
If n is odd, then n^n is odd. n! is even. Therefore we can’t divide the n^n by n! perfectly. Since n^n>= n!, we can use the pigeon hole principle to prove things will not be uniform.
We could stop here, but I didn’t create the best coding newsletter ever by skipping details. Besides going over both cases will truly impress your interviewers.
Case 2: n is even
We can write n^n as k*(2^m) and n! as p*(2^s) where k,p are the smallest odd integers possible. Therefore, n^n/n! will be equal to
k*(2^m)/p*(2^s) = (k* 2^(m-s))/p. The top is even, the denominator is odd. Thus, it will not be uniform.
Fun FACT: If you feel like flexing, you could talk about how this is the inverse of a well-known converging series, and thus the terms will be divergent as n—>infinity. Do so only if you are in a position of flexing.
Once again, take a breath and make sure you understand everything. Especially Case 2. This logic breaks down if (m-s)==0 && k%p==0. Why does that not happen? Take a second to think about it. Struggling with such questions will help you get better. If you don’t get why, comment. It’s crucial you understand.
Step 5: Improving our algorithm
It is now time to come up with our final, improved algorithm. Believe it or not, we’re almost done. Generalizing the algorithm and analyzing it mathematically we see that choosing the swapping index (j) from 0 to (n-1) didn’t work. So let’s tweak things a little. What if we constrained our j from i to n-1? This would allow us to not violate the pigeonhole principle (both numerator and denominator would be n!).
However, that would not be correct. In this case, the Pigeonhole principle just tells us when something doesn’t work. Just because we don’t violate it, doesn’t mean we have the right answer. So how do we proceed?
If we want to prove something about our algorithm, and the algorithm uses loops, using loop invariants is a powerful technique. A loop invariant is a property of a program loop that is true before (and after) each iteration. It is to understand the impact of the loop on your script.
Our loop invariant will be the following: at each index i of our loop, all indices before i have an equally random probability of being any element from our array.
Consider i = 1. Since we are swapping A[0] with an index that spans the entire array, A[0] has an equally uniform probability of being any element in the array. So our invariant is true in this case.
Assume our loop invariant is true until i and consider the loop at i + 1. Then we should calculate the probability of some element ending up at index i + 1. That's equal to the probability of not picking that element up until i and then choosing it.
All the remaining prospective elements must not have been picked yet, which means it avoided being picked from 0 to i. That's a probability of (n - 1 / n) * (n - 2 / n - 1) * ... * (n - i - 1 / n - i).
Finally, we need to actually choosing it. Since there are n - i remaining elements to choose from, that's a probability of 1 / (n - i).
Putting them together, we have a probability of (n - 1 / n) * (n - 2 / n - 1) * ... * (n - i - 1 / n - i) * (1 / n - i). Notice that everything beautifully cancels out and we are left with a probability of 1 / n!
This technique where we prove something for a base case (i=1), assume our statement is true for a statement up to i, and then prove the statement for i+1 is called Mathematical Induction. It works because by proving for a base case, we show that there is at least one value that is valid for i. Since we take arbitrary i and i+1, statements proved for these terms will be applicable to any arbitrary number in the domain. Notice how wonderfully recursive Mathematical Induction is!!
The code for this looks like
def shuffle(arr):
n = len(arr)
for i in range(n - 1):
j = randint(i, n - 1)
arr[i], arr[j] = arr[j], arr[i]
return arr We are looping through the cards array once. Thus the time complexity is O(n) (assuming our random function is constant time).
Time- O(n) because of the traversal
Space- O(1) to store the solution.
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75