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