One of my friends was asked how to shuffle a list as an interview question, and got into an argument with his interviewer over whether fisher-yates was better than the naive (wrong) shuffle. He had to produce the proof on the spot to convince the interviewer.
Seems like you shouldn’t be asking interview questions you don’t know the answer to, although I suppose that if you’re asking questions at the boundary of your understanding (ie you want to hire someone better than you) you might have to.
One “interview pattern” I’ve seen before is the interviewer asking the candidate to implement a sort/shuffle/tree/other basic task and then make a false claim about the solution - either that it’s wrong, suboptimal, etc. The goal is to see how the candidate defends their position.
I’m not certain that this is what happened to your friend, but consider: that interviewer managed to have your friend show not only that they have heard of and can implement the right algorithm, but that they understand the algorithm as well. Sounds like good interviewing to me ;)
Another of my friends had interviewed with the same guy before, and gave the naive solution, and was told it was correct. He was later offered a job. So it was a pretty weird filter, if it was.
Let me go ahead and revise my comment: sounds like bad interviewing to me!
That’s the thing about that interview pattern - it’s easily confused with ignorance. The few times I’ve seen it done the interviewer usually tips their hand at the end.
So did your first friend get an offer? And, if so, did he take it?
Yes, he got an offer, but he didn’t take it.
There’s another shuffle algorithm that is not as efficient as Fisher-Yates, but much simpler to implement in interview situations. This sort is only as good as your random number generator:
It’s exceptionally simple to implement if it is convenient to do Schwartzian transforms in the implementation language.
The easiest way I find to visualize the fairness of Fisher-Yates is by comparing the array to a lottery bowl. You draw balls from the bowl (the tail-end of the array), and place them in order (at the head of the array). As you draw more balls from the bowl, the number of remaining balls is reduced (the tail shrinks).
Basically, you draw a random element from the remaining elements for each position in the array.