A complete waste of time!

[zunger]

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

Comments

[heef]

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.

[zunger]

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)

[heef]

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.

[ipsafictura]

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.

[zunger]

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.

[sy4]

Beer

Without peeking

[kamileon]

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

[kamileon]

Foo. Am I really the first one to answer?

Re: Without peeking

[zunger]

You are, and you win! :)

Re: Without peeking

[kamileon]

Woohoo! My math has not failed me. :)

Miss a few days and get this? ;-)

[anonymous]

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