How the question is posed really matters. What if the question had been "hey, you have a starting node in a linked structure, and you want to visit / collect / search all of the nodes that it can reach, without duplicates", you'd probably come up with DFS or BFS on the spot because the problem is not that hard and those are really the only two ways to attack it, and having found one of the two you'd probably also realize that the other approach could have been used. Whereas, if just asked to implement DFS or BFS, the question becomes less about problem solving aptitude and more about memorization.
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.
I've conducted hundreds of programming interviews for Google, and I'd expect any good candidate to need way less than 45 minutes to code up a graph traversal in arbitrary order, even if I believed that they didn't already know an algorithm for doing so.
