[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
j
between 0 andn - 1
Swap
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
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.