Status: 7.5 years total experience - 5.5 years exp after PG (M.Tech in CS) from IIT Delhi + 2 years between UG and PG
Position: Software Developer at in-house startup for last 1.5 years. (Senior Software Engineer at a Hyderabad based company prior to that).
Location: Bangalore, India
Last Interview Date: March 2, 2020
Telephonic Interview - January 21, 2020
It was a 45 minute round on Google Hangouts and Google Docs. It had 2 questions:
Observation - The interviewer did not give me any inputs (other than answers to the initial clarifying questions) and maintained a poker face throughout. I could never tell if he was satisfied with my approach or whether he wanted me to think of alternative aproaches. I felt like I was the one who had to drive the round.
The next day my recruiter informed me that I had done positively in the hangout interview, and connected me to a recruiter in Bangalore to proceed with the next rounds.
The onsite rounds were divided into two days - the first day I was supposed to have two coding and one behavorial round, and if I did well, they would call me for the final two rounds.
Onsite Round 1 - Technical - February 18, 2020
I had reached on time but because of some logistics issue on their end, it got 10 minutes late by the time I was taken to the interview room allocated for my interviews for the day, and got introduced to my interviewer.
There was a whiteboard to discuss the problem and solution but I was also provided a chromebook and was expected to code my solution on that.
The interviewer started with a scenario with a mobile app and a library required for its functioning. The problem translated to a sort of class design problem, in which I had to come up with how to receive and preprocess initial bulk data and then how to process subsequent queries using the preprocessed data. Majority of the time was spent in discussing and identifying different ways to represent and preprocess the data, I eventually ended up with a treemap data structure to efficiently query range related information.
There wasn't much time left for coding, and I coded only main parts of the class. The interviewer asked me to review and identify problems with my code. I suggested a couple of improvements that could be done. We were out of time, so we ended the discussion.
Observation: Again, it was very hard to tell if the interviewer was satisfied with my approach. In fact, I kept feeling that probably, he was looking for something else. Also, because we ran out of time and we barely completed just one question, I didn't feel confident about my performance in this round.
Lunch Interview - February 18, 2020
The first round was followed by lunch. I was accompanied by a Googler for an hour long lunch which involved casual discussion. I could barely bring myself to eat that day. I asked him about team sizes, different teams, how easy/difficult it was to change teams in Google, etc. I also asked him how adversely it would affect my chances if I didn't do well in one of my interviews. He reassured me that it is always hard to tell whether you did well or not in an interview, and also that each round is evaluated independently and that the average of all interviews are taken into consideration, so I need not worry. He also mentioned that when time is less, the expectation is also adjusted accordingly. That helped with my confidence a little.
Onsite Round 2 - Technical - February 18, 2020
Lunch was followed by another coding round, where I came back to my interview room. Although an onsite round, this interview happened over video conference. I couldn't use the whiteboard anymore but had to code up the solution on the same chromebook allocated for my interview.
The interviewer told me that it would be a 3 part problem - the first part was a typical 2D matrix DP problem, where you have to calculate total number of ways to reach the bottom right cell of a matrix from the top left cell with a constraint that some cells of the matrix have obstacles and you can only move right or down at each step. See https://leetcode.com/problems/unique-paths-ii/
Being familiar with the problem, I quickly explained how I would approach the problem and explained the steps. I started to feel relaxed and confident by this time.
He then proceeded with two follow-ups on this question, by adding more and more constraints to the problem. Those required a little more of thinking, and I was able to derive them. The interviewer asked me to code the last variant of the problem, and I was able to do it quickly. He pointed out a minor bug which I quickly corrected.
After that there was some time left, so he asked me another problem to discuss how I would approach that. I told him about a backtracking approach where I would consider all possibilities at each node, etc. Then, we were out of time, but I felt pretty positive about this round.
Observation - This interviewer was very interactive and I thoroughly enjoyed this interview session. It felt more like a discussion with a fellow colleague. The interviewer also gave me couple of hints in the follow-up questions when he felt that I was close to getting the solution but needed a nudge. I was able to pick up those hints well and got to the answer fast.
Onsite Round 3 - Googleyness & Leadership - February 18, 2020
This was the last round for the day. This was a behavioral round. I had discussed some typical behavioral questions with my friends, and had also written down some instances about some typical situations like my accomplishments, my failures, my initiatives etc. from my previous work experience. That helped me with some of the answers during the interview. There was also a hypothetical scenario based question, to which I didn't think I answered very well, something like - what would you do if you colleague hogs all your credit? Overall, I answered as honestly as I could, and felt that my answers should have been more or less satisfactory.
This was the end of my first set of onsite rounds with Google. The very same night, my recruiter contacted me and said that my feedbacks were positive in all the rounds, and that they wanted to proceed with the remaining two rounds quickly. My recruiter explained that at Google, for L4, the System Design round was optional, so I had an option to choose another algo and coding round. He said that the remaining two rounds would be of a higher difficulty level. I got the interview scheduled on March 2, and brushed up on harder problems on leetcode in the mean time.
Onsite Round 4 - Technical - March 2, 2020
This interview was scheduled in the other Google office in Bangalore. There was some logistics issue - the security desk at the front gate was not informed about my interview, and they were not letting me in. Fortunately, my recruiter was online and I was able to contact him immediately and got it sorted.
Again, there was both a whiteboard available to discuss the problems, and a chromebook to code the solutions.
The interviewer told me that he intended to get one question completed, and if time permitted we would discuss another problem.
He started with a medium level DP question. It was similar to https://leetcode.com/problems/knight-dialer/, with some differences, but similar difficulty level. I started formulating an initial recursive solution. He asked me what the run time would be, which I explained. I then explained how I would optimize it to avoid repetitive calculations and bring the time complexity down from exponential to linear time, He asked me if there was any further scope to improve on complexity, where I explained that we could not improve on run time but could bring down space complexity from linear to constant, since at each hop the result depends only on the last level of prev hops. He was satisfied with the solution and asked me to code it, which I did. He pointed out a minor bug in my code, which I was able to identify immediately and fixed.
There was plenty of time left for the second question. He asked me a hard level problem this time, related to medians of subarrays. This was more for discussion purpose and he didn't expect me to code it. I asked clarifying questions, came up with a brute force approach, explained the complexity, and then came up with an intuition for an improved approach. I couldn't derive the complete solution as we ran out of time but the interviewer seemed satisfied.
Observation: I felt very good about this round and felt I did well. The interviewer seemed happy with my solutions.
At this point, I was relaxed. I had heard from different people that if you do well in 4 rounds, one round will not make much difference unless it had some serious red flags. So, there was some breathing room for the last remaining round even if I didn't nail that.
Onsite Round 5 - Technical - March 2, 2020
In this round, the interviewer asked me a hard problem related to optimizing travelling some distance with gas stations in between with a few constraints. I started to think of starting with all possibilities with backtracking initially, but gave up that idea midway. After thinking through for some time, I came up with a greedy approach. This solution required some stack related subproblems which were themselves equivalent to medium level problems on LC. The interviewer asked me to code it. I took some time to code this, found myself getting confused with the flow while writing the code, and ended up doing a lot of rework. After completing, when I did a dry run on an example given by the interviewer, I found 2 major issues with the code. I was able to fix one of them immediately, but the second was a case that I had not considered in my solution, and it would require a little more time to think. But, we had run out of time and had to end the interview.
Observation: This interviewer was again a silent one. After he gave me the problem, he didn't participate in any discussion other than answering clarifying questions. In all my rounds, I struggled the most in this round. I missed out on considering one of the cases. The positive thing was that I was able to come up with optimal solution for the parts which I had identified. I think the interviewer wanted me to be able to point out the issues in the code, which I was able to do. I would have been able to complete the problem but there was no more time left.
This was the end of all my interview rounds with Google. Later, I got an update from my recruiter that I had done well in all rounds, except the last one where my problem solving was strong but coding was messy. After a few weeks, I was informed that my packet was cleared from the hiring committee. I had team matching interviews, and finally got my official offer letter from Google today.
I hope this detailed writeup would be helpful to the Leetcode community. I wouldn't be able to give out the exact questions as they were confidential. I have tried to give out as much as possible.
Update: My prep strategy:
I had only applied to Google, so I prepared only targetting Google in mind. The thought process was that I would first try to complete the process with Google. If I don't clear it this time, I would apply to other companies.
I started my preparation around October end. Before starting with Leetcode, I took an Algorithms course on Coursera, and tried to do some relevant chapters of the Cracking the Coding Interview book.
But, the most effective preparation happened through Leetcode. I started Leetcode in December. I gave myself 1.5 months before I would take my telephonic. I started with easy-medium 5-10 problems from each of the 10 topics that are asked in Google. Then I took a premium subscription and tried to do the Google Interview Preparation card. It had rather harder level questions, so I won't recommend starting with that. I practiced problems from some Leetcode Explore Learn cards like Binary Search, Recursion I, Recursion II, Binary Tree, Array and String. Those would be a good starting point while starting with Leetcode.
Then, I came across a very useful link on Leetcode Discuss, which had grouped together a bunch of questions by common patterns: https://leetcode.com/discuss/interview-question/448285/List-of-questions-sorted-by-common-patterns. I practiced those. I tried to solve as many problems as I could from that list. And I practiced a few mock interview timed questions on Leetcode.
I made a habit of marking as favorite any problem that I found particularly interesting or tricky, so I could revisit them.
For DP, I found this link to be useful: https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns - I solved may be easier half of problems from this list. I would still struggle with harder DP problems.
Another useful link I used was: https://medium.com/leetcode-patterns - This esp helped me with backtracking, and sliding window patterns.
Regarding number of LC problems solved:
I think I solved ~ 170 problems by the time I had my telephonic round, which involved 30 hard, 40 easy, and ~ 100 medium problems. By the time all my rounds were over, my count was around 320 - 90 easy, 170 medium, 60 hard. These are approx numbers.
Update - Team Matching
In the team matching interviews, the managers who are looking for candidates in their project would shortlist selected candidates based on their resume, and then have a call with them explaining their project/team size, goals etc.
I have heard that these days, Google recruiters are usually assigned for dedicated teams. Not sure how true this is. So anyway in my case, after all the interview process was over, in parallel while my packet was being reviewed by the hiring committee, my recruiter told me that one of the managers was interested in my resume, and wanted to connect with me. This team matching call happened right after the time the HC decision was made. However, this particular project required me to work on front-end for a while, but I was more interested in a backend role, so I requested my recruiter to connect me with another team that might have an opening. He checked and then connected me with another manager, which felt better suited for me so I said yes.
Update - Topics covered
Since many people are asking what 10 topics I was talking about in the prep, here's the list shared by my recruiter.
Preparation checklist (not exhaustive) :
1. Binary search
2. BFS/DFS/Flood fill
3. Tree traversals
4. Hash tables
5. Linked list, stacks, queues, two pointers/sliding window
6. Binary heaps
7. Dynamic programming
8. Union find
9. Ad hoc/string manipulations
10. Arrays
11. Other good to know topics: Trie, segment trees/fenwick trees, bitmasksUpdate - Regarding Compensation
From this experience, I realized that the compensation you're offered at Google (Bangalore) will depend largely on your previous salary, and if you have any competing offers. Since I was working at an in-house startup previously, I was not on a payroll for approx. two years. So I had to share my payslip from the company prior to that with my recruiter. The compensation was calculated based on that. Also, I didn't have any competing offers since I had only applied to Google. So, there was not much room for negotiation in my case.
Hope this helps!