First off, I’ll spare you the suspense. I did NOT get offered a job at Google… but I did have a lot of fun!

I was first contacted back in December by a Google talent recruiter. Mike had been in the middle of his Google interviews, so it was an exciting time.

Was I interested? Definitely! There are few in the software industry that wouldn’t jump at a chance to work for Google - one might call them the Mecca of the software industry (but only if it doesn’t offend anyone; if it does, let’s just call it a pretty neat place to work).

I first received an email from the recruiter asking if I was interested, and where I wanted to look for a position. She told me that she thought there was a good fit for me for a Java position in Mountain View, but I asked her about looking for a job in Waterloo. Was it a mistake? Maybe, but she did mention that I could look into a position in Mountain View if the Waterloo position didn’t work out.

Over the Christmas holidays, the recruited emailed me to let me know that the Waterloo position was a C++ position, and that perhaps I would have a better chance finding interest in Mountain View, but the next day she emailed me back to let me know that the Waterloo offices were interested.

I was excited. One of my goals, new years resolutions if you will, was to step out of my comfort zone with regards to software development. It seems that every script I needed to write was being written in Perl and Bash script and every piece of software I was writing professionally was in Java. I wanted get out of the habbit of relying on Java/Perl/Bash. This seemed like a good opportunity as C++ is one of many languages I wanted to work on this year.

Well, I guess what you really want to know is what sorts of things I was asked on my interviews. Well, before that, there are a lot of things that need to be reviewed; first and foremost, asymptotic notation and complexity. The interview questions consisted of asking me to come up with a semi-high level algorithm and then to explain the asymptotic complexity of each part as I went along, and then what the final complexity of the algorithm would be.

The next thing that should be reviewed is your basic sorting algorithms and their respective complexities. I made sure to know heap sort, bubble sort, selection sort, binary sort, merge sort, quick sort and insertion sort. Also important, you should know the memory requirements that each algorithm uses to run (in big-O notation). I was asked in my first interview to not only minimize the runtime, but also the memory footprint (ie. insertion sort although is O(n^2) in runtime, it is O(1) with regards to memory).

The next thing I reviewed was memory structures. Hash’s, binary trees, n-tier trees, etc and the properties that each one possesses. If the interviewer asks you about a binary tree, make sure you know the properties that make a binary tree special so that you can leverage it in your solution.

Now, on to the interviews.

The first interview started with a quick introduction from Steve about where he worked within Google (Google NYC) and what he worked on there (Google maps). Then it was right down to business. The first questions (from my memory, so don’t blame me if it isn’t 100% correct) was as follows:

Given a binary tree, and two leaves, can you find the lowest common node of those leaves?

I won’t give you the answer here. I’ll let you work it out for a bit and perhaps if there is enough discussion in the comments, I’ll leave the answer there. When giving my answer to the interviewer, I think I could have been a lot clearer. I was nervous; very nervous. I really didn’t know what to expect, even though Mike prepared me the night before. The answer I gave was right (as far as a solution and its complexity) however, about 10 minutes after completing my interview, I figured out a way to better leverage the binary tree structure which would have also given a much clearer answer. Also, I was asked to minimize both the runtime and memory usage in my solution.

The next interview I had was about 2 weeks later and it was with Chris (also from the Google NYC offices) but he worked for Google’s blog search. This one started a little different; he asked about what I had worked on at my previous companies and more specifically what I felt the coolest project was. I had so many to choose from at Pason, but I went with the biggest and more complex, the DataStream project. After that, he asked me my ideal problem to solve was if I could leverage all that is Google. This really caught me off guard. I should have known it was going to come; I even read about someone who was asked a similar questions. I spent so much time preparing for the technical part of the interview, I forgot about the lighter part. I wish I could have done it over. My answer was a lame scheduling mash-up for Google maps. I really needed to think bigger… hell, my friends and I have talked for years about cool stuff that we could do if only we had a company that was as big as Google.

I felt like an idiot, but what can you do. No sense dwelling on that. There were two technical questions that comprised this part of the interview. The first was:

If you were designing the Vector class in Java, how would you code the add(Object) method?

Deceptive; not hard per se, but there are a few things that need to be worried about when solving this question.

The next question was the algorithm question:

If you were given an unordered set of plane tickets which represented legs in a trip, can you figure out the order in which to use the tickets?

This was a really fun problem to work on, and again, I’ll save the answer for the comments. Remember that they want you to come up with the lowest runtime algorithm that you can.

Three days after I completed this interview, I got my letter letting me know that they were not going to be offering me a position. Was I disappointed? Sure. I have to admit that I thought about how neat it would be to work at Google, but it wasn’t all bad. It helped me fulfill another one of my new years resolutions - to get back into studying the “science” of computer science, and although stressful, the whole experience was a lot of fun.