If you follow my Twitter, I may have already given away the ending to this! But as a continuation from my first round, here is my experience for my second (final) on-site with Google two weeks ago.

What Did I Do To Prep?

Things were a little hectic with the end of Extreme Blue and our trip to New York, and my plan to read The Algorithm Design Manual (Amazon) on the bus fell apart somewhat after the bus broke down, I went 5 hours without water in the heat and had a small breakdown. There was (apparently) a hilarious ending that I don’t remember in it’s entirety, which I won’t be sharing on the internet…

That said, I did make it through section 1 which was really helpful and the book actually contains suggested interview questions – great for preparation. I also read more of Java(TM) Puzzlers (Amazon) and started Making it Big in Software (Amazon – good read, mostly for once you’ve made it through the interview though I think).

How Was It?

It was fun. I got to hang out with smart people and code for four hours! My first interviewer was a woman, who was super nice and that really helped. My lunch-buddy was a woman too, so even though diversity at Waterloo is not great it didn’t seem that bad at the time! I don’t know if they do that deliberately or not. I didn’t find the questions too tricky and could answer them all, probably because I’d done enough preparation that I’d got into that way of thinking. I had 3 technical interviews, and one architectural one (designing an API).

Takeaways

Much the same as last time. Knowledge of APIs, particuarly String, Collections and arrays, but additionally:

• If coding in Java, know 1.5 features. One of my interviewers was more C++ and hadn’t coded in Java 1.5, and so when I used a for-each they asked the question, and I could answer – for-each loop added as of 1.5. Generics, too. I coded one question using Generics. Some people can find the syntax tricky, so if you’re going to use it (and IMO you should for good design) – know it.
• Immutability! In the API-design question immutability made the second part of the question (how would you change it so you can do X) immeasurably easier. Know when you want to have immutable classes, and use get/set and visibility accordingly.
• Trade-off’s between space and time. For another question, before I started coding I could say, I can do it in this complexity with this space overhead, or this (higher) complexity with no space overhead. In the end, we coded both. But I started with the easier one!

Overall

Unusually for me, I was happy with how I did! Despite having less time to prepare for this round, I’d remembered the stuff I’d gone over for the last interview and left feeling that I’d done the best I could.

Incredibly, I heard the following day (!) that I’d made it through regional review, my references were collected the day after and I received an offer a week after that. The HR guy in Waterloo was amazing in terms of keeping me in the loop and I got emails from two of my interviewers (one from each round) congratulating me. I’ve read (and heard) about people having a miserable experience interviewing at Google, but that was not at all my experience. The process took a couple of months, but that was because of my schedule and not them. I really liked everyone I interviewed with and everyone I encountered was super nice. I’m really excited about going to work there – and frankly still in shock that I made it!

I start in January. I guess I’m leaving Ottawa and moving to Kitchener/Waterloo. Bring on the next adventure!

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.