I spent close to 40 hours studying for the Google onsite interview. Here's an outline of the material I studied and how relevant it ended up being to the actual interview:
- TopCoder Algorithms Tutorials. I worked through all of these and practiced at least a couple problems related to each article. I wasn't asked any geometry problems but also hadn't mention any graphics experience on my resume. However, there was a coding question involving a greedy algorithm and another requiring depth-first search. For some code solutions, the interviewer asked for the big-O time complexity.
- Wu:Riddles CS Forum. This ended up being very important! I worked through the entire forum, paying special attention to problems that looked especially interview worthy. Going through this forum was much more effective than practicing TopCoder problems. A lot of interview material was related to topics discussed on this forum.
- Wu:Riddles in general. This is one of the best collections of classic riddles and puzzles on the web. I didn't get any interview questions that were riddle-like, but if there had been any, this web site almost certainly would either have had the exact riddle or something very similar to it. Maybe that's why they don't use riddles much any more. But solving riddles seems to be a good way to keep the creative side of problem solving sharp, and it's also a nice break from textbook study.
- CLR Algorithms book. I wanted to have solid preparation on algorithms and especially to be able to give textbook examples of each kind of algorithm -- e.g. problems solvable with gredy algorithms, problems that benefit from dynamic programming, how hash tables work, etc. I wasn't directly asked for examples, but knowing them did help recognize what algorithms may apply to a coding problem. Of course, I didn't have time to study the entire book, so my focus was on topics that appeared in the TopCoder tutorials and the Wu:Riddles forum.
- Wikipedia pages on algorithms, sorting, big O notation, and the pigeon hole principle. For me, these were a gentler intro before getting into CLR. Studying the Wikipedia pages would probably have been enough preparation, but for me diving into CLR and going deeper than necessary was a way to ensure the fundamentals were really solid.
- Design Patterns book. The most important part to know was the first chapter. The questions I was asked were cleverly aimed to probe for experience in using design patterns. We talked about what patterns are, why they're important, when to use them, when not to use them (a good answer shows experience), how to decide what patterns to use and not to use, etc. That part of the interview basically involved giving a 5-minute synopsis of Chapter 1, plus a few design stories to illustrate key points. I had prepared a list of JDK examples of each pattern to talk about, but was asked more about patterns I've used or avoided in my own code.
- Effective Java book. I read the whole thing and typed up a study sheet for each item heading, including bullets for any sentences that were in boldface. I also had stories of real-world design experiences where going against the advice of the book ended up being critical to success. The interviewer seemed to like those stories.
- Refactoring book. My resume had specific items about refactoring experience, and one interviewer did ask a lot of questions about it. Chapers 2-4 were the most important to know, especially describing what forces affect the decision of whether to refactor or not to refactor, listing what code smells were most common by my experience, identifying key techniques for successful refactoring, etc.
Below are some other hints I collected from the web and other people who've interviewed at tech companies (not necessarily at Google):
- How do ArrayList, HashMap, LinkedList, and HashSet work and what are their big-O time and space complexities?
- Can you take a while or for loop and wrap it inside a java.util.Iterator implementation?
- How do you use the synchronized keyword together with wait() and notify()/notifyAll()?
- Bit manipulation tricks
- Coding on a whiteboard is effective in an interview for a few reasons.
- It shows whether you know the language well enough to be productive without an IDE.
- It really exposes how clear your thinking is, especially how close you are to the final solution on the first try.
- It shows how good you are at stepping through your own code. Are you systematic and careful? Or ad hoc and rushed?
- Java language keywords/constructs and their edge cases -- e.g. try-finally, static, checked vs. runtime exceptions, where classes can be declared, etc.
- What techniques do you use to maximize unit test coverage in your code? Have you experienced any situations where achieving a high level of unit test coverage was difficult? What made it difficult and what did/could you do to lessen the difficulty?
- You are investigating a bug, but when you try the reported steps, sometimes the bug occurs and sometimes it does not.
- In your experience, what are the most common reasons that a bug might be inconsistently reproducible? Come up with at least 5 types of causes and give an example of each.
- For each potential reason, what techniques would you use to identify the cause of the bug and its fix?
- Have you ever fixed a bug which you never actually observed directly? If yes, how were you able to locate the problem and fix it?
