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)
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? ;-)
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! ;-)