I applied for a Google Software Engineer position online. The recruiter contacted me within a week to set up a phone interview. The phone screen was scheduled within the same week.

The interviewer asked about various data structures and general computer science concepts, focusing on queues and heaps. After that, there were two programming questions:

1. Traverse an array in a spiral order.
2. Check if a directed graph contains a cycle.

Within two weeks, I was contacted to set up an on-site interview. I requested to schedule the interview three weeks later to allow for preparation.

There were four technical interviews on-site, one lunch interview (an informal chat with someone from the Google Glass department), and finally, a PhD dissertation discussion.

Technical Interview 1:

The first question involved the in-order traversal of a Binary Search Tree (BST). I wrote the code. Then, I was asked to check if two different BSTs have the same in-order traversal. I suggested storing the first in-order traversal into a vector and, while traversing the second BST, checking if the element values matched. I also started suggesting using a linked list or a modified recursive approach, but the interviewer advised going with the simpler solution.

Technical Interview 2:

The second interviewer gave me an array with elements that were first strictly increasing, then strictly decreasing. I was asked to find the largest number. I suggested using binary search, achieving O(log N) time complexity with no additional space required. After implementing the code, he asked another question: Given an infinite doubly linked list and a separate list of elements linked to some linked list elements, find out how many neighboring groups are formed from the list of elements. I suggested using a hash table for quick look-up and then traversing the elements to check for neighboring elements, resulting in O(N) time and space complexity. I implemented the code, but ran out of time to test it with different cases.

Technical Interview 3:

The third interview was the strangest. The interviewer had a thick accent, and communication quickly became an issue. He presented a system design question: An Observer class with three methods: AddObserver(), RemoveObserver(), and NotifyAllObservers(). After asking some clarification questions, I suggested using a doubly linked list to keep track of all observers and a hash table to look up individual observers. He then asked me to implement the three methods. After I implemented the code in Java, he stated the program would not work, as the Observer was designed for the Chrome browser. He went into details about user mouse clicks and key releases. I responded that the initial question was vague and asked for more clarification and precise requirements. I suggested changes to address the problem, but time ran out before I could modify the code on the whiteboard.

Technical Interview 4:

After lunch, I returned for the fourth technical interview. The interviewer asked me to add two numbers in base 3, provided as strings. The function should return the sum also as a base 3 string. I suggested converting from base 3 to base 10, adding the numbers, and then converting back to base 3. I know how to add binary streams without conversion, but under time pressure, I chose the easier route. I implemented the conversion from base 3 to base 10. The interviewer indicated satisfaction and asked me to solve another problem: Given a file size, partition the file into chunks so that each chunk size is a power of two, and the number of chunks is minimal. I suggested finding the nearest power of two, calculating the absolute difference between the original file size and this power of two, and then reapplying the process until the remainder is a power of two (1 is 2^0). Due to time pressure, I did not have time for analysis, so I just implemented and submitted the code.

PhD Dissertation Discussion:

My PhD dissertation discussion went alright.

Most interviews went okay, except for the third one, during which I had a hard time communicating. Within a week, the recruiter emailed me, stating the hiring committee decided not to move forward with my application.

I didn't feel any of the questions were difficult. I haven't been stuck at any point, but apparently that wasn't enough.

I also had the chance to look up online the most optimal answers to the questions I was asked.

To be honest, there is very little I would have changed in my responses.