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)
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.
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