In my experience I have found that, for puzzle-type interview questions, the actual answer you come up with is not as important as the process by which you came up with the answer.
Interviewers know that you are under pressure during an interview and may not be at your coding best. It's hard to code under that kind of pressure. However, if you approach the problem with a reasonable attempt at a solution and are able to reason your way through the implementation, performance implications and possible edge cases then that will help you. Try to think of the problem in real-world terms, if possible. Ask questions about the problem to find out what aspects are important. Is it OK to implement a solution that's correct but slow so you can make it fast later? Or does it need to be correct and fast right now? Optimization is a difficult task, particularly when you only have a short time to do it.
The speed with which you generate answer is probably not so important in most cases. Better to come up with a good answer slowly than a mediocre one quickly.
I believe there are essentially two types of interview question:
- Does the candidate know the languages they claim to know?
- Does the candidate know enough about programming to be able to solve a tricky problem?
For the first type you do need to be able to reply quickly. I think it's probably worth studying the language a bit more if you think your recall is too slow. For example, if you say you know Java then you'd better be able to implement some basic functions without needing to think about them too much (e.g. reverse a string, compute the Fibonacci sequence, know what types of
Collection implementation are available in the core Java libraries and the pros and cons of each etc).
For the second type speed is much less important. Thoughtfulness and attention to good design are more important.
I'd stay away from the "learn each hard computer science problem and know a solution for each one" approach, because in the real world you don't get "pure" computer science problems very often. That said, it's definitely worth being able to recognise an NP-hard problem when you see it and have some idea about how to approach a solution.
Time for a grain of salt: each interviewer has their own ideas about what is important and what is not. I have said what I think is important but your mileage may vary, results not typical, consult your doctor before use etc etc.
EDIT: A couple of other things to note. Be willing to say "I don't know" when you don't know. It's hard (I'm really bad at it) but it helps. Of course, you should follow up with a reasonable attempt after you've established your lack of knowledge...depending on the question, of course.
Also, it's very helpful to be able to say "this would be easier in language X" or "with tool Y". Different tools for different jobs. If someone asks you to look through log files to obtain all requests from a particular IP address then you're going to lose major points if you try to use Java rather than grep.