Interviewed at Google Pt.1

Today I want to blog about an on-site interview which I had at Google a while ago. Since I did not sign a non-disclosure agreement and only agreed on not taking photos in their office, I hope it is okay to write about this interview. Going to an on-site interview, is like reaching the next level, if Google is satisfied with your previous telephone interview(s). Due to summer-time and a lot of vacations, I had my on-site interview more than 1,5 months after doing the initial phone interview. This was very good, because it gave me extra time to brush up on some stuff. I read some books about data-structures and algorithms and practiced white-board coding a bit. I coded through a lot of sample questions from software interviews, which I was able to find on the net. However, all the questions during the interview were new to me, so I had to be spontaneous.

The job I was interviewed for, was Software Engineer in Test and the interview was held in Zürich, Usually the candidates are flying to the interview location one day in advance. That did not work for me, because I was already on another flight a day earlier. Instead Google booked two flights on the same day for me. which was OK. I arrived in time and signed in at the reception. As stated, you have to agree on not taking photos and you have to put some label identifying yourself on your shirt. Some minutes later I was picked up by my HR contact. She gave me a short office tour and set me up in one of the interview rooms. You could tell that Google is doing a lot for their employees. The Zürich office had a big fitness room with a personal coach. Free soft drinks everywhere, video gaming rooms, pool tables all that kind of stuff. My interview room was very small, maybe 3 times 3 meters and had a white-board. She handed me my interview schedule and I was surprised that it was six interviews, each 45 minutes long with a lunch break in between.

After some minutes the first interviewer came and we got into action right away. This first interview went really well. We talked a bit about continuous integration, my contribution to the Hudson project and about testing in general. Then the interviewer switched to a question about bash in Linux. We talked about how piping works under the hood. We spoke about the case where the first command is non-stopping one like "yes" or "tail -f". I learned that Linux is not executing the commands sequentially, like I thought it would. Rather it sends the output of a command to a buffer and the following command would use read and write blocks to work on the buffer. Time went and the next two interviewers came.

For some of the interviews, there are actually two people in the room. One of them being just a observer, that need to learn how to interview candidates. For the second interview, the interviewer directly put up a matrix on the white-board.

-4  -1   4   5
-3   0   6   10
 1   8   11  15
17   19  22  30

I did not realize, that the matrix was set up in a way that each row and each column was ascending - from negative into positive numbers. My task then, was to come up with an algorithm that, given any number, would return true or false if the number was contained in the matrix. The first idea I had was looking at the upper left number, reading the right and lower neighbor and select the neighbor which would bring me closer to the target number. Surprisingly this worked out but the interviewer was able to find a negative example. For the next attempts I tried starting from the lower right corner, starting from the middle element looking at all 4 neighbors and even go row by row running binary search. The binary search algorithm would have worked but the interviewer indicated that this is not the best solution and that I should try a different starting location for my first approach. After some discussion we agreed that it would be possible to start lower left, so that the row would be ascending and the column would be descending. If the number, we were looking for, was bigger than the current item in the matrix (lower left at the start) I would go to the right neighbor. If it was lower I would go to the upper neighbor. This neighbor becomes the next item and the algorithm would again check right and upper neighbors until either the element was found or there was no way to go further. Finally I wrote some Java code for this and the second interview finished.

It was lunchtime and someone from Brazil picked me up for a lunch-date. We went to the Google cafeteria and I got a free lunch. We talked about different things and it was nice to relax a little bit from coding exercises.