All that is true, but I went through some interviews last year at Google, and honestly, you really can't afford to be thinking about things like this. Nobody is going to ask you to just implement DFS, but you may get a problem that essentially reduces to DFS, if you can see it. In my experience, you really will be expected to solve this problem at a whiteboard in 45 minutes. Syntax and so forth won't be an issue, but you can't do too much handwaving, you really are expected to write code that solves the problem.
If you have to stop and reason your way back through DFS, I'd say there's no way you'll get this done in 45 minutes. You need to know this stuff cold.
Rote memorization is useless, of course, because you won't be able to adapt or modify these algorithms. But there's a kind of memorization in the level of sharpness and mental prep you need to have when you walk into those interviews.
