I interviewed for a Software Engineer in Test role at Google in Jan 2010 when I had two hour long phone interview in the same day. The precursor to this was that I was referred by someone I knew in the company, I then had a quick 20 minute talk with an HR person who set up my 2 interviews.
The first interview was with a member of the Test team for Chrome. We started with going through my background, why I applied for the role and then moved onto some of what would be considered technical questions. The first was a testing question, he asked me what approach I would take to Test that Google Chrome actually works. We went through that for about 15-20 minutes when I was asked a logic/programming question. The setup was that I was a parking attendant in a lot that only ever had one open spot, and I wanted to move the cars into a new arrangement (from their original). Create a program that will print out instructions on how to move the cars most efficiently.
The problem is not that difficult, what you have to do is find the empty spot, then look in the desired arrangement for what car should be in that spot, and move that car there. Repeat until complete.
The second phone interview was much more heavily focuses on Data Structures, there was very few questions on my background, we got into the coding portion right away. With this interview I found that the interviewer was very unclear in what she desired, and it did not seem like it was on purpose (eg, she was not being intentionally vague), and we honestly just did not click.
Based on the second interview my expectations were low. A week after the interviews I got a call from the HR person associated with me and she said that at this time they were not interested in me. I asked for more feedback, and she was unable to offer any. This is a large annoyance of mine because I really am looking to improve myself, and without feedback that is difficult to do. In this case though I am almost certain that my experience with data structures was my downfall.
My advice, if you are interviewing for a position at Google, make sure you know those data structures through and through, because that seems to be what they care about.