I strongly recommend against using OrderBy(e => rng.Next()). Firstly, this is biased randomness; I might give that a pass if rnd.Next was 64 bit, but it's a measly 32. Secondly, this is extremely inefficient, costing \$\mathcal{O}(n \log n)\$ time for what amounts to \$\mathcal{O}(n)\$ work.

@Veedrac You're correct about it being O(n logn), however in an interview situation, I'd highly favour readability and succinctness. Granted, it'd be a good idea to be able to point out during the interview the trade-off. As for bias, I disagree about it being an issue. See this comment.

Don't have time to go into nuances (and wow, C#'s Random sucks), but imagine shuffling a \$2^{33}\$-long list. A proper shuffle will at least seem shuffled; this approach won't pass casual inspection.

This is not a proper shuffle.

@Veedrac: If n is constant then O(n log n) is also constant. Asymptotic order is only relevant when the size of the input is potentially large. The problem given is not to shuffle a list of eight billion elements; it's given to shuffle a list of ten thousand.

@Veedrac I'd like to see your $2^33$ long List<T>, considering T[] is limited to $2^31$ elements. Also the question specifies 10k numbers, not 8 billion numbers.

@CodesInChaos That was just to show why the bias is significant. It's still present in smaller arrays. That said, it might even be worse than I thought; is OrderBy guaranteed to call the function only once per element?

@EricLippert True, I skimmed past that part. Still, interviews are meant to show you know what you're doing. Writing fragile, inefficient code doesn't paint a good picture.

@Veedrac: So I'll bite: how would you shuffle a list of eight billion distinct longs? (Obviously there are not that many ints.) Begin with how you would represent that in memory; that's 64 billion bytes in an array, considerably larger than the largest array that is legal in .NET.

@Veedrac: OrderBy guarantees that the key extraction function is called once per item, yes.

@EricLippert As I said elsewhere, that argument was to demonstrate the bias by making you think about a reductionistic case. The bias still exists at shorter lengths. Also, d'you have a source on the claim OrderBy guarantees the mapping is once per item?

@Veedrac, check out OrderBy implementation, its open source: github.com/Microsoft/referencesource/blob/master/System.Core‌​/… .

@NikitaB The implementation isn't much of a guarantee ;).

and FWIW, I'd flunk any interviewee that didn't use Fisher-Yates for this task.

@Alnitak and what if someone decides to provide Randomize with a sequential list (i.e., a linked list)? In C# List<T> does imply a randomly-accessible list, yes, but for example in Java List<T> does not imply that indexing is constant-time, rather that it is possible. With sequential lists, Fisher-Yates would be \$O(1)\$ space and \$O(n^2)\$ time, whereas this method would be \$O(n)\$ space and \$O(nlogn)\$ time always (assuming they implemented merge sort for linked lists).

This is why Scala's collections hierarchy makes the most sense.

@Alnitak in summary, you should only fail C# candidates who don't use a Fisher-Yates for the job - seeing as almost everyone thinks that memory is cheaper than time these days!

@Alnitak, personally I do not see how any of this is relevant for 10k array. Especially your 40kb memory concern, it's 2017 out there... Modern PC's won't even blink on such task, therefore the simple solution is the best solution. Cases where this solution will not be enough as well as optimizations that can be made in those cases can be discussed separately as a bunch of follow up questions. "Flunking" anyone who does not instantly produce a solution you expect is a lousy interviewing strategy, IMHO.

@NikitaB some of the other commenters appeared to be suggesting that the above method would be a mitigation for the amount of memory needed to shuffle a large sequence. It's not.