Google Onsite Interview (January 2019)

Status: Industry Hire, MS CS (University Of Waterloo), 4 years of experience
Position: Software Engineer L4 at Google
Location: Kitchener, Ontario, Canada
Onsite: First Week of January
The interview process and format of each interview

Technical phone screen (1 hour):
- Algorithmic DP question and some Operating Systems Questions. (LC complexity: Easy/Medium)
Onsite (45 minutes long 5 rounds):
- First round asked 3 questions, one easy and 2 medium. They were not exactly from LeetCode but
you can find many similar question on Leetcode. I gave optimal solutions for all questions and wrote
code for one easy and one medium problem. He didn’t ask me to code last problem. All questions were
related to each other and they involved hashing and sorting.
- Second round asked me a Math question. I gave brute force, sub-optimized and finally optimized solution.
Then I wrote the code and tested it. I guess it was b/w medium and hard and can be solved using
hash sets. In last 10 minutes, He asked me a very hard computational geometry question and asked me
just to tell solution. I gave him a vague idea that we can solve it in O(N) but still some dots were missing
in my solution. He said solve it at your home.
- Third Round asked me 2 tree questions. I was able to give optimized solution for both of them and wrote
code for them. One involved simple Tree Traversal and other involved Dijkstra.
- Fourth Round was a Trie question. I was able to give optimized and sub-optimized solution and discussed
trade-off of both solutions based on input structure. He asked me to code sub-optimal solution which I did.
- Fifth Round was also a Trie questions and input size was 80GB. I gave him a memory inefficient and time
efficient solution. He said improve memory inefficiency without changing time complexity which I did and
finally I coded the solution.
No question was from LeetCode. They were not only concerned about Big O complexity but also code level improvements which don’t change Big O complexities at all. Overall questions were not that hard at all. Except third interview, I solved all questions without any hint. In third interview, I gave a solution and I thought it was incorrect but after some time interviewer told me your first solution was correct why you thought it’s incorrect. I solved nearly 400 LC questions and out of them 140 were LC hards. I solved the questions topic wise i.e. first mastered DP then Trees, Graphs and so on.

After onsite, I cleared Hiring Committee after 1.5 weeks. In the next week, I was matched with a team and finally got offer in third week.