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)
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.
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)
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.
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.
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.
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! ;-)
April 30 2010, 17:58:43 UTC 5 years ago
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.
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.
April 30 2010, 18:07:20 UTC 5 years ago
Oh, and I have no idea what the answer is, that not being my field at all.
April 30 2010, 18:08:23 UTC 5 years ago
April 30 2010, 18:47:16 UTC 5 years ago
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.
Miss a few days and get this? ;-)
Anonymous
May 3 2010, 03:45:20 UTC 5 years ago
*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! ;-)
May 3 2010, 13:43:16 UTC 5 years ago