Google Interview Questions & Reviews in Kirkland, WA

Interviewed Mar 2008 in Kirkland, WA (took a day)

Background
I had a screening interview with Google, and then they invited me over to their Kirkland, WA office to do an 'interview loop' there.

Interview #1
After filling out a bit of paperwork, interviewer came and got me, and took me to his office. And so began the day. We chatted for about 20 seconds, and then he gave me a programming problem. The problem was: "Write the 'grow' function for a C++ vector class". Easy enough.
The second problem he gave me was a bit more difficult: Reverse a linked list. It took me about 15-20 minutes to come up with the solution and code it. But, I learned one important 'trick' to these types of interview questions. When you figure out an algorithm that takes a duplicate data structure, you can usually 'massage' the given data structure to get the solution you want.

Interview #2 - Mark The Lunch Interview
So, I got a free lunch at the Google cafeteria... but, that didn't mean I wasn't getting more interviewing questions. During lunch, I got the question: "How would you determine if someone has won a game of tic-tac-toe on a board of any size?". This really took me longer than it should have to figure out. The crazy thing is... no matter how big the board is, the solution is constant time.
Then, he gave me a pretty cool question: "The government wants cars to keep track of whether or not they are speeding. The unit to determine this is already able to determine the speed of the vechicle, how would you finish it". So, I spent some time rolling some ideas around in my head. Determined it wasn't feasible to 'read' speed limit signs reliably from a car. Then I thought if the car had a Mapquest-esque database of speed limits, and a GPS to report coordinates to the unit, you could determine if the car was speeding. And, the database could be updated once per year when you get your emissions checked (I know not everyone has to have their emissioned check... but its a good idea).
Then we went back to Mark's office, and the coding questions started. First, I had to write a binary search for a sorted array. I wrote it recursively, because thats the way I learned it. Then he had me write it iteratively... which wasn't too hard either.
Now, you've got an array of size 10^6, with the numbers 0 through (10^6)-1. The array has duplicate entries, so there will me missing numbers. Write a function to find one of the missing numbers. The solution should be in linear time.
Mark was a cool guy, and he'd be fun to work with.

Interview #3
Mark and I actually talked for quite a while about my senior design project. Then, he asked me to code for him (suprise!). Given a sorted array of integers, write a function to remove any duplicates (e.g. 1,2,3,3,3,4,4,5 would go to 1,2,3,4,5). I came up with a solution to this, but it wasn't that good... so we talked about a way to make it better. This was my 'worst' interview... but even this one wasn't too bad.

Interview #4
The first one he had me do was: write a function to find the 2 biggest numbers in an array, and return the sum. Then he had me write a function to find the K biggest elements in the array, and return the sum. Both in linear time. There were some good optimizations for this one too.
Then, I had to write a function the removed space from a given array of characters. I told him about the solution that me and Ryan had discussed and how it applied to this problem. Then we talked about a few of the finer points of this problem. I didn't end up having to write any code for that problem, which was good... because my shoulder was getting sore from writing on whiteboards all day (seriously... it still hurts).

Wrap-up with Recruiter - Katy
Then I went and talked with the recruiter about how the day went, yadda yadda. She told me I'd hear back in 5-7 business days.

I spent lots of mental energy coming up with the solutions to those problems... so, I'm not to just divuldge them (plus, I don't want someone to 'beat' my work :)

It was a long day. I got there at about 11AM to fill out some paperwork. I left after my talk with Katy at 4:30PM. It was 5.5 hours of almost pure 'testing'. It was F-U-N though. I learned a few new algorithms, and discovered a few too. It was also D-R-A-I-N-I-N-G... thats a long time to be constantly getting questions and pressure to come up with better solutions.