I have realized that I have a perfect recipe to passing a Google interview. It's not easy, but if you do it, you have 95% or more chance of success. The good thing is that the result is portable - you will be equally employable by Microsoft, as well as most other good software companies.
Here it is.
Read and do all exercises in the following books:
(1) Introduction to Algorithms
(Except chapters on advanced data structures (including B-trees, binomial and Fibonacci heaps, representing disjoint sets in data structures); sorting networks; polynomials and the Fast Fourier Transformation (FFT))
(2) Computer Architecture, Fourth Edition: A Quantitative Approach
(3) Hacker's Delight
If you do this and you're not hired (but you can prove that you've done all the exercises and tried to pass the interview in good faith), I will pay you $200 :-).