In practice recent prior exposure to the problem and possible solutions makes answering such a question far easier, so the most prepared for the questions wins. They don't test thinking, they test preparation.
Not only that, but some worker may be well prepared without even noticing. And without any bad intentions to trick you.
This happened to myself (although in a non-interview situation):
In general, if you have solved many problems and looked at many solutions, you simply won't remember each specific problem. This effect may start as early as your first math olympiad, and will only get worse on university while you study math and/or computer science.
Some time ago I solved a math puzzle, where I got the right ideas relatively quickly, even though I was convinced this problem was new to me. Later I found out in my writings that I actually solved exactly that problem some years ago.
Even though I was unable to remember the exact solution, not even remembered I've seen it before, I seem to have internalized enough clues so I could rediscover the exact solution whenever I need it.
You are right, thinking logically is always better option than memorizing solutions. To have a good thinking ability, one needs practice. Solving many problems leads you to think different approaches, compute running time and space complexity of your solution before writing code to any problem. I think, this is one of the best ways to improve "thinking".
That's just plain wrong. What happens if you need for example ukonnens algorithm for creating a suffix tree? Good luck deriving that on your own. Similarly Fourier transforms. Memorizing what algorithms do and what types of problems they can solve is essential to being a programmer, and besides that it's simply faster.
I agree that memorizing algorithms is useful. That said, Google interview questions are usually much easier than deriving Ukkonen's algorithm or FFT on your own. They are more like "given a rotated sorted array, find a given value quickly". Well, a bit harder than that, but solvable in 40 min.
