[catnaroek]

It's essentially impossible to require candidates not to prepare for a technical interview, but someone who can't discover the tortoise and hare algorithm on their own probably shouldn't have a computer science degree.

[xroche]

> someone who can't discover the tortoise and hare algorithm on their own probably shouldn't have a computer science degree

This sentence is simply ridiculous. Most engineers aren't able to discover this trick. I wouldn't.

The same goes for the rod cutting problem or the maximum sub-array problem (Kadane algorithm): expecting an engineer to find them, especially in an interview, is totally inane.

[catnaroek]

Of course, nobody expects engineers and scientists to have the same skills.

[adamwk]

Then why is tortoise and the hair credited to Floyd if it’s so trivial?

[catnaroek]

Attribution in science works in mysterious ways, and I don't claim to know how it works.

In any case, I didn't say “trivial”. If you can only derive trivial things, then you shouldn't be a computer scientist.

[varjag]

Are you suggesting computer scientists should be able to derive non trivial results on job interviews? Really?

[catnaroek]

This amount of nontrivial, yes. Similarly, I'd expect a computer scientist to come up with a proof of correctness for either binary search or merge sort (the out of place variant) in ~30 minutes. It's not particularly difficult.

[microtherion]

The number of incorrect binary search algorithms published in the literature over the years would indicate otherwise…

I agree that reasoning about the correctness of a binary search algorithm is an important job skill for a computer scientist. Deriving the tortoise and hare algorithm on the fly, though, is not.