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.

AddThis Social Bookmark Button

2 Trackbacks to “The Google Interviews”

  1. Trackback from Dan Grossman : Google Interview Scheduled on January 2nd, 2007 at 2:59 pm:

    […] Update: You can find how the interview went here. This post is tagged: google. Feel free to trackback it, or even digg it. […]

  2. Trackback from Dan Grossman : The Google Rejection on January 5th, 2007 at 9:29 pm:

    […] Looks like I won’t be packing up and moving out to California in April; Google turned me down for the job I applied to. Maybe that second interviewer’s questioning really did mean they wanted a C coder despite the job description listing C++. Hi Daniel, […]

11 Responses to “The Google Interviews”

  1. Mike
    December 28th, 2006

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

    Good luck with it Dan

  2. john2k
    December 28th, 2006

    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.

  3. sara
    January 2nd, 2007

    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!

  4. Michael Ellis
    February 7th, 2007

    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.

  5. Me
    February 18th, 2007

    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 :)

  6. Fahd
    September 29th, 2007

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

  7. Dan
    September 29th, 2007

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

  8. Celebrity
    June 12th, 2008

    excellent read.

  9. Joe
    June 22nd, 2008

    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.

Leave a Reply

You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Network Activity

Visitor Boost and Targeted Visitors have received 17 orders today and 15 orders yesterday.

W3Counter is currently processing -39 queries per second for 12,750 websites.

Website Goodies is hosting 79,835 guestbooks, 12,159 counters and 7,276 polls.

Award Winning Hosts has collected 182 customer reviews of web hosts.