3 ms·
It might be the difficulty of actually getting it right (if by "right" we mean that all 52! permutations are equally likely. Or perhaps it is more accurate to s
by tzs 4y ago
It might be the difficulty of actually getting it right (if by "right" we mean that all 52! permutations are equally likely. Or perhaps it is more accurate to say the ease of not getting it right.
Something like this:
10 pick a number from 1 to 52
20 if not already printed it
30 print it
40 if we have printed 52 numbers
50 halt
60 goto 10
works, but could take arbitrarily long time. Most people prefer bounded run time.
Most people seem to come up with something like this:
array = [1, 2, ..., 52]
for i = 0 to 51
j = random(0,51)
swap(array[i], array[j])
print(array)
That has bounded time (constant time assuming random and swap are constant time). Unfortunately not all permutations are equally likely.
We can see that all permutations are equally likely by noting that there are 52 iterations of the loop, and each iteration has 52 possible outcomes. That gives us a total of 52^52 possible outcomes. 52! does not divide 52^52, so it is not possible for each of the 52! possible outcomes to be equally represented in the 52^52 outcomes.
To fix this, you can use the same basic idea of going through all 52 places in your array [1, 2, ..., 52] and swapping each with a random location, but instead of swapping the Nth location with a random location in the whole array, swap with a random location that is not earlier in the array.
Then you still have 52 iterations, but now the number of outcomes varies by iteration. The first iteration has 52 outcomes. The second has 51 outcomes. The third 50 outcomes and so on down to that last having only 1 outcome. That gives 52! possible outcomes, all equally likely. We just then have to show that every one of the 52! permutations is among those outcomes which is easy to do, and then we have shown that this is a correct shuffle.
- Kim_Bruning 4y agoSo what happens in your code if you just change the line j = random(0,51) to j = random(i,51) ?
- tzs 4y agoThat is indeed the simplest fix. It is called the Fisher-Yates shuffle [1]. [1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...
- Kim_Bruning 4y agoThank you! I now have a bunch of theory to read through that I hadn't encountered before. And I also have some more to think about how I assess people's skills too.
- gumby 4y agoI like to use problems like this too. What’s nice about this example is it provides lots of scope for discussion (as you did) without requiring much domain experience. If the person can’t program their way out of a paper bag you’ll find out right away. If they are a junior hire, any working answer is fine. If they have more experience they can start to talk about why they chose the approach they did. If they are quite senior you could talk about the benefits and limitations of different strategies, as you did. In my case (if I still applied for programming jobs, which I don’t), I’d most likely do a naive shuffle and then discuss how problems using random numbers involve corner cases that require thought and domain knowledge I don’t have at my finger tips, so we could talk more about the (pseudo in this case) application needs so I could (in the real world) focus on the most important constraints. As an interviewer I’m as happy, or even more happy, when the candidate knows their domain limitations and where they are important and where they are not.
- tzs 4y agoIf I was interviewing people what I'd probably do is pick 3 or 4 LeetCode problems, but not ask the person to actually solve them. Instead, we'd pick whichever of the problems they find most interesting discuss the problem specification, and how we might approach it. We'd discuss what difficulties and special cases we anticipate. Then we'd look at the answer together and see if it seems to make sense. In these discussions I'd try to let them take the lead but would contribute enough to get things moving if they are getting hung up on something. Finally, we'd go to the most valuable part of LeetCode, the discussion forum for the problem. In the discussion many people post their solutions and a lot of them are wrong. We'd look at a few of those and review them, again with me letting the candidate take the lead. The great thing about the discussions is that the answers people post contain a wide variety of mistakes. Some don't solve the right problem. Some do get the right answer but don't meet the time or space constrains from the spec. Some miss edge cases. Some fall apart if the problem is too big (e.g., if an input array is big enough that every unsigned integer the language supports is a valid index). Before we started I'd tell them we are going to do that, so when they hear the word "LeetCode" they don't have to worry even for a moment that I'm going to spring some hard trick question on them and expect to solve it under pressure. I'd probably even ask them if they have any LeetCode problems they have seen or did before and would like to use for this discussion. Since I'm not asking them to solve them, it doesn't matter if they've already seen them.