I was contacted directly by a recruiter. We exchanged a few emails and talked for a few minutes about past experience, skills, interests, etc. After I agreed to continue with the process, I had a phone interview, an on-site interview, was told that they would contact my references, and then received the offer. One to three weeks passed between each step.

The recruiter talked me through the process and kept me informed about the progress of my application, but the process itself is rather opaque. You do not get to know exactly what you could be working on, you're unlikely to meet people you will be working with, and you do not get much feedback until the offer or no-offer stage. Hiring decisions are made by committee(s) (i.e., not by a hiring manager who has an opening on his team). Although the recruiters may have a good feeling of which direction the application is going, they cannot promise anything until the decision is made.

The phone interview was with one software engineer for 45-60 minutes. After a few ice-breaking questions, they jumped into a few technical questions and then gave me a few minutes for my questions. The on-site interview consisted of five one-on-one technical interviews of 45 minutes each with software engineers, plus a lunch break in one of the cafeterias with another engineer. In total, I probably answered 20-30 different questions on data structures, algorithms, and discrete mathematics.

You write down the answers on a whiteboard or notebook, and the interviewers take notes. Sometimes correct syntax is required; sometimes pseudocode is acceptable. The level of the questions varied a lot and covered a lot of areas. One minute I was manipulating the bits of a byte to implement one coding trick; the next, I was discussing heuristics for an intractable problem. Most interviewers gave me a few minutes at the end to ask them questions, and the discussions touched briefly on my past experience, although I was not expected (and one really shouldn't) to give too much information on my current work. Keep in mind that the interviewee signs an NDA, but the interviewers do not.

In my current job, I do a fair amount of interviewing, and I often interview candidates who give the impression of being competent but fall short of doing well in the technical interview because they are unprepared. This often leads to a no-hire decision, probably an unfortunate false negative. However, hiring decisions are very hard to make since bad recruits are a severe liability to an engineering team. I did not want to be such a candidate, so I prepared as best as I could. Luckily, the process was slow enough to give me some time to do that.

I read (and worked through the exercises of) textbooks on algorithms, data structures, discrete mathematics, and the languages I use. I practiced my handwriting, brushed up on standard CS topics I do not currently use, and learned a bit about Google-specific technology like MapReduce. I also brushed up on my past research/experience and areas related to that.

I was not asked about most of what I prepared on, and I was asked about areas I had not thought of preparing for. However, I think this preparation really helped me to be in the right mindset to solve the type of questions I was asked. In my opinion, good knowledge in the fundamentals is essential, but the most important skill is problem-solving. I was asked questions about areas I'm not familiar with, but (with some help from the interviewers) I was able to break them down into smaller components I could at least tackle. I probably didn't impress in those questions, but it was better than throwing in the towel.

I was not asked directly about specific data structures and algorithms, but if I decided to use some to solve a problem, then I was asked detailed questions about them. So, problem-solving is the skill; CS knowledge provides the tools.

I have negligible experience of being an interviewee, and it's amazing all the silly mistakes my nerves made me do. I really felt that I had misrepresented myself as being clumsy (at least more than I am...). Luckily, it is a myth that one mistake is enough to fail the whole process.

I did not feel the arrogance in the interviewers mentioned in other reviews here. Not all of them made me feel comfortable, but overall, they are what you expect from a Silicon Valley company. Before the application proceeded, I couldn't tell how I did, but I felt that it was a fair process and definitely a positive experience that left me with a very good impression of Google. If you are good at the fundamentals, can show a level of expertise on everything you list on your resume, have spent the time to prepare, and are not intimidated by relentless questioning, possibly on areas you're not that familiar with, then you have a good chance of satisfying enough interviewers to move on to the next step.

Keep in mind that Google affords to be picky, so their hiring process tries to minimize hiring bad recruits at the cost of rejecting potentially good ones.

I got the impression that interviewers are selected depending on what's on your resume. I was asked about heuristics on a specific intractable problem, probably because my background included something related. You really need to know your stuff.