Submitted resume online on 2009-09-15.

Received an email from someone in Staffing on 2009-10-07 asking for my location preferences, whether I am eligible to work in the US, and my actual date of intended graduation.

Received an email from a recruiter in the Seattle/Kirkland office on 2009-10-08 to schedule a phone call. They stated we would talk about Google's recruiting process and focus on my background, education, and career interests to ensure that I speak with engineers who have a background and interests similar to my own.

Received a call from the recruiter as scheduled on 2009-10-14. We talked about Google's recruiting process, but not so much about my background, education, and career interests. I made sure she had my latest resume and asked some questions about work-life balance in the Seattle office and also about Google's IP/non-compete policies. After the call, I emailed times I would be available for two back-to-back technical phone interviews.

Received an email from the recruiter on 2009-10-15 confirming my scheduled time for two back-to-back technical phone interviews. The email included information about types of software engineer positions in the office and links to various Google pages (Labs, Code, lifeatgoogle YouTube channel) and Yegge's advice article. They also asked me to answer a few preliminary questions about myself to ensure I don't have any conflicts.

Received a call from the first Google engineer as scheduled on 2009-10-20. He described his work in Gmail on contact management and chat, mainly using C++. He asked me to describe a big project I've worked on, and I told him about my thesis and its accompanying software implementation. He then asked some technical questions. I asked him about his work-life balance in that office and if working there is anything like what you read about in Hamming's "You and Your Research."

After the interview, I hung out for a couple of hours waiting for the next phone call, but it never came. I contacted the recruiter, and she informed me that the second interviewer was unable to access his calendar and therefore unable to call. We rescheduled the second interview.

Received a phone call from the second engineer as rescheduled on 2009-10-23. He told me how he works on Google Maps and used to work on Talk at the Kirkland office. He asked me to talk about my thesis, and I did, but for some reason, I got really nervous talking about it this time. My voice was shaky for a while. After that, he asked two technical questions. I asked him about his work-life balance at that office and what his most interesting use of Google's tremendous resources has been.

I was told by both engineers that I would hear from the recruiter soon, so I waited for about a week and a half. On 2009-11-04, I emailed the recruiter asking if we would be proceeding with the interview, and later that evening, I received a call from her stating the engineers enjoyed talking to me but we would not be moving forward.

The overall process was enjoyable, even when I was an anxious wreck. The technical interviews boosted my confidence, even though I stumbled on the easiest questions (postorder & basic C programming). The first engineer was far more polite & humble than the second one, but the second one was certainly civil enough. The recruiter was kind, easy to talk to, and obviously put effort into answering all of my tough questions about the Seattle/Kirkland offices & Google policies.

I learned that the Seattle/Kirkland offices tend to be a little more laid-back than the Mountain View office. Also, Google does make you sign a non-compete, but it's not overly draconian. Many engineers run their own companies after hours and are even allowed to use AdWords and whatnot, provided they sign some agreements. I encourage you to go through the process for interview practice if nothing else.

Describe a balanced binary tree.

When would you want to use a balanced tree rather than a hashmap?

Describe preorder, inorder, and postorder traversals.

Write a function, preferably in C or C++, to reverse a string.

Describe the design of a most-recently-used list, such as the "Recent Files" menu in Microsoft Word. It has two public methods: getList() and access(str), which retrieve the list and mark an item as accessed, respectively. The list has a maximum number of items it can hold (e.g., 5) and should not contain duplicates. Describe the data structure used and the running time of both public methods.

You have a data structure of integers, which can be negative, zero, or positive, and you need to support an API with two public methods: insert(int) and getMedian(). Describe a data structure you would use to support this API and the running time of the two methods.

Imagine you're writing a function that takes an array of integers and an integer. It needs to return true if any pair in the array sums to the second argument. The array can contain negative numbers, zero, or positive numbers. Describe how you would design this function and what its running time would be. Consider the trivial O(n^2) solution, an O(n log n) modification, and a linear O(n) solution.