What are some of the questions asked in Google interviews?

The other thing to note that's particular to Google is that my interface to the process is that I talk to you, then I write 1,000 to 1,500 words on how that went, and that's it. No meeting, no shades of gray, no nonverbal iffiness. The more you can demonstrate that you really grasp the problem, the better an essay I can write. Please, please, help me write a great essay about you. Think out loud.

I work at Google. I do a lot of interviews. The main things I would really like to see candidates do for prep are:
1. Practice problems that can be knocked down in 20 minutes.
2. Practice coding on a whiteboard.

Interview coding is not the same skill as coding in real life where you have Stack Overflow, reference materials, and an editor. Nevertheless, these are the skills we check for in in-person interviews. Being practiced at these gives me a better, cleaner signal about your actual skill level, rather than how unfamiliar you are with coding in an interview setting.

The other thing to note that's particular to Google is that my interface to the process is that I talk to you, then I write 1,000 to 1,500 words on how that went, and that's it. No meeting, no shades of gray, no nonverbal iffiness. The more you can demonstrate that you really grasp the problem, the better an essay I can write. Please, please, help me write a great essay about you. Think out loud. I need to see how you think, so I can be sure you worked your way to a correct answer, rather than got lucky. I care far more about seeing you dig your way out of a mistake or discuss alternative approaches than getting some "perfect" (probably memorized) answer.

You should be able to:
- Comprehend an English description of a problem and produce working code.
- Analyze an unfamiliar problem and discuss the Big-O for space and speed of various alternatives.
- Recognize situations where common software tools would be appropriate. (I won't ever ask "tell me what a database is good for"; I will give you a problem where using a database is a reasonable approach, and expect you to realize that.)
- Discuss trade-offs intelligently. There are very few absolutes in software design at any level - from function signature through N-tier architecture.