The Google InterviewsI’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.
Tags: binary search, faster solutions, Google, inefficient algorithm, k-th order statistic selection algorithm, language translation services, Linux, Machine Translation, Microsoft, purposely inefficient algorithm, software developer
 |
Self-promotion
Recent Comments
Activity Stream
Popular Posts
|
  |
|
|||
Home About Archives Projects Links
|
Mike
Michael Ellis
Me
Joe
[…] Update: You can find how the interview went here. This post is tagged: google. Feel free to trackback it, or even digg it. […]
[…] 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, […]