The Google Interview

"...Despite Google’s terrible track record so far for being organized and getting things done, I was still excited. I was so excited, I unfortunately could not sleep the night prior.
I drive to Google’s campus and wait about 30 minutes. The person I was supposed to meet went on a trip and did not tell me except via an automatic email that I received after emailing him asking “Where are you?” The recruiter comes along as backup and finds me, and takes me to my first interview. She asks me if I am ready, if I have used Google products before, and ensures that I will do just fine on the interviews as long as I am confident.

Interview #1: Maps and Sets

The first interviewer came and was 15 minutes late, but did get started right away. He asked me the following question

Create a data structure that has fast insertion, removal, membership testing, and random selection.

I poke around for a little bit and end up writing a chart of three or four elementary data structures, outlining the time complexities of each operation, but I suspected there was something better, which was confirmed by the interviewer’s push to see if I could develop something better. So next I try to mix the best attributes of one data structure with another. After some thinking, I finally got the details hammered out and mixed a hash table and a vector to produce something that has amortized constant everything. I felt victorious, especially since it is something I had to discover on the fly. For those interested, the code is here.

Interview #2: Servers and Data

The next interviewer came in, and he totally crushed me. I’m not even sure if I remember the question correctly.

If you have n servers that take requests, and server Si can take a request every ti seconds, and you need to distribute requests to them as efficiently as possible, how do you do it?

I fumbled around a lot, trying to create an efficient loop, modding a timer and switching to the machine that needed the request. Then he asked how I’d add more machines at runtime, and I turned this loop with fixed time points into a data structure that associated ti to Si. The interviewer thought this was completely unsatisfactory, and said “I wanted you to use a priority queue. We will just move to another question.” I felt pretty bad about this, but he asked another question.

If you have n machines with a 10 GB string of characters on each, how do you find the most common character?

I got this one I thought. Just ask for a distribution of each character from each machine, send the tables to a master machine which added them up and found the character with the highest frequency. Then he asked questions like “If we make the network faster, does it make sense to send over all the data to one machine?” I respond “no”, and explain that it would actually degrade performance. Finally, toward the end, he asked

Now suppose you are in the middle of Africa, each machine is on an Edge network, and each packet between the machines costs $1.00. Write a solution that minimizes the cost.

There was only 5 or 10 so minutes left, but I thought that maybe I could incrementally determine the maximum. I started off by saying that each machine calculates a frequency table, but instead of sending the whole table, the master machine asks for the most common. I start describing very roughly the algorithm for doing this, but I don’t think I was getting the details and corner cases right. Time was very pressured, and the interviewer expressed dissatisfaction with what I’ve done. “Time’s up. Maybe you can ask your friend there what the answer is.” My friend was one of the people who recommended me and took me to lunch. He didn’t know the answer off the top of his head either.
I felt a bit unhappy with my performance, but thought that I got far enough that I must have did at least okay. I ate lunch with two of the people I know at Google, and one of them looked at my “docket” and exclaimed “this question is illegal.” He didn’t tell me which one but he wrote something down and gave it back to me. We finished lunch talking about language runtimes, Lisp, and Go.

Interview #3: Trees

This was probably the most straightforward interview. It started off with a discussion about languages. What’s good about C? What’s bad about it? What languages solve those problems? What languages introduce new ones? I mostly discussed type safety and memory safety, two things that I deal with most often in industrial code.
Then he moved for a technical question. I’m not sure if I remember the question accurately, though.

Given a list of pairs (a,b) where a is the number of a node and b is its parent, construct a tree and return the root.

There may have been a third value c, but I fail to remember what it was if it even was.
I blazed through this. I wrote the code down to do so correctly and quickly the first time, and the interviewer actually said “I probably should not have asked a Lisp programmer about trees.” We spent the rest of the time (there was a lot of it) talking about Google and his position. I was particularly keen to figure out if he and his peers were solving tough problems or if most of the work was just tedium. I at least got an indication that he enjoyed what he did, but my question wasn’t really answered. Interview ended, and I felt good again.

Interview #4: Intervals and Regexen

I get to my next interview, performed by a very nice man with a quiet, Russian accent. He asked me the following question, though he asked it more cryptically than I write:

If you have a set of n disjoint, sorted intervals I=⋃nk=1[ak,bk], and you have an interval I′=[x,y], compute I∪I′.

I’d worked with interval arithmetic before, and so I was in somewhat familiar territory. I quickly noted all of the possible cases, and proceeded to implement a solution that was actually more general than what the interviewer asked. I instead wrote a solution for the problem of computing I efficiently given I1,…,In+1. It is a very easy generalization, and the interviewer saw that I think. Simplifying the union took no extra space and only took linear time, which was a sharp lower bound because we have to examine each possibly-overlapping interval at least once. The code for this is here.
He then proceeded to ask me questions about regular expressions, then asked me to write the regular expression for a variety of things.

Write a regular expression for floating point numbers.

I went through it, and even talked about what the DFA would look like, and describe why it would be very efficient to match.
I was even happier. Maybe lunch had helped! I thought this interview was a roaring success. We even had plenty of time to talk about Google and other things.

Interview #5: Dynamic Programming

The last interview was mostly okay.

Given a set of Lego bricks of height 1, 2, 3, and 4, each colored differently, write a program to compute the number of ways of constructing a tower of height n≥1.

This wasn’t a foreign question. Very quickly, I wrote down the typical exponential solution; just recursively count. It looks almost exactly like Fibonacci, but with four branches instead of two. I said it could be made a lot better, and computed in linear time. Here, I choked up a bit. I’ve done this a million times before. I started writing the iterative solution in Scheme, but I wasn’t getting the base cases quite right. I had to write out a few of the iterations, and after all that, I finally wrote it down, relieved. It felt almost scary, to forget something so trivial. The interviewer asked me if I could think of another way, and I couldn’t. Then he wrote down a 4-by-4 square matrix, and I basically completed his sentence: “Oh yes, of course, a particular right triangular matrix that you project onto the first dimension by right-multiplying by a unit vector after doing binary exponentiation to n, just like Fibonacci.” I wrote down quickly using mathematical notation what the binary exponentiation looks like and what the projection looks like. He agreed, and we sat down and chatted some...."

Source: Link