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 v

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