The Google Interviews

I’ve just finished an hour and a half on the phone doing two interviews for a software engineer intern position at Google. Those were definitely the most interesting, challenging and enjoyable job interviews I’ve ever done.

Interview #1

My first interviewer was an engineer in the Machine Translation Group where I’m applying to work. They handle all the software and systems for Google’s language translation services and are mainly looking for someone to do optimization work.

He started right off with the theory questions. The first 40 minutes were spent having me walk through creating algorithms to solve two problems and then analyzing their asymptotic run time behavior. I don’t want to give away the problems here, but one involved searching text and the other finding a specific statistic among a set of numbers too large to fit into memory, parallelized across multiple computers. I didn’t come up with the optimal solution for either answer even with a couple hints, but I at least felt I showed I wasn’t clueless and came pretty close.

For the text searching problem I worked through starting with a binary search of some strings, to building an index to limit the range of the binary searches, to expanding that index to include more and more information. I was slowly getting closer to building some type of tree as that index but wasn’t able to get there in the limited time we had.

The second problem was the first time I’d really thought about parallelizing any algorithm. I split up the data across k computers and came up with an algorithm that’d run in some complicated (n/k)*log(n/k) + (n/2) time to finish the problem, knew I was overworking it, but couldn’t come up with a method that’d avoid the extra work.

I still think I did alright, and the interviewer told me he didn’t expect me to know the algorithms and data structures he presented as faster solutions. I at least showed that I can develop algorithms to solve a problem and analyze their running time.

That left only a couple minutes before the next interview to talk about some of my experience and the job. He brought up W3Counter which I mentioned in my cover letter (not by name, but briefly by description), and I talked about the design of the database for efficiency concerns and also mentioned the CPU and memory limits I’m hitting and what I’ve been doing to get more out of the server.

Interview #2

The second interview was a shorter one. This interviewer told me at the start he was screening for technical ability. We again started out with a problem and runtime analysis which I fumbled through moreso than with the first interview. I was thrown off a bit by being asked to analyze a purposely inefficient algorithm with lots of factorial and large polynomial components.

Then I was asked to implement one of C’s basic memory management functions. Yep, write the code over the phone. The interviewer was aware I had C++ experience but not much with C and probably chose such a simple function for that reason. I gave him the code, there wasn’t much to it, and that ended the technical part of the interview. I’m not sure if it would’ve continued further if I had shown more skill with C or if that was just all he wanted to ask.

That took only about 25 minutes in total, followed by about 5 minutes where I asked a few questions about the work environment at Google, and then it was over.

My Thoughts

I want to get this job. Google is about as good a work place as a software developer could ask for, everything developed there has actual users, and there are always challenging problems to tackle. It’s the type of place you’re free to spend a little extra time refactoring code for efficiency or trying a novel algorithm for a problem. And while I still have interviews with Microsoft coming up, I’m more comfortable in the Linux environment.

My hope is that the first interviewer has some influence as part of the team I’d be working with. I think I did a better job talking through the problems with him, and had an interesting conversation as we both tried to recall the details of the k-th order statistic selection algorithm that works kinda like a quicksort (pivoting around medians of medians to guarantee a worst case running time of n*log(n)) when I thought that might be applicable to one of the problems.

Now I wait.

Posted on December 28, 2006 in Personal

More from this category

  • Mike

    Sounds a little more complex than displaying a result set with PHP with checkboxes to delete records :)

    Good luck with it Dan

  • http://www.htmlhelpcentral.com john2k

    I saw a link to this site in your signature at SP. Anyhow, just wanted to wish you the best of luck with getting the internship at Google. Good luck with your upcoming Microsoft interviews as well. A job with either would be quite an interesting opportunity.

  • http://www.ilovecode.com sara

    This sounds like an interview I had with Amazon.com when I was graduating from school. My first interview was over the phone and it went pretty well. Then I had an in-person interview which I thought I nailed. There were a lot of theory questions and algorithm analysis questions. In the end though, someone else got the job. It was a great experience though!

    Good luck on getting this google gig!

  • Pingback: Dan Grossman : Google Interview Scheduled

  • Pingback: Dan Grossman : The Google Rejection

  • Michael Ellis

    Google seems to only be interested in hiring aspergers syndrome babies who can spit out the big-O of a obscure algorithims without (gasp!) having to look it up in a book. I know several extremely talented software developers who’ve interviewed there and not been made offers because they’ve spent their careers focusing on the difficult things that matter in software development, as opposed to the minutae that anyone with a room temperature IQ can look up when they come up. No surprise that their products and services are a complete mess.

  • Me

    Nice post. I have heard from people that the questions asked are puzzle-type questions. Ones similar to http://www.technical-interview.com, for me I have not gone through one and planning to apply to Google once I graduate :)

  • http://www.freesitestatus.com Fahd

    That was an interesting read, Dan. Any update? Its been almost a year now.

  • http://www.dangrossman.info Dan

    There have been several updates (see the trackback) and I went to work for Microsoft instead.

  • http://www.hotcelebrityimages.com/ Celebrity

    excellent read.

  • Joe

    It seems that google goes through a lot of time and effort to pull “the best and brightest” that were forged by other institutions. If google has so much time and energy to throw their best engineers at this lengthy costly process why not just bring a bunch of people on that have “potential” and then throw in a few oddball candidates that they wouldn’t touch with a barge pole and mix them up and put them on 2 week projects and see who shakes out. Do this over a period of say 6 months (because not everyone is going to shine right away) and at the end of that stint, pick the ones who work out the best. In the end it would cost less money and they would have some production (or near production) ready results and it would waste less of their top engineer’s time. It just seems to be that all this is doing is costing google a ton of money and wasting other developer’s time who’s talents are far more needed where they currently are that was built up in a culture outside of google. The end result is just going to be an elitist group of computer scientists and it seems that could only serve to hurt the company’s end-game because it’s the mix of backgrounds that makes great things happen. Example, look at the tech + creative mix at Apple.

  • http://www.catonmat.net/ Peteris Krumins

    Hi, it was an interesting reading.

    I’d like to correct you on the k-th order statistics algorithm. The expected running time of this algorithm is O(n), and not (n·lg(n))!!

    Also the worst case for this algorithm is O(n^2)!

    There is an algorithm by Blum, Floyd, Pratt, Rivest and Tarjan (by 5 gentlemen) which has worst case O(n) running time, but it is rarely used in practice because of the constant term being too big!

  • http://www.catonmat.net/ Peteris Krumins

    I forgot to add that I am writing an article series on my blog about MIT’s “Introduction to Algorithms” course. The series starts here:

    MIT’s Introduction to Algorithms, Part I