So a few days ago, I got an amusing idea for an interview question which I realized was totally pointless as an interview question, because it has no practical value whatsoever. So instead, I'm going to post it on my blog, as a way to help waste the time of all my CS friends. There is no prize whatsoever for a correct answer, except for the satisfaction of having avoided work for a while solved an amusing problem.
Here are two really bad ways to sort an array:
Random sort: Repeatedly select a random permutation and apply it to the set. Stop when it becomes sorted.
Brute-force sort: Iterate over the set of all permutations of N elements. Apply each in turn. If the list is now sorted, stop.
The question is: which of the two is less efficient, and (the trickier part) by how much?
(Clarification: For the latter, "how much" in terms of average [mean] time to sort. You can also average over a large number of possible inputs)
For the first thing: Yes, I meant the former. The latter wouldn't work. :)
For the latter: Mean runtime over a large, uniformly selected sample of input arguments. (i.e., input arguments are equally likely to be in any permutation of sorted order)
April 30 2010, 18:07:48 UTC 5 years ago
For the latter: Mean runtime over a large, uniformly selected sample of input arguments. (i.e., input arguments are equally likely to be in any permutation of sorted order)
April 30 2010, 18:19:35 UTC 5 years ago
However, I should point out that if you were interviewing Teela Brown, her randomly selected sample would already be sorted.