If the interviewer expects a correct answer off the bat, or rates candidates based on the time they got the solution, then the interview process is bad. But th

If the interviewer expects a correct answer off the bat, or rates candidates based on the time they got the solution, then the interview process is bad. But the question is legitimate. If you're a programmer then you should be able to come up at least with a naive (but correct) solution. You don't need any tricks for that. Then you estimate the efficiency of your naive solution and see if you can improve it. That said, there's still the problem that OP and several comments here mention, that the interviewer might get nervous, freeze, etc, even for problems that they would normally have no problem solving.