January 2011, Mt. View campus

Visited Google five years ago; I was rejected that time. This time, a recruiter contacted me again and offered me the chance to interview again.

The Silicon Valley rumor mill brought several facts about interview practices: each interviewer has to submit a rather detailed report to the hiring committee, recording everything written on the whiteboard and allegedly even what you say. Sometimes, two interviewers talk to the candidate; in such cases, the second person is a trainee. Sometimes, there are two rounds if Google is uncertain. The candidate has to select their preferred programming language for the interview. My choice was C, as I was applying for what the recruiter called "kernel" positions in the ChromeOS team.

I was first met by the recruiter. He spent 10 minutes with me. I asked about the practices above. Although he confirmed them, he downplayed the "exact recording of what the candidate says" part. He answered that the written report on a candidate is about 1-2 typed pages on average.

I met a total of 6 people: 5 technical, and one at lunch.

First Interviewer:

• General discussion on testing methodologies (why unit tests might fail?).
• Asked me to code review some C++ code, even though I explicitly selected C as my preferred language. I couldn't say much as I don't use C++.
• Asked to implement a C++ method for a class "arbitrary reader," given we have a class "4K reader" which can only read 4K blocks.

Second Interviewer:

• Given two binary search trees, write a function that tells if two such trees are the same (i.e., same information in the nodes, same branching to left and right at every node).

I presented a recursive implementation. I was asked to do a non-recursive version (the question wasn't about a better solution, say, with constant memory). I proposed to change the recursive algorithm to a non-recursive one using a user-defined stack (a formal transformation, rather boring but doable, like FORTRAN people do it). I demonstrated that, but the code was messy with gotos, etc. I was asked about complexity. Both recursive and non-recursive versions required linear stack space in the worst case of pathological one-sided trees.

Third Interviewer:

• Reverse bits in a 32-bit integer.
• Given two large files with 64-bit integers, produce a file with integers that are present in both files and estimate the O(?) complexity of your algorithm. I proposed a solution of splitting both files into n chunks (k integers in each) and solving n^2 subproblems while incrementally updating the result by merging sorted files of partial results (we would need to sort each chunk once). After the algorithm was finalized, we checked the complexity, and it was something cubic by n and k. Too bad. The interviewer guided me to the solution of sorting both files and finding the intersection by merging; this was better. As an afterthought, I still think that when files do not have a large overlap, my solution might be better as sorting the original large files is not required (k should be selected so that each chunk could be sorted in memory; how about n=k=sqrt(file-size)?).
• One has a stream of queries coming over a day; how do you keep a cache of the 1000 most frequently used ones? I did not have time for this one.

Fourth Interviewer:

• Asked light technical questions on past items listed in my resume.
• When you do a "read()" call, what is happening under the hood in user space? (The answer needs to clarify how it is translated to a system call by libc).
• How to find a median in a large file of 64-bit integers. I first mentioned the classical "order statistics" algorithm with splitting the initial group into 5-tuples and finding the median of medians, etc. My proposal for the problem was to adapt the median algorithm to the case where we are dealing with a large file. However, no additional disk space could be used; it should be done "in place," and it wasn't clear to me if the order statistics algorithm could be easily done with such a restriction. The interviewer downplayed the order statistics approach and guided me to a solution that I liked: keeping in-memory counters for binary intervals, practically counting occurrences of prefixes (say, 24-bit prefixes). After that, we can tell what prefix range the median belongs to, recalculate the index of the element to search instead of the median, and go over the particular prefix range to find it there. Sweet.

After two weeks, I received a rejection, stating I did not match current open positions.

Given two binary search trees, write a function which tells if two such trees are the same (i.e., same info in the nodes, same branching to left and right at every node).

Given two large files with 64-bit integers, produce a file with integers which are present in both files and estimate the O(?) complexity of your algorithm.

How to find a median in a large file of 64-bit integers.

Input is a 4x4 table with letters. One starts from any of the 16 elements and can move in one step to any of the 8 neighboring cells not visited before (up, down, left, right, up-left, etc., no hyperspace jumps between rows 1 & 4, columns 1 & 4).

Every time a step is made, the letter in that cell is added, so a word is built as we walk. These generated words are looked up in an external dictionary (a function to look up in the dictionary is provided; I did not understand the significance of this dictionary well). The goal of the exercise is to output all words generated by all possible table walks and which are contained in the dictionary.

When you are doing a "read()" call, what is happening under the hood in user space?