Google Software Engineer Interview Experience — Three Technical Rounds and Googleyness

First round: Technical interview

Question: Add and search for words in a Trie.

Because I had limited preparation time, I mainly reviewed common topics such as graph theory and dynamic programming, but I did not cover Tries. The problem was roughly about adding and searching for words. A Trie supports fast word lookup because of its tree structure, and the return behavior needed attention.

I told the interviewer directly that I knew this was a Trie problem but had not practiced Tries. The interviewer understood and still wanted me to continue. I then proposed using a hash table. The interviewer seemed quite satisfied with that, but still guided me toward implementing it with a Trie. I did not solve it in the end, though the interviewer seemed to understand my situation.

Second round: Technical interview

Question: There is a class with two methods. One is addNonOverlappingInterval(), and the other checks whether a number falls within an interval.

The interviewer asked me to discuss O(N), O(log N), and O(1) approaches for checkIntervalInRange(). I proposed a linear-time solution and suggested using binary search for O(log N). I could not think of an O(1) method right away, so I proposed creating a hash table containing every number in all the intervals and then querying it.

The interviewer asked me to express the time complexity in terms of the number of bits, and I messed that up. At the end, the interviewer told me my overall performance was good and that, with more time, I probably would have derived the correct complexity.

Third round: Technical interview

Question: Given a file made entirely of IP headers, find the ten IP addresses that occur most frequently.

My approach used a priority queue. The follow-up asked how to handle tied frequencies by returning nested pairs, where each pair contains a frequency and a list of all IP addresses with that frequency. I used an approach similar to bucket sort.

The final follow-up was open-ended: what would I do if memory were not large enough to read the entire file?

Fourth round: Googleyness

I was asked:

• Tell me about how you work with difficult people.
• Do you prefer working in small or large teams?
• Define your ideal work environment and manager.