Interviewing @ Google

For those of you who didn’t know (or work it out), this is where I interviewed last week. It went well, I think – at least I feel like I did the best I could and whatever happens that will be helpful.

I agreed to an NDA, so I can’t write about the questions that they asked me. However, I can write about how I found it and what I did to prepare.

First, it’s Google – so I would never have applied had my friend who works there not talked me into it and referred me. I didn’t have a phone interview, since I was “local” I was invited on-site directly. I don’t really think Ottawa is local for Waterloo (maybe because I don’t have the Canadian perception of distance!), but definitely in-person interviews are better than phone interviews and I lucked out because it was Ignite Waterloo that night, which was awesome.

First, I had a brief chat with a recruiter, who explained that I would be using a whiteboard and the process, and then two 45 minute interviews with two software engineers, one on one. I was amazed that I found the interviews fun! Normally I find interviewing really stressful, but what’s great is that it’s not so much like interviewing as jamming with another softie. That’s pretty cool! The questions in the first interview was fairly easy, the second one was a little harder but not too bad. The hardest thing was probably coding on the whiteboard (rather than a computer!) – hard to do TDD on a whiteboard! They tell you not to get dressed up, and definitely best not to – I spent a good portion of the time sat on the floor writing on the whiteboard and covered my hands in marker. Imagine doing that in a skirt!

Helpfully, they sent me a list of things to prepare for the interview. I have a solid undergrad so I’d covered all of it at some point, but it was good to know what things to focus on revising. Note that this is in addition to what I do in general – remain current with industry news, use Google products extensively, blog, and think a lot about how technology is changing our lives (yes, these last two things helped). I also already have a good grasp and use the Java 5 additions like Generics, Enums, for-each etc.

Here’s what I prepped (all book links are Amazon links):

• Read Effective Java (2nd Edition) – I credit this book with any pretense I have of being a competent Java programmer.
• Read Programming Interviews Exposed and worked through all the exercises – really helpful overview and refreshers on basic data structures like lists and trees. The recursion section was not as strong as I’d have liked (given my functional background) and advocated writing iterative methods instead, but other than that, it was a really good and helpful book.
• Read Coders at Work – there are an astonishing number of Googlers in this book, which gives an idea of the culture. But there’s also a ton of interesting programming history that I definitely had not been aware of, insight into how these people solve problems, and discussion of APIs, scalability etc.
• Reviewed Knapsack and Traveling salesman and NP-completeness in Combinatorial Algorithms: Generation, Enumeration, and Search (I also read almost the entire book and took a course on Combinatorial Algorithms in the fall semester) – honestly, I’m not a big fan of this book. I think it’s written in a fairly math-sy way. If you’re a programmer rather than a mathematician, solving these kind of problems using actual code is probably more helpful, and Wikipedia is almost certainly more readable.
• Worked through some of Java Puzzlers – helpful for getting you in the mentality of looking at bits of code and picking out issues in it. I wasn’t asked that kind of question, but I did need to look at my own code critically. IBM gave me a question like that in my phone screen for EB, and I understand that Google do use that kind of question too.
• Reviewed concurrency issues – deadlock, livelock, mutexes, locks, semaphores etc. When would you use the synchronized keyword in Java? How do you avoid deadlock? How do you avoid livelock?
• Reviewed tree traversal – in-order, post-order, pre-order. Depth-first search vs. breadth-first search. A*, Dijkstra etc.
• Reviewed balanced binary trees – red-black trees, AVL-trees, splay-trees.
• Reviewed graphs. Representation, minimum spanning trees, search etc.
• Run-time analysis.
• Coded 6 sorting algorithms – including the key O(n log n) ones – TDD-style (Test Driven Development – see this post for my test cases).
• Coded a hash table, using only arrays. Included: generics, dynamic arrays, lazy initialization. Again, test-first.
• Worked through all the practice questions that I could get my hands on – search for “Google interview questions” but don’t bother with the estimates or manhole covers, look for ones like these. Sometimes I coded in Eclipse, but sometimes in Google docs. I’d work with a friend who would review my code and ask questions.
• Talked to my friend who worked there a lot. Asked a lot of questions. He was absolutely amazing, and really helped me a lot with my prep. Even more than that, understanding why he thinks I would be a good fit and why he believes I can do it was really helpful in understanding why I would want to work there (yes it’s a cliche, and yes it’s Google but as one of my mentors pointed out, it is about whether you want to work for them nearly as much as whether they want you).

My Googler friend says I was “insanely well prepared”, and even I would say I was adequately prepared – but having gone through it, what would I do in addition to this stuff?

• More run-time analysis – do as much of it as can find code to analyze.
• Calculating sums. E.g. how can you sum the numbers 1-n? Work through the proof. Playing back the runtime analysis from my second interview, I have something that looks like: (n-1)(n-2) + (n-2)(n-3) + … + (3)(2) + (2)(1). Of course, I didn’t create it at the time so it became an upper bound of O(n³).
• Review Java library data-structures. At one point, I was literally said, “I know there’s a data structure that doesn’t take duplicates, I just can’t remember the name of it right now”. Of course it’s anything implementing Set. And of course I remembered later than afternoon.
• Review library methods for some key things – Arrays and Strings would have been helpful.
• Practice coding on a whiteboard or just on paper. You take for granted being able to insert a line here or refactor and it’s much harder to do that on a whiteboard. Also, it’s easy to forget the return statement – Eclipse never lets me so I tend to write declarations and return statement first and put my code in the middle – can’t do that on a whiteboard!

What next?

• Waiting.
• Waiting.
• Waiting!
• Whatever happens, hopefully I will be able to get some feedback.
• Code the interview questions (with test cases!)
• Finish Java Puzzlers.
• Reclaim my life – you might have gathered, I’ve spent quite a lot of time preparing.
• Investigate opportunities with other companies. In particular – meet with IBMers and see if I can find something that’s a great fit for me there.
• Debrief with mentors.