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 some paperwork, an interviewer came and got me and took me to his office. The day began.

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. I learned an 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

I got a free lunch at the Google cafeteria, but that didn't mean I wasn't getting more interview questions. During lunch, I was asked: "How would you determine if someone has won a game of tic-tac-toe on a board of any size?" This 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 vehicle; how would you finish it?" I spent some time rolling ideas around in my head. I 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. The database could be updated once per year when you get your emissions checked (I know not everyone has to have their emissions checked, but it's 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 that's 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 be 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 (surprise!). 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 problem he had me do was: write a function to find the 2 biggest numbers in an array and return their sum. Then he had me write a function to find the K biggest elements in the array and return their sum, both in linear time. There were some good optimizations for this one too.

Then, I had to write a function that removed spaces from a given array of characters. I told him about the solution that Ryan and I 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 going to just divulge them (plus, I don't want someone to 'beat' my work).

It was a long day. I got there at about 11 AM to fill out some paperwork. I left after my talk with Katy at 4:30 PM. 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; that's a long time to be constantly getting questions and pressure to come up with better solutions.

How would you determine if someone has won a game of tic-tac-toe on a board of any size?