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)
This looks to me like sampling with and without replacement.
Iterating over all permutations is sampling without replacement. That's n choose 1, (in other words, there are n! permutations), and on average, we'll find the correct one halfway through. So it's O(n!), with a constant of .5.
Random iterations is sampling with replacement, and the sample space is again all the permutations So it becomes a geometric distribution with probability of success 1/n!, and the expected time to success is 1/(1/n!), or n!. (but without the reduced constant.)
Huh. I mis-thunk this one. On first read, it looked like Drunkard's Walk v. Iterative Brute Force, which I thought favored Drunkard's Walk. Except that that's wrong, because the 'you'll find it halfway through' rule applies to Brute Force, while the random replacement isn't actually a Drunkard's Walk.
Without peeking
April 30 2010, 20:36:11 UTC 5 years ago
Iterating over all permutations is sampling without replacement. That's n choose 1, (in other words, there are n! permutations), and on average, we'll find the correct one halfway through. So it's O(n!), with a constant of .5.
Random iterations is sampling with replacement, and the sample space is again all the permutations So it becomes a geometric distribution with probability of success 1/n!, and the expected time to success is 1/(1/n!), or n!. (but without the reduced constant.)
So random permutations is twice as inefficient.
Going to peek now!
Re: Without peeking
April 30 2010, 20:37:33 UTC 5 years ago
Re: Without peeking
April 30 2010, 22:08:43 UTC 5 years ago
Re: Without peeking
April 30 2010, 23:02:55 UTC 5 years ago
Re: Without peeking
May 3 2010, 16:14:34 UTC 5 years ago
I mis-thunk this one.
On first read, it looked like Drunkard's Walk v. Iterative Brute Force, which I thought favored Drunkard's Walk.
Except that that's wrong, because the 'you'll find it halfway through' rule applies to Brute Force, while the random replacement isn't actually a Drunkard's Walk.