The main problem, I believe, is the time constraint and the interview environment, both add a LOT of stress and will reduce our ability to come up with an answer. I think most people can come up with a good algorithmic solution given the proper time to do so.

IMHO take home tests with a following discussion of the solution is the best way to go. Interviewers can judge the code quality as well as critical thinking with the follow up discussions.