Status: 5+ years total Experience
Last Company: Expedia
Location: Bangalore, India
Last Interview Date: 20th July, 2020
Update:
Prepration Strategy
I started with revising all Data structures and attempted questions from LeetCode after I am done with particular data structure.
After this, I practiced top questions from Leetcode and gave around 15-20 mock interviews.
I have solved 200+ questions from Leetcode till my final interview.
Ratio of different level was 40% (Easy), 50% (Medium), 10% (Hard)
Prepration Time
I started my prepration from April Mid (I was also preparing for the other things like Design, improving my Technology skills for other companies) and took around 2 months before screening round
Questions to Attempt
Rather than attempting multiple questions of same approach, I focused on solving 1-2 questions of all different patterns.
This interview experience helped me in my preprating strategy throughout and it has useful links about the Patterns.
https://leetcode.com/discuss/interview-experience/550220/Google-or-SWE-(L4)-or-Bangalore-or-March-2020-Offer
Mock Interviews
- I asked one of my friend who is working in Google to take 1 mock round when I felt prepared for the interviews.
- For rest of the mock interviews, I mainly attempted Online assessment on LeetCode (Google, Facebook, Amazon and Random Company interview set)
Interview Rounds
Screening Round – 26th June, 2020 (45 minutes)
All rounds in Google were 45 minute rounds. Due to Covid situation, all rounds were held on Google meet
Questions – There were 2 questions in this round. I can’t remember the first one but it was an easy level question
2nd was a medium level array question related to Triangular array which can be solved using 2 pointer approach and hashset. This question had multiple follow-ups like there is a single class with single array input and we might have to perform multiple operations on that.
I completed all the scenarios quickly and was able to code the class with all operations. While coding, I realized that my code was getting messy so I deleted that code and rewrote. There was not much time left after the coding so we ended the discussion.
Observation – Interviewer was interactive and he was sharing if solution looks fine to him or he wants me to optimize. While writing code for 1 scenario, I realized that I should validate array so wrote a different valid method and he also asked cross questions like where exactly this validation should happen. I thoroughly enjoyed this interview as I was also able to understand how I am doing.
Round 1 – Technical - 13th July, 2020 (45 Minutes)
He started with a string question where original and edited string is given with some constraints, something similar to https://leetcode.com/problems/rearrange-words-in-a-sentence/ (harder than this), https://leetcode.com/problems/substring-with-concatenation-of-all-words/ (easier than this).
I was able to come up with the solution with Linear complexity after some thinking and took care of all invalid edit scenarios.
I also dry run my code with 1-2 valid scenarios, which helped me find 1-2 small bugs in code and I fixed it myself. After I finished my coding, he was not able to understand the 2nd half of the solution but I was confident about my solution so I quickly explained it to him.
Interviewer asked me check if there is a tactical mistake in the code and I was able to fix that quickly.
Observation – This interviewer was interacting but with no hints of whether he liked the solution or not.
Round 2 – Googleyness & Leadership - 14th July, 2020 (45 minutes)
For preparation of this round, I had discussed some general questions with my friends and wrote all important things like Project details, Achievements, Failures, Weaknesses
In this round, most of the questions were scenario based questions like "some project where I did really well or some time where I had any conflict with someone". I had thought through different scenarios and about my projects done in the past, which helped me remember the details.
Observation – The interviewer was very interactive and I completely enjoyed this round. It looked like having a conversation with a fellow colleague rather than an interview. He was also backing up my answers with some statements which gave me a pretty good feeling about my answers. I felt really confident about this round.
Round 3 – Technical – 14th July, 2020 (45 Minutes)
In this round, interviewer gave me a very hard level string problem related to Suffix Tree (Cannot be solved directly with suffix tree as well).
I quickly gave a brute force solution with complexity and started thinking of an optimized solution. After some time, I was able to come up with O(n^2) complexity solution and asked if I should optimize this further. Interviewer asked me to try to optimize this more. I tried for couple of more minutes but then he asked me to code the solution first. I was able to code and dry run the solution quickly.
After the code, I spent last 15 minutes trying to find different ways to optimize this further. I was able to come up with some solutions which will optimize the complexity in some cases or most of the cases but worst case complexity was not reduced. We concluded the interview as time was over.
Observation – The interviewer was silent almost the whole time and didn’t give me any input/hints during the interview. I was not sure if he was fine with the solution and I kept trying for better solutions till the end. After the round ended, he asked me to check the algo and shared that it was hard to find linear complexity. After this, I felt relaxed as I presented multiple solution in O(n^2) complexity and maybe he was not looking for me to solve it in linear complexity.
Round 4 – Technical – 20th July, 2020 (45 Minutes)
Interviewer started with a matrix problem with some criteria and we had to perform 2 different operations (Not a dp path problem). After some thinking, I was able to solve the scenarios in linear and constant complexity respectively. I was trying to find some approaches to optimize my solution so that I don’t have to go through linear complexity everytime in 1st scenario. I came up with few solutions but I didn’t get any output from the interviewer.
Interviewer asked me to move to coding as there were only 20 minutes left. I started with a class with methods of different scenarios. I initially added comments and empty methods of some basic operations like initialization, invalid cases etc that I will attempt later if time permits. I didn’t get any hints from the interviewer about how input/output should look like. Interviewer asked me to take complete freedom to design my class. After completing basic functionality, I asked my interviewer and I filled all the methods/outputs for invalid cases etc.
After I was done with the code, we concluded the interview
Observation – This interviewer was again a silent one. I had to drive the whole round. Infact, in this round I couldn’t understand whether interviewer wanted me to focus on optimizing the performance of my scenarios, class design or my code. Every time I asked, he told me to go forward as I like.
Round 5 – Technical – 20th July, 2020 (45 minutes)
In this round, interviewer asked me a matrix grid problem. This question had complicated problem statement which took some time to understand and after some thinking and discussion it ultimately transformed to Graph shortest path finding problem. Something like, https://leetcode.com/problems/optimize-water-distribution-in-a-village/
I explained the solution with some test cases and complexity, the interviewer seemed satisfied with the solution and asked me to code the problem.
I was able to code the problem and ran some test cases to check my code. Interviewer seemed satisfied with the code and we ended the discussion.
Observation – I had some issue understanding the problem as it used some difficult words. Interviewer helped me understand the problem with some example and gave a hint when I was going in the wrong direction.
Suggestions –
• In all google meet rounds, you have to write code in google doc which is more difficult than writing on paper as this doesn’t give right indentation and you start feeling the code is getting messy. I recommend to practice writing code on google doc before the interview.
• If in some question, you are not able to draw/write on google doc and want to explain the solution. You can ask them if you can draw on paper and show them on screen, I did that in some of the rounds.
Update:
Approaching the problem
According to my Experience, path to the solution is really important for Google. You might give the perfect algo but still might not have the good feedback. There are couple of suggestions below while solving the given problem
- Make sure you understand the problem right, think of the edge cases and confirm with the interviewer about what output is expected for those cases. In case of any confusion, clarify the understanding of the question and assumption made with interviewer.
- How you are thinking is the most important part. If you don't have the perfect solution in 1st go, that's not a problem. You can start with the basic approach you will go with and then think of optimizing the solution.
- Think out loud, even if you are not sure about your approach, just tell the interviewer that you are thinking out loud. If helps interviewer understand how you are thinking, in case you are going in completely wrong direction, interviewer might help you which will save a lot of time.
- While writing code make sure to cover all edge cases. After writing the code, review/dry run your code with couple of test cases before you say you are done with code (I was able to fix most of the bugs during this phase).
- Don't give up, even if you are not able to reach to any solution, keep trying and thinking till the end of the interview.
**Update:
Data Structures Covered (Will add later if missed something)
For data structures, I just went to another platform and read about all the data structures I could find there -
- Array
- Vector
- List
- Priority Queue (MinHeap, MaxHeap)
- Stack
- Set (Hashset, TreeSet, LinkedHashSet)
- Map (Hash, Tree, LinkedHash)
- Multiset/MultiMap
- Pair
- Tree (Binary tree, n-ary tree, complete tree, segment tree, red black tree, AVL tree, Trie)
Algorithms covered
- Binary Search
- Two Pointer
- BFS/DFS
- All Tree related algorithms (PreOrder, PostOrder, InOrder) and solving Tree questions with recursive and iterative way and all above mentioned Trees implementations
- Graph algorithms (Min spanning tree algorithms, Shortest path algorithms etc)
- Trie, Suffix tree
- String maniputation algorithms
- Union find algorithm (You can try different ways to find a cycle in a graph)
- Dynamic Programming patterns and algorithms
Update:
Team Matching:
It took me around 1.5 weeks for team Matching.
Recuriter told me that my interview feedback is positive and they will go ahead with team matching and then it will go to the Hiring comittee for final response.
I talked to 1st team next day only but didn't find the work matching with my interest so asked the recuriter for some other Team. My recuriter told me that another team is interested in my resume after 3-4 days, I talked to the manager and I found the work quite interesting, so I said yes.