Frankly, your comment bewilders me. Sure, you might not be able to replicate KMP in the middle of an interview if you didn't already know it, but I'd certainly expect any competent programmer to be able to come up with some form of solution (and I'd probably expect them to get reasonably close to KMP) reasonably quickly and then to be able to discuss their solution and identify it's flaws. A moderately intelligent version ought to be fairly trivial for someone with a solid comp-sci grounding.
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.
I have several points/cases regarding inability to come up with a KMP like algorithm:
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.
Agree on the 2 & 3... I've probably been out of school (CS) for longer than most on here have been programming.
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.
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.