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.