Tags: | Posted by Admin on 8/11/2006 11:50 PM | Comments (0)

Few things inspire as much dread and anxiety as the interview process. This screening process, which precedes any job in our industry, is of debatable value. It’s the worst kind of test: subjective, non-repeatable, and entirely qualitative. If the interview was a computer program, it’d be a thousand lines of spaghetti code held together by string, ducktape, prayer, the phase of the moon, and the color of your tie.

Each cycle of the IT industry highlights a new company as having the most hideous, awe inspiring, and mind gnashing interview experience. In the first dot-com boom, it was Microsoft. With their two day long process, as many as 8 or 9 hour long interviews a day (including lunch), and mind bogglingly open-ended questions (Implement malloc.) the interviewee was left haggard, drained, and desperately in need of a bathroom after too much caffeine and stress. All things change, however; this cycle, Google’s got the prize.

Trying to catch them all, Pokemon style, Google has swiftly gained a reputation for trying to pull in every top notch developer they can lay their hands on who survives the interview. Stealing a page from Microsoft’s book, Google interviews are renowned for placing intractable problems before interviewees with the panache of a sommelier.

For your delectation, here are the questions in order for my recent Google phone screen. Not quite the full grilling I expect I’ll get when I go there in person, but a good representative sample of what you might expect.

Q. Why does C++ have Virtual Functions?
A. I replied that usually the question was “how”, with discussion on thunking and such, but that the primary answer was to enable polymorphism of behaviors in objects — thus answering two questions for the price of one!

Q. What is the complexity of a search in a binary tree?
A. O(logn) — I’m really glad I covered this material during my review sessions!

Q. What is the complexity of a search in a hash table?
A. I initially screwed this one up (for some reason my brain had bounced to heaps) but backtracked and caught myself, and got out that calculating the hash was constant time to index into the bucket.

Q. When you form a connection with TCP/IP, what happens?
A. I guessed where he was going on this one, with the TCP handshaking procedure, so mentioning the SYN, SYNACK, ACK three packet handshake was the answer he was looking for.

Q. When you type in, say, “www.google.com” and press enter in your webbrowser, what happens?
A. This is one of those wonderful questions where you’re supposed to trace out every single bloody step of the process without running out of breath. Starting with the keyboard interrupt for the enter key, continuing to the windows event handling, and then onwards to the URL parsing, the structure of the DNS resolution, the request itself, and finishing the rendering of the page about summed it up. During this question, I made a point of stopping regularly and making sure things were still on track. This is a good technique I’ve learned to avoid wandering off too far from where the interviewer is looking to go; the feedback also serves to give the interviewer an opportunity to guide the discussion.

Q. If you have a phonebook, say of 3 million entries, and you want to provide searches through it as the user types in the name (think Microsoft Help Index’s, where the number of topics displayed gets pruned based on the user input), how would you do this?
A. I immediately answered “By using a real database, such as PostgreSQL”. Which was, of course, the real-world “right” answer, but not the particular detail the interviewer wanted discussed (though it did give me points for practicality, which is important). I scrambled for a bit here, fortunately mostly mentally, but came up with a datastructure involving indexs based on each character (i.e. “A’ starts at entry 0, B’ starts at entry two thousand and thirty nine, C’ starts … etc. etc.), and that at a certain point you would just do an iterative search as the bucket got smaller, perhaps a Fibonacci search or some such. The important parts, the interviewer said, were the practicality of the real database approach, the keyed list access, and the concept that at a certain level, it makes sense to switch algorithms and use a linear search approach.

All this took about a half-hour to go through, after which the interviewer and I talked a bit about the company, what it’s like to work for Google, the various products he was involved in, and so forth.

For all of you out there who will be interviewing with Google in the future, I hope this helps your phone interviews go well!

Original story

Add comment

  Country flag
  • Comment
  • Preview