How to prepare for an interview with Google – Everything you need to know | by Alexander Rojas.

I spent three weeks preparing for the telephone interview and two additional weeks for the on-site interview. I basically stopped using the computer to code and did so only on a whiteboard (you can get one for €5) or on a piece of paper.

I spent 2.5 hours preparing every day during the weekdays and 8 hours a day on weekends. The first thing I did was to create a schedule of the things I wanted to do each day, things like: Solve two algorithms problems, one Design problem, implement A*, implement a red-black-tree, etc. I did so because the first day I panicked trying to learn a little bit of everything at the same time, while thinking I needed to know everything right away. Creating a plan helped me to focus on a few topics a day knowing that I would have time to study all I wanted to prepare. On weekends I also took some time, 1 – 1.5 hours, to review what I had studied during the rest of the week.

The last, but not least important part of my preparation was getting the friends who went through the Google interview process to do mock interview with me. I got almost one mock interview every weekend (sometimes two). The input received from these interviews was invaluable. It helped me to fix my communication errors on time. They also helped me to device a series of steps I would use to solve each kind of problems (basically one for algorithms problems and another for Design problems).

I also halted all coding, and algorithms solving preparations one or two days before the actual interview. This is a policy I developed during the time I studied for my exams in university. The rationale is: If you prepared well enough, solving that extra problem one day before will not help that much on your overall skills, but if you cannot solve it, you will really freak out, think you are not ready and that is certainly the last thing you need. At that point I focused on preparing for the soft skill questions. Things like: which was your biggest challenge, hardest bug and so forth. You will have 5 interviews on one day, at least one guy is going to ask you some soft skills question and you better be ready for it (I actually was asked one in my last interview when I was exhausted). Filling the table they mention in Cracking the Coding Interview helps a lot.

To prepare I used the following books:

Cracking the coding interview: by far the best resource on interviewing. The only thing I would like to add to the book is: don’t write code when solving the Design questions. Think of boxes representing modules and their relationships. I wasn’t asked to write code in the Design interview and I feel writing code may force you to oversimplify the Design problems. I actually got asked two problems taken directly from this book.

Introduction to Algorithms: I used this one to review data structures and remember how they work. I didn’t bother to solve their problems since they are mostly about proving stuff. While I am not against doing demonstrations, that is not what the interview is about.

Probability and Statistics by Morris H. DeGroot. The recruiters mentioned there could be combinatronics problems during the interview, and the first chapters of this book are perfect explaining it. The book has plenty of practical problems on the topic which is perfect because the combinatronics problems on most of the discrete mathematics books are mostly about demonstrations. I followed until the first half of the chapter on probability distributions (really, just until I got the binomial distribution right).

Head First Design Patterns: Design was my weak area, and so I spent a lot of effort on improving it. I tried many times with the “Design Patterns: Elements of Reusable Object Oriented Software” book, but I never completely got it. Head First is an excellent book on Design in general. What I learnt reading will definitely help a lot in my real life. Preparing for the Design problems are better if you have a really experienced programmer or an architect to help you. Unfortunately the ones I know are colleagues of mine and I couldn’t count on them, so I had to come up with a process to solve this kind of problems.

Hackers Delight: During the process, it is almost certain that at least one problem will be about playing around with bits (I got one about it). This is the best book on the topic by far.

I also read the Google papers on GFS and MapReduce, and I actually got asked questions which could be solved very easily using them. The interviewers may not allow to use either GFS or MapReduce in your solution, but mentioning how you would solve your problem with them will certainly give you a plus. Do read them!

Despite the suggestion from the recruiters, I personally didn’t find “Programming Pearls” or “Programming Interviews Exposed” particularly useful. The first two chapters or Programming Pearls are OK, but you won’t miss a lot not reading it. The rest of the pearls is mostly on problems relevant in the 70’s or 80’s, i.e. when it started talking about how great is it to use arrays instead of naming your variables a1, a2, etc. I realized it was written for B programmers and stopped reading it. The second book has a good introduction to the interview process but nothing that is not in the Cracking the Coding Interview, and the problems are so easy they are not a challenge to solve and therefore not very good to prepare. If you want to spend your money wisely, buy Craking the Coding Interview.

Other resources I used were:

Wikipedia: I based my implementations of Dijkstra, A* and Knuth-Morris-Pratt algorithms on the ones from wikipedia. I also checked other stuff in here since I feel it is easier to understand than the over technical Cormen book.

CareerCup is a great site to find some questions. I have to say however that the questions marked as Google tend to be full of students trying to get you to solve their homework, so sometimes the questions there are really weird. Check the ones marked amazon, they tend to be great ones.

Project Euler has a lot or nice problems. I solved the first 50 of them. They are not the kind of questions you are going to get asked but they get your mind into problem-solving mode.

I found that one of the best ways to learn about a lot of algorithms is to check how they are implemented in the C++ standard library. Or at least to think about how you would implement them if you were writing the STL. For example, I never before wondered how to implement an algorithm to generate all permutations of a set until I checked it in the STL.

Many people will recommend to use top coder. Despite all my efforts, I never got to make it work on my computer so I had to do without. I guess if you have no access to the Cormen book, its tutorials are some of the best on the internet.

OverTheWire – Wargames has links to some of the best tutorials on the internet on many topics. I used it long time ago, not for this interview, but I did learn a lot from it. Particularly I only got to really understand how a program is mapped into memory thanks to its tutorials.

On a closing note, I have to say the whole point of preparing is just to set your brain into the right mindset. After all that training it was surprising to see that once I saw a problem I knew right away which data structure to use and how the algorithm will look like. That’s the point you want to reach. The problems themselves are irrelevant but the right problem-solving mindset is everything.

Did I get an offer? Well, I still don’t know. I am pretty confident about interviews 2-5. I solved the problems without major difficulties. But I was so nervous I think I screwed up the first one, so I don’t know. I will tell when I have an answer.