My experience has been different. Usually the best thing to do is to write the naive approach first and then let the interviewer guide you towards what they think you could improve.

This.

Implement -> Evaluate -> Refactor

I'd rather have someone who could caveman the first approach, recognize the inefficiencies, and improve the execution than someone who rattles off a memorized algorithm to a common problem.

If the interviewer is wanting the eloquent solution right out of the gate, then the manager might be hiring for the wrong position.

This works best when you've formed a rapport with the interviewer. If you haven't then you've already bombed.

OK, so you are just going to assume that any interview you can't pass is broken?

There have been interviews I have failed and instead of blaming the interviewers I took the time to actually study the problem I was given. This has helped me become a better programmer.

No, i was just presenting a counter argument. I never had to actually implement KMP outside of uni though.

Interviews that require extra knowledge outside of what the job actually asks for are definitely broken.

That has not been my experience as an interviewee. Implementing the naive solution for small n has been well received in my interviews, and from there (imperfectly) optimizing it is a collaborative experience.

I don't doubt you've experienced differently. But if you have, I think it's likely the interviewer, not the question. Lots of interview questions can be abused, not just basic algorithms and data structures questions.