Some friends of mine have been interviewing at Google and I've been helping them prepare. After some practice interviews, I drew up this flowchart for them to take with them (mentally) to the interviews.

Google uses "oral exam" type interviews:

For another strategy, pull out your copy of CLR(S) (you do have a copy, right?) and re-learn everything. It's all fair game in a google interview.

After you start reviewing, you must do practice interviews. Invite a friend over to ask you questions. Here is what they have to do:

  1. Pick a challenging question and read it to you.
  2. Not give you any help at all.
  3. Ask for a solution in pseudo-code. When you provide it, ask for the order of magnitude runtime analysis.
  4. If you make a mistake, after a while, they should say "are you sure that's correct?"
  5. If you don't give the optimal solution, they should let you develop it, and when you're done, say "do you think there's a better way to do it?"

Believe it or not, interviewing someone isn't a fun as you think, so provide them with beer and/or pizza. Meanwhile you must do your work on a whiteboard. If you don't have one, use a flip-chart or as a last resort paper.

Trust me, answering questions in real time on a white board isn't like doing them in your head. You must practice this or you're going to mess up the interview. Practice with a friend!

Finally, use the interview flowchart to answer the questions:

  • The first, simplest solution just has to work. Don't worry about runtime at this point.
  • Start with pseudocode. Only real code if they ask for it.
  • Do a bunch of examples. Make up some sample data and run through it by hand. This will help you understand the problem better, even if you think you already do.
  • Once you complete a simple (slow) solution, prove it works and then move on to making it faster.

If you do well, the interviewer will tell you you're done before you run out of time. Good luck!