Context: I was interviewing for a full-time position after graduation. I passed the phone interview in mid-July and had maybe 3-4 weeks to prepare for the on-site. Google was my first interview in two years and my first interview for a full-time position in any company. In the end, I got an offer, which I accepted. Here is what I did.
There were two different parts to this, knowledge-based preparation and comfort-based preparation. The purpose of the knowledge-based part is to refresh the basic-to-intermediate computer science stuff that you've forgotten but that you need as a foundation for your intuition and understanding. The purpose of the comfort-based part is to get to the point where you can be comfortable, confident, and relaxed fielding questions from Google.
Like Gayle said, the questions Google asks are really not that hard or different from the questions other top tech companies ask. You don't need to memorize how to do X complicated algorithm or spend 10,000 hours becoming such an expert in interview questions that someone could ask you a research question for an algorithms grad student and you could solve it in 30 seconds. Realizing that the space of questions you'll get is not actually all that enormous is key to focusing on the right knowledge and becoming comfortable going in with what you know.
First, the knowledge-based preparation. Basically there was a bunch of stuff I had learned and then didn't really remember. So I had to go make sure I remembered it all again.
Review data structures and algorithms
I already had a pretty good grip on these because I had done enough interviews before that the basics were pretty internalized. Instead of looking at the more complex algorithms in the back of the Algorithm Design Manual I just focused on hashtables, heaps, linked lists, etc. basically the algorithms and data structures covered in a standard intro course. Went up to AVL trees and Dijkstra's algorithm. I also made sure to review tries, because I was expecting a lot of questions involving text data.
Fall in love with algorithms, again
I had some notes from the second half of Algorithm Design Manual and went through them one night just to rekindle my old love of algorithms by re-acclimating myself with all the awesome possibilities for algorithms there were. I wasn't asked to implement anything complex like these but it was always fun to have a conversation after solving a problem that started with "you know, there's actually a crazy algorithm out there, I forgot what its name is but basically it does this… and you might actually be able to solve this problem way faster with it." Then the interviewer and I could have fun just talking about a cool algorithm I vaguely remembered and how it could apply to the problem, which was great.
Review operating systems, networking, computer architecture, system design and scalability
I only spent a weekend on this, just re-reading my notes from when I took the respective classes to remember how computers and systems worked. I never took classes just on scalability or system design, but had a pretty good intuition from projects and internships, so I just Googled some stuff to get a good idea of what the standard tricks were to make things work on a large scale so I could know I wasn't missing anything basic.
Get really comfortable with language of choice
I chose Python, so I started from the basics by re-doing "Python the Hard Way" up to the big Django program, and then crawled around through the Python API, Python Quora/StackOverflow, "Pro Python", Google's Python Style Guide, and some Python blogs (including Guido's blog about the history of Python) just to really get myself in the Python environment and mindset after having programmed in Java for Amazon for the last three months. Whenever I ran into something that I didn't know, or something that I knew I forgot all the time (i.e. conditional list comprehension is for…in….if, not for…in…where like I always want to use) I wrote it down in a Notepad doc. I could have just used Java, but I found Python much easier to whiteboard and think clearly with. Also critical was figuring out what the APIs and standard implementations for the different data structures were in Python (There's a Heap API, most of the rest you have to do yourself) so I could just whip them out in the interview.
Learn Google stuff
I did this before the phone interview, but basically I just skimmed the papers about Google File System, MapReduce, and BigTable so I had an idea of what they did, and then read a little about the history of Google and what its current goals and major products were.
Basically, the knowledge-based preparation was a couple evenings spent reviewing data structures and algorithms, then one weekend that was "Computer Science review weekend" and a second that was "Python review weekend."
On to the comfort-based preparation, by which I mean being comfortable solving problems during the interview.
Most of the rest of my preparation was just going through Elements of Programming Interviews (Elements of Programming Interviews: The Insiders' Guide: Adnan Aziz, Tsung-Hsien Lee, Amit Prakash: 9781479274833: Amazon.com: Books), which is great because it just has tons of problems up to a really high level of difficulty (if you've ever studied chess, it's analogous to the famous Imagination in Chess). I'd randomly pick problems, solve them in pseudocode on paper, and then write solutions in Python and test them on some basic cases to make sure I was doing the right thing. Usually only 1, maybe 2, problems a day on those days I did work on it — the quantity of problems wasn't what was important so much as just figuring out what the typical mistakes I was making in Python were and sorting them out. It didn't take long to figure out which sorts of design patterns in Python I was most comfortable with, and after that things started going much faster. I used PyLint to make sure my code wasn't sloppy.
Sometimes I looked at the answer if I wanted to feel good about myself after solving a problem, but usually I'd skip it if I knew I was right; if I didn't know how to solve it I'd never peek, instead I just let it sit in my head for a day or two until the answer hit me. Some days before walking to work I'd look at one of the "very hard" problems over breakfast and think about it on the walk; I usually couldn't solve these but just thinking about them helped me build creativity and get comfortable using my knowledge to throw different solutions at a problem. I also did some practice with friends to work on my ability to explain my answers and not feel as nervous during the interview.
The main thing, though, was that while I was doing this I noticed that there were a lot of thinking patterns, and that for certain problems once I figured out what kind of problem it was there were easy patterns I could jump into that would go right to the solution i.e. "stream of data where we want to find some sort of representative? Sounds like a heap problem." I never really wrote them down (kept meaning to but forgot) but they were pretty well internalized after 30-40 problems. EPI is a really good book for this because a lot of the "easy" problems are pretty simple but strike at the core of the concepts for those types of algorithms — a lot of other books give questions that have a lot of edge cases or complexity, and those aren't as good for building intuition.
Keeping it real
An important point is that I didn't overdo it here. I only spent maybe a couple hours every few days working on the above. The rest of the time I spent relaxing, spending time with friends, going to concerts, etc. Keeping grounded in reality and maintaining your personality, I think, is an important part of preparing for the interview, because it's easy to get so lost in your preparation that you forget who you are, you define yourself by how ready you are for the interview, and I think that makes you really fragile and cold. The end result of doing things this way was that instead of being anxious and afraid of my interviewers, I was able to talk to them, have a laugh about the whiteboard quality, connect with them; then when the questions came, instead of feeling like they were coming from some sort of Google God who was judging my destiny, they just had the same vibe as a buddy asking me a question after work. If I had spent four weeks as a shut-in doing nothing but solving programming problems, I wouldn't have been able to be as friendly or happy — instead, I would have been constantly thinking "OK, come on, let's get to the questions, I have to do this perfectly, I spent four weeks on it."
Don't let it be a once-in-a-lifetime chance
Finally, have some other options. Don't let it be your one big chance to get into Google. Realize that you can always apply again next year, and apply to other companies at the same time, just to keep your wits about you and not get nervous and stressed out by putting too much significance on every minute of the interview. Besides, this is probably one of the few, if not the only, times in your life when you'll be so ready for a tech interview; why waste the moment just interviewing with Google?
Anyway. That is what I did and it worked for me. If you have a CS degree, you probably already have the knowledge you need, you just have to go build the ability to access the parts of it that are relevant for the interview in an organized and quick fashion. The key is just to get to the point where you're comfortable and relaxed during the interview so you can think clearly and have fun.
One final thought. A lot of the suggestions on here are like "look at all these links, these are mandatory" or "you need to know all these things" which I think creates the impression that you need to know **everything** and that if you miss one thing you're doomed. That's not a good mindset to have because you'll be focused on the wrong stuff — you'll be focused on thoroughly understanding every corner of CS rather than actually having the confidence to solve problems. Knowing stuff is important, but you have to draw the line somewhere. Becoming extremely comfortable with the core of what you know is more important.
Also, it's really tempting to want to be as thoroughly overprepared as possible and understand the theoretical justification for A* or memorize all the string methods in Java or what have you, especially if you have a long time to prepare, but trust me, you won't need to know that stuff, and if you fill your mind with it it's just going to be like fat on a muscle, and the amount of time you waste learning it will hurt you a lot.