Random Card Problem
Random Card Problem is quite popular in game company. I failed a phone interview a month ago because of this problem, so I search for the right answer and post here.
Problem statement is, design an algorithm so that you get a random placement of a set of n cards.
My original answer is as follows:
for each index i, get a random index j, change cards between i and j
However, this is wrong. To see why, let’s have a look at what a right answer looks like:
for each index i, get a random index j from i to n, change cards between i and j
There exist another good algorithm: we know each placement has a unique ID: its place in the whole possible placements. For example, assume n = 3, ID of ‘123’ is 1, ‘132’ is 2, ‘213’ is 3, ‘231’ is 4, ‘312’ is 5, and ‘321’ is 6. It is easy to get the placement from its ID, so we random an ID and get its placement.
Why my answer is wrong
From calculation, we know that, in the right solution, the probability a card stays in its original index is the same for each card, while it is not in my solution.
In the right solution, when i = 1, Pr(1st card stays in 1st place) = 1/n; when i = 2, Pr(2nd…) = (n - 1)/n * 1/(n - 1) = 1/n; when i = 3, Pr(3rd…) = … = 1/n…
Now you see why the right solution right, and you see why my solution wrong. I was surprised by the magical math here the first time I realized it.