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)
Yonatan Zunger’s Blog 
Clarification just so I know what you’re getting at: When you say “Repeatedly apply a random permutation to the set” does that mean “arrange the set’s elements in an entirely random order irrespective of its previous state” or are you applying a single, randomly selected permutation repeatedly to subsequent iterations of the set?
That said, if you meant the former, the first part of the answer is that (2) is more efficient, as it will never repeat. If you meant the latter, (2) is the only one guaranteed to give a solution, as a single, re-used random permutation may have a cycle through a subset of the solution space, whereas brute force covers the entire solution space.
Clarifying now the question: When you say “by how much”, there’s no real answer, as (1) has no guarantee of a solution through any finite number of iterations (again, assuming its possible permutations cover the entire solution space.) That forces us to pick an expected chance of success in order to come up with a meaningful comparison of the two.
I don’t think a lack of a practical value takes it off the table as an interview question, because how a person reasons out a fairly theoretical question tells you a lot about their methods and their capacities. My old boss used a fairly irrelevant logic problem to test out engineers and it was extremely telling.
Oh, and I have no idea what the answer is, that not being my field at all.
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)
True. But I prefer CS interview questions which test something similar to what one will actually do at work, and this one is so theoretical that it doesn’t really tell you much about how the candidate would do things day-to-day.
Well, I’ll figure out the mean runtime soon.
However, I should point out that if you were interviewing Teela Brown, her randomly selected sample would already be sorted.
Beer
Without peeking
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.)
So random permutations is twice as inefficient.
Going to peek now!
Re: Without peeking
Foo. Am I really the first one to answer?
Re: Without peeking
You are, and you win! 🙂
Re: Without peeking
Woohoo! My math has not failed me. 🙂
Miss a few days and get this? 😉
Just saw this post, and I’m happy to say I thought of an answer (twice as long on ave for random, assuming random is allowed to repeat – man, being in medicine makes it easy to forget math!), but then I thought of something else – what about the actual time needed for the machine to actually create the list? Would it depend on the language (I assume), but likely makes the random list that much longer unless there’s a pre-defined set? Also, if it has to test each iteration to see if it’s fully sorted, it rejects it the first item that isn’t sorted… ack, me bwane huwts!
*sigh* Yony, you can tell I miss you, right? 🙂 (btw, there’s a pic of the 3 of us up on my website)
I usually ask them “What question did you want me to ask that I didn’t?” or “Anything you want to tell me that I didn’t ask about?”. I’ll be adding this one immediately! 😉
Miss a few days and get this? 😉
Just saw this post, and I’m happy to say I thought of an answer (twice as long on ave for random, assuming random is allowed to repeat – man, being in medicine makes it easy to forget math!), but then I thought of something else – what about the actual time needed for the machine to actually create the list? Would it depend on the language (I assume), but likely makes the random list that much longer unless there’s a pre-defined set? Also, if it has to test each iteration to see if it’s fully sorted, it rejects it the first item that isn’t sorted… ack, me bwane huwts!
*sigh* Yony, you can tell I miss you, right? 🙂 (btw, there’s a pic of the 3 of us up on my website)
I usually ask them “What question did you want me to ask that I didn’t?” or “Anything you want to tell me that I didn’t ask about?”. I’ll be adding this one immediately! 😉
I’ve heard both of these referred to as Bogosort, with the non-obvious ultra-efficient improvement called Quantum Bogosort.
I’ve heard both of these referred to as Bogosort, with the non-obvious ultra-efficient improvement called Quantum Bogosort.
Re: Without peeking
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.
Re: Without peeking
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.