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.
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.
When I say “some code” I mean no more than ~20 lines and who cares about missed semicolons or such.
And only one or two interviews need this, the subsequent interviewers can do more of the important stuff you’re talking about.
Another important point about these discussions: train your interviewers. I hate interviewing with (for that matter Working with too) someone who wants to show how smart they are. If we bring someone in for a round of interviews it’s because we want to hire them so are looking to see if our prior judgement is correct. Don’t be mean to the candidate and don’t waste their time or yours.
j = random(0,51)
j = random(i,51)
?[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...
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.
Something like this:
works, but could take arbitrarily long time. Most people prefer bounded run time.Most people seem to come up with something like this:
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.