> - it's not enough to be able to solve the problems, you need to be able to solve them on the spot, without much thinking, in an interview context

So true. It's not enough to write some approach that's better than brute force. We need to write the best possible method. And sometimes interviewers do not encourage methods that are not on their mind.

Just sucks!!