Interviewing with Google
7 Nov 2006
First, a little about me. I graduated for the last time in 2004 with a dissertation title of Correct Implementation of Network Protocols---it concerns maintaining the correctness properties of a formal network protocol specification through to an implementation. It also involved a compiler written primarily in Python (with extension modules written using Flex and Bison, some of my favorite hacks). I have about 15 years of experience as a sysadmin and system programmer, and spent about eight years as a Unix system administrator for the University of Texas at Austin, Department of Computer Sciences. Among other things, I wrote the semi-automated installation system that has put Linux on somewhere near a thousand machines.
Speaking of Linux, I have a 3.5-inch diskette with the 0.99pl14 kernel source on it somewhere. That was the first version I built myself.
My last job involved (as part of a team consisting of, well, me) writing a embeddable multiprotocol engine for a peer-to-peer digital media system, supporting multicast UDP and HTTP. My current job involves supporting a job-management system for middling-large (say, 4000 machines) heterogeneous clusters, built on top of LSF.
I like Google. A lot. Their services that I have used work really well. I've also got a inkling of what they do to make it work, and the stuff they're looking at is fascinating.
My first contact with Google was about eight months before the rest of this story plays out. I was contacted by a recruiter asking if I would be interested in talking about a job. I wrote back, saying that while I was, I had just started a new contract and did not feel comfortable considering leaving so soon. I suggested, somewhat faceously, that he contact me in six months or so.
Six or seven months later, when I was actually considering applying to Google, the same recruiter contacted me again. Excellent timing, I thought.
All of the interviews I have had with Google have been "technical" interviews---never dealing with trick questions or puzzles, nor with the usual interview garbage. Which is good---I'm not good with trick questions and tend to feel that most of the games interviewers play are unprofessional. 
The big question from the first interview was something along the lines of, "Assuming you have unlimited memory but need it to be as fast as possible, describe a function to find the number of set bits in a 32-bit value."
I caught the "unlimited memory" bit, and my first thought was to initialize a 2^32-element array with the number of set bits for every possible 32-bit value. The function becomes an array lookup.
I suspect that the first solution they usually see is a 32-iteration loop that uses bitwise operations to count the number of set bits. That, according to a couple of simple tests I later ran, is significantly slower than the alternative (although I don't have machine with memory the far side of 4GB).
(Upon further consideration I don't think the one I came up with is actually optimal---it will blow the cache and memory wait-states will kill you. I think a better solution (which is what I actually tested), would be something in the middle---a N-iteration loop using bit manipulations to support lookups in a 2^M-element array, where M*N = 32. Say, 4 lookups into a 256-element array.)
The interviewer seemed satisfied with my answers, though, and I scheduled a second phone interview.
Not too long ago during a phone interview, I was asked by someone who claimed to be a manager, interviewing for a research and development position, to "write" a function in C computing the n'th number in the fibonacci sequence. My response upon subsequently being asked to schedule a second interview was, "I'm not who you are looking for." If someone wants sample code from me, there is plenty available, and it is somewhat more interesting than functional programming's "hello, world".
[Edit 28 Jul 2010: After interviewing many more candidates myself, I would like to officially reconsider this position. If someone had publicly available source, I would be thrilled to look at it; in fact, that would be an almost automatic "Let's hire this one!". But no one does. And a "write a function" question is definitely needed. I still do not think it is appropriate on a phone interview, though.]
The second and third interviews, over the course of a month and a half, were similar. "How would you monitor something like AdSense?" and "What happens when you type a URL into a broweser?" were two questions. Fortunately for the last one, I wrote a pretty marginal DNS server as part of my dissertation research and so knew a bit about the goofiness that is one of the Internet's most important protocols. (He mentioned seeing cached DNS answers for hosts on networks that had ceased to exist several years before. That does top any DNS horror story I've seen---the nearest I can come was that UTCS was one of the last to turn on UDP checksums, or perhaps that one of the home internet appliances that were somewhat popular a while back was using UTCS for DNS service, without asking.)
Unlike many other Google interviewees I have heard about on the 'net, I actually enjoy these kinds of things. This is fun trivia. 
I was pretty satisfied with my interviews, and the interviewers also seemed tolerably happy. I got to the point of scheduling a physical visit and interview.
|||I just got a copy of George Varghese's Network Algorithmics. Apart from being condescending and suffering from some unfortunate grammar, it is something I would definitely recommend. Varghese has been doing this stuff forever, and knows what he is about.|
One of the downsides of Google is that all of their facilities seem to be located in the most crowded, expensive real estate that they can find. The one thing that prevented me from applying to Google before was their enthusiasm for Mountain View. The Site Reliability Engineering (SRE) position for which I was interviewing, however, exists at a large number of locations including, for me, two interesting possibilities: Kirkland and Dublin. (Unfortunately I don't speak German or French, so Zurich was out.) Both are expensive and crowded, I am given to understand, but Washington sounds like fun and who wouldn't want to work in Dublin?
I had been told that Google did all their physical interviews in California, but when it came to scheduling one I learned that they were to moving them out to the sites. I chose Dublin, and since I was going to be in Europe for a vacation, I scheduled a couple of days out of my trip to fly to Ireland, spend four or so hours on the griddle, and then fly back. Which I did.
I didn't get any Google lunches, although the snack bar looks nice. I did get to meet a goodly stack of really nice, enthusiastic, very smart folks. The interviews were more of the same, including the infameous write-code-on-the-whiteboard thing.
(My big question: "Write a C function taking two strings and returning a string containing one copy of the characters that occur in both." Hint: Spend some time looking at one of the strings and use an array of flags.)
The interviews also touched on standard deviations, regular expressions, and implementing tail(1). I had fun, but was pretty thoroughly wasted at the end.
I was pretty happy with my interview (and liked what I saw of Dublin a lot). So, apparently, were the interviewers: I got back home to the following mail from the recruiter there :
It looks like the Google interview process is coming to a successful conclusion. I am the Dublin-based recruiter for the Google roles and I hope to be able to submit you to the Hiring Committee in the US next week for a final decision on a job offer to be made. With this in mind, I will need to talk to you as soon as practicable about your current situation etc, but if I can get two names of references from you as soon as possible, that would be very helpful. I need to e-mail two of your previous/ current supervisors, so the details I need from you are two names, their title and the company they work for, how long you have know them and their e-mail addresses. Could you please let them know I would need references back from them by next Thursday morning at the very latest if we are to get you an offer the following week. [Emphasis mine.]
If you could also let me know a number to call and when would be a good time to talk on Monday that would be very helpful.
I responded with one reference (and started tracking down another---grumbling about people who don't stay put), and with my contact information.
|||I realize it is not good netiquette to post personal mail, and in fact that by posting this note and those mails I've pretty much shot any chance of working for Google, ever, period. But I seem to having a hard time with this. Besides, the cease-and-desist letter should sell well on Ebay.|
The next thing I heard from Google, however, was about three business days later:
Tommy M. McGuire,
Thank you so much for your interest in Google and for taking the time to come in and interview with us. The hiring committee carefully reviewed your experience and qualifications and determined that there is not a strong match for a 'Software Engineer, Google.com - EU Headquarters' position at this time.
We hope that in the future a position at Google arises that will be a better fit. We'll keep you in mind as Google continues to grow and hope you might consider us again sometime down the road. Thanks again for considering Google. We wish you well in your future endeavors.
I felt like I had been kicked in the stomach. I admit the failure of cynicism, but I was really looking forward to working for Google. Now what was I supposed to do?
I wrote back, thanking everyone, and asked about the possibility of a position in Washington. I got no answer at all.
Given the lack of response to my questions, I submitted an application for the position in Washington. I was called the next day by a Google recruiter, but was unable to talk. I replied by email that I was familiar with the Google process, and received the following response:
We received your resume and would like to thank you for your interest in Google. After carefully reviewing your experience and qualifications, we have determined that we do not have a position available which is a strong match at this time.
Thanks again for considering Google. We wish you well in your endeavors and hope you might consider us again in the future.
Sincerely, Google Staffing
Recently, about three weeks after the above events, I get this:
I am a Recruiter for the Google.com Engineering Group at Google. This is the most dynamic and challenging group at Google. This group is responsible for the Google website from start to finish.
I wanted to see if you may be interested in opportunities in our Google.com group at Google. We are constantly seeking extraordinary engineers with a combination of expertise in software development, Unix/Linux systems, and networking. We have positions open in the USA in Mountain View (CA), Santa Monica (CA), New York (NY), and Kirkland (WA) as well as Dublin (Ireland) and Zurich (Switzerland) and we could relocate you to any of these locations of your choice. I am enclosing a job description of a position that I feel may be a great match for you.
If you feel that this position is something that may be of interest to you, please send me an email with your current CV/Resume, so we can schedule a time for me to call you to discuss this in greater detail. If you are not interested or available, but know a friend or colleague who would be interested in this opportunity, feel free to forward this information to them.
That is a rough clone of the original mail I received. Sigh.
I have no idea why I got the ol' blackball. Judging by the comments in the email above, as well as my feeling from the interviews, I don't think the reason was technical.
I do think I understand why I don't get responses from the recruiter's afterward, though. I rather suspect that they are paid, or at least incentiveized, per the actual, hired employee and that they are operating in a target-rich environment. I'm apparently not hirable, and any time spent on me is therefore wasted. Something like leaving toasted hardware in the rack until you physically run out of space---it's cheaper to ignore it and install new stuff.
As I posted this note, I received the following reply (two weeks after the last sequel):
Sorry for the delay in my response. I did check on your status in the system and did notice that you have had an onsite interview for the Dublin position and it has also been mentioned in that that you were interested in Kirkland as well. Now that the hiring committee has passed on your application the best we can do is to revisit in 10 more months for the same position and group, should be interested still at that point of time.
So it looks like Google does have a permanent file on me.
I received a couple of emails from two different Google recruiters in early 2010, one from Dublin. I responded with my resume, and received in return the standard beginning of their interview process. I did not have the heart to reply.
I think from now on I'll just refer them to this page.
Oh, and I saw Mark Dennehy's post describing two roughly similar sets of interviews with Google. Nice.