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.

I 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.

If 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.

I agree, but there is a reason for having the candidate write some code: some people can talk a good talk but can’t actually write a line of code. That’s a phone screen fail, but yes, some people pass the phone screen, so the sooner you figure it out the better.

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.

So what happens in your code if you just change the line

     j = random(0,51)

to

     j = random(i,51)

?

That is indeed the simplest fix. It is called the Fisher-Yates shuffle [1].

[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...

Thank 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.

This question came up in a weekly "random topic" talk that we had at an MIT lab I was visiting at the time, many years ago. One of the lab members - who was a very impressive coder and researcher - had been asked this question at a google interview. I remember being pretty surprised that he wasn't familiar with the fisher-yates shuffle (and that this would be considered a good question to ask at google). His first answer to the problem was actually one of the "obvious" (and incorrect) answers one might give. But then he also walked us through the process he went through with the interviewer on deriving a correct algorithm, along with a mathematical justification of its correctness. I think regardless of whether one is familiar with the typical algorithms, being able to explain and justify them does show skills. (And fwiw, he did end up getting an offer and working at google).

The questions I got were very specific to playing card patterns. The one I remember best was "How many times does it take to perfectly cut and shuffle a deck of cards before it is back in original order". Spoiler: A "perfect" shuffle is called a Faro shuffle and the holy grail of false shuffles to master as a magician. When a deck is cut evenly at 26 cards (doable with practice or a slightly bent or irregular marker card) and Faro shuffled correctly eight times, the deck will return to its original order.

If I really liked the company I might indulge your question, but it would annoy me unless you were a game development company and this was a real problem someone faced recently.

I general I don't like live coding questions because they don't reveal anywhere near the quality of work I produce if left alone to think for a bit. If the questions pertain to a real world problem I will noamally indulge them though. As an interviewer I don't make people do them. I often do live code -review- to see if people can understand code and spot security flaws or bugs as I find that a more useful skill than coding anyway, and code review -is- something actually often done together with peers in the real world.

I sometimes ask for people do take-home tests if they have no open source projects I can reference, because seeing how people code on their own is how I find out if they can do the job. If they use search engines to help, I don't care. That is how real life works.

That said, I only do this if I know the employer is willing to pay them for the time. Work simulation goes both ways.

If I am going to make it like real work, I need to pay for it like real work.

Hilarious. Python's random module has a built-in shuffle.

Interesting, what CS concepts were you looking for?

Stuff like whether the algorithm will always stop, or whether it runs O(N) vs O(N square). The main point to me was more to be able to have a conversation about the solution rather than it being absolutely right. I remember quite a few people using randomness, the most odd (and totally wrong) one using a random sort function over an array of (1..52).

Why is the random sort wrong?

Random sort meaning that sometimes a>b, other times a<b for the same values. Whatever algorithm a language's built in sort implements probably assumes that comparisons are consistent. I remember checking a few versions of perl and some created a core dump iirc.

Ah okay. Thought you meant using something like shuffle in Ruby.

I do wonder what the result of doing a randomized sort like that would be. Probably not really random. Feel like numbers near the median would be overrepresented in the middle of the array.

np.random.choice(52, 52, False) + 1

I'd start with, "What do you mean by 'random'?"

What is the catch here? In multi dimensional and infinite cases it can be a little tricky, but in this one is there more to it than "all permutations should have the same probability"?

I'm not an expert, but here are a few of the things that come to mind for me:

- One conception of random is subjective: the pattern must not be predictable by a particular person/entity. E.g., the Fibonacci sequence may seem random to a person with IQ 3, but not IQ 1000.

- I think related to that is the concept of cryptographically random: [0]

- Random numbers can have different statistical distributions. You referred to uniform randomness, but depending on the application, that's not necessarily what you want. E.g., [1] Especially for statistical / Monte Carlo modeling.

- Depending on just how random you need something to be and to whom, you may or may not need specialized computing hardware. [2]

- Sometimes people kinda want random, but they also want reproducibility if necessary. Think randomly generated unit test input, or randomly generated game levels. For those applications, it's helpful to know that most software uses pseudo- -random number generators (PRNG's). If you can remember the specific number used to seed the PRNG stream, you may be able to deterministically re-execute the code at will. Alternatively, if you want to (nearly) guarantee that subsequent runs of the program aren't the same, you'll want to somehow ensure that a different seed number is used for the different program runs.

So if anything about the job opening depends on this kind of stuff, IMHO it's a great interview question.

[0] https://crypto.stackexchange.com/questions/39186/what-does-i...

[1] https://stackoverflow.com/questions/37828955/what-is-the-dif...

[2] https://en.wikipedia.org/wiki/Entropy_(computing)

Mine would be "what do you mean by 'first number'." If they answer with one-indexing, walk out of the interview.

Yup. Seemingly trivial questions can reveal a lot about the candidate.

Indeed.

I have been routinely questioned about what happens from when you type www.somesite.com and when the webpage is displayed when interviewing over the years and realised that nowadays I could fill 2 whole hours talking about all the stuff that actually happens (and many times I would have to say “but about this specific thing I’m not very knowledgeable about)… whereas at the start of my career i would have probably spoken for like 15 seconds and felt smart about answering “such an easy question”.

Obligatory response, Dilbert’s “9… 9… 9…” number generator, “the problem with randomness, is that you can never be sure…” https://www.dilbert.com/strip/2001-10-25

If we are talking obligatory responses, don't forget this one: https://xkcd.com/221/