In these cases, most of your head-space is focused on the problem, which isn't written down anywhere other than PM's requirements doc. It's pretty critical that you understand the algorithm really well, because if you have to look it up you're going to have to unload all the messy problem-domain stuff that's in your brain.
Also, you can learn the algorithm first then figure out the problem. No need to do it on the fly, although sometimes that can help too.
In the cases where I didn't get the job, I naturally asked why. Despite repeatedly having assured me that they just wanted to know how my brain works and not whether I'd memorized specific concepts, I am usually flat-out told the rejection was because I had implemented some minor detail of algorithm X incorrectly; that my implementation failed in some corner case.
I've also passed and worked at companies which do CS trivia style interviews. When they later interviewed other candidates while I was there, I sometimes observed how the people conducting the interview would first study algorithms and data structures for hours on Wikipedia prior to going in -- because they themselves can't recite any of that without preloading.
Maybe Google works differently; I don't know. At most places, the "CS trivia" style interview seems to primarily serve as a vehicle for bolstering the egos of the people conducting the interview -- they get to feel superior and ding people for not knowing the gotchas of algorithm X.
Just came here to say that from my limited experience, I concur with this comment. Google also has improved their feedback loop after the interview, which I find severely lacking in other companies with similar interviewing styles.
That...
I don't see how being able to recite trivia questions from memory is a good indicator even for implementing a standard library.
Having a rudimentary understanding of algorithms and data structures is useful but in many cases it's also something you could look up.