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.
I tried doing it -- even with the knowledge of how it works, it took me at least a day to get to an acceptable implementation.
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.
Interviews that require extra knowledge outside of what the job actually asks for are definitely broken.