[1] http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pr...
Even then, it's not the coded solution that I'm particularly interested in - it's the explanation that follows about how you got to that solution and the discussion about the pros and cons of your particular implementation. I'm looking for signs that you can solve problems and that you can look at your solutions with a critical eye and understand their weaknesses as well.
For what it's worth, the nastiest interview question I've ever had involved building and searching interval trees with up to a billion intervals stored in it where they were looking for solutions which provided the fastest posible search times. It was less than fun.
1. Fresh CS graduate from the top university (MIT, ETH, Stanford, etc..) - I agree, it is a bad sign.
2. Mid/late career professional - I disagree.
3. Self-taught professional - I disagree.
In latter two cases, some might just never needed/seen similar reasoning/algorithm implementation in their life, but that doesn't make them bad programmers.
Another point - many interviewers have beforehand written down exact fixed algorithm, and if your solution diverges at some point with that single variant (although your solution might be correct as well) - this is the red flag for them - and they interrupt you in the middle. I've experienced this even with an open ended design questions - this is really frustrating.
And my last point - remember that when KMP were coming up with this algorithm, no one were breathing in their back/neck.
Not being able to come up with KMP on a whiteboard in an interview hasn't kept me from playing no small part in producing millions in revenue for companies.
Especially outrageous is all of the companies that think they need to ask these questions, when the day to day work is essentially mundane CRUD type stuff.