TL;DR Read three books, watch two classes, solve problems at topcoder/codeforces/projecteuler. Links are below.
If you are interested in getting a job at Google, you’ve probably already read Steve Yegge’s famous post (if you didn’t, read it first). It assumes you have only a couple of weeks for preparation and focuses on topics. I used it as a checklist. This recipe focuses on resources; depending on your background, requires 3–6 months, and gives you pretty good chances to pass the interview even if you never knew the difference between a graph and a hash table.
After following the recipe you will
- have basic math, algorithm and data structure knowledge required for the interview
- change the way you think about problems, expressing them using mathematical models (it is not scary, rather fun)
- possibly love learning. Here at Google it is a continuous process and not less intensive.
- learn nothing about system design (see below)
I spent 2/3 of time on education and 1/3 on solving problems, but that’s because I had almost zero CS knowledge. If you just need a refresher, you should probably spend more time on problems.
The lecturer, Prof. Tom Leighton, is just great. He gives simple real-life examples that help understanding material easily. The course is designed for undergraduate students.
Learn algorithms and data structures
- Watch MIT’s Introduction to Algorithms video course.
- Read Introduction to Algoritms book by Cormen et al.
- Do homework
- Write algorithm and data structure implementations yourself. Write unit tests
- Skim through the second part of Algorithm design manual book by Skiena. It is a catalog of well-known algorithmic problems. The first part is not required since Introduction to Algorithms covers theory pretty well
- Optionally, skim through Algorithms book by Sedgewick. He covers 3-way-quicksort and has great illustrations
The Introduction to Algorithms book is the primary source of knowledge in the whole recipe. The video lectures mainly explain the material in the book, bring some fun, but also present something not covered by the book.
The book is big, but according to Steve and reports available on the Internet, not all knowledge presented in the book is required for the interview. At least you should read the material covered by the lectures. I enjoyed reading more because it turned out to be soo interesting.
I believe writing code after reading theoretical material is the only way to memorize it and find real-life obstacles, not obvious from pseudocode. For instance, Dijkstra’s algorithm pseudocode initializes distance for all nodes in the beginning. In practice it will cause unnecessary memory waste and it is much more efficient to assign distance to a node on discovery. I wouldn’t figure this out without implementing it myself.
I didn’t have time to read it all, but Part I Fundamentals is worth reading even if Java is not your language. You must be able to tell why a given piece of code won’t work multi-threaded and how to fix it.
The second part of the recipe is simply solving algorithmic problems available at contest sites, such as TopCoder and Codeforces. Solve as many problems as time permits. It is OK to feel “I am stupid” when looking at a problem. I still have it, yet I’ve got a job.
Two main languages for an interview are Java and Python. Choose one and use it to solve all problems.
There is a plenty of interview problems posted on the Internet. Here are some of them:
Problems at topcoder/codeforces are generally more difficult than published interview problems, so make sure you know how to solve all interview problems that you find.
Learn system design
You will be asked system design questions for sure. This recipe does not cover it. I didn’t prepare for system design and regretted. If you have a book/course recommendation, please post in comments.
Good luck, but more importantly prepare for intensive self-development. After getting the job you will find this material was just a tip of an iceberg.