Re: Math/CompSci Interview Question - Thoughts?

Paul E. Black wrote:
I took an algorithms or analysis of algorithms class. We solved a ton
of problems like "design an O(n^2) algorithm for ..." (or n log n or
whatever). After a semester of this, we were pretty good at coming up
with stuff. Note: just "knowing" the complexity of a solution went a
long way as a hint to how it might be solved.

Your algorithms professor was kinder than mine. He set problems of the
form "Write an algorithm for ..." with standing instructions that we had
to state a claimed time complexity, prove correctness, and prove the
claimed time complexity. Given correct proofs, he gave better grades for
lower complexity algorithms.

That was more realistic, because someone starting on designing an
algorithm does not usually know in advance what complexity is
achievable. However, it had the unpleasant consequence that I could
rarely be sure I had finished my homework, even after I had written an
algorithm and the required proofs.