Google | SE (L4) | Bangalore | August 2020 [Offer!!!]
Summary
I interviewed for a Software Engineer L4 position at Google in Bangalore and successfully received an offer after multiple technical and behavioral rounds, spanning coding, system design, and leadership principles.
Full Experience
My interview journey for a Software Engineer L4 position at Google in Bangalore began in April Mid with preparation, leading to the actual interviews from late June to late July 2020. All rounds were 45 minutes and conducted on Google Meet due to the Covid situation.
Screening Round – June 26, 2020 (45 minutes)
This round consisted of two questions. I don't recall the first one, but it was an easy problem. The second was a medium-level array question related to a triangular array, solvable using a two-pointer approach and a hashset. It had multiple follow-ups, requiring operations on a single array input within a class. I quickly coded all scenarios, but realized my initial code was messy and rewrote it for clarity. The interviewer was interactive, offering feedback and asking probing questions about my validation approach, which I thoroughly enjoyed.
Round 1 – Technical – July 13, 2020 (45 Minutes)
The interviewer presented a string manipulation problem where an original and an edited string were given under certain constraints. It was harder than Rearrange Words in a Sentence but easier than Substring with Concatenation of All Words. After some thought, I developed a solution with linear complexity and handled all invalid edit scenarios. I dry-ran my code, catching and fixing a couple of small bugs. Although the interviewer initially struggled to understand the second half of my solution, I confidently explained it, and he later asked me to check for a tactical mistake, which I quickly resolved. This interviewer was interactive but didn't give hints about his satisfaction with my solution.
Round 2 – Googleyness & Leadership – July 14, 2020 (45 minutes)
For this round, I had prepared by discussing general questions with friends and noting down key details about my projects, achievements, failures, and weaknesses. Most questions were scenario-based, such as "a project where I excelled" or "a time I had a conflict." My preparation helped me recall details and structure my answers effectively. This was a very interactive and enjoyable round, feeling more like a conversation with a colleague. The interviewer's positive reinforcement made me feel very confident about my performance.
Round 3 – Technical – July 14, 2020 (45 Minutes)
I was given a very hard string problem related to Suffix Trees, though it couldn't be directly solved using a suffix tree. I quickly provided a brute-force solution and its complexity before attempting an optimized one. I managed to come up with an O(n^2) solution and asked if further optimization was needed. The interviewer encouraged me to try more, so I spent a few more minutes before he asked me to code the O(n^2) solution, which I did efficiently and dry-ran. For the last 15 minutes, I continued to explore ways to optimize, finding some solutions that improved complexity in certain cases but not the worst-case. The interviewer was largely silent throughout, providing no hints. At the end, he confirmed it was hard to find a linear complexity solution, which relieved me, knowing my O(n^2) approaches were sufficient.
Round 4 – Technical – July 20, 2020 (45 Minutes)
This round started with a matrix problem requiring two different operations, not a DP path problem. After some thought, I devised solutions for the scenarios with linear and constant complexity respectively. I explored optimization approaches to avoid linear complexity for the first scenario but received no feedback from the interviewer. With only 20 minutes left, I moved to coding, designing a class with methods for different scenarios. I took the freedom to design the class as I saw fit, adding comments and basic operations like initialization and invalid case handling. After completing the core functionality, I confirmed with the interviewer and filled in the invalid case handling. This interviewer was also very silent, and I had to drive the entire round without much guidance on whether to focus on optimization, class design, or code clarity.
Round 5 – Technical – July 20, 2020 (45 minutes)
I faced another matrix grid problem with a complicated statement that took some time to fully grasp. After discussion, it became clear it was a graph shortest path finding problem, similar to Optimize Water Distribution in a Village. I explained my solution with test cases and complexity, and the interviewer seemed satisfied, asking me to code it. I successfully coded the problem, ran test cases, and the interviewer was pleased with the result. This interviewer was helpful in clarifying the problem statement with examples and offering hints when I strayed off course.
Interview Questions (4)
Given a triangular array, perform multiple operations. The problem can be solved using a two-pointer approach and a hashset. It included follow-ups and required implementing a class to handle operations on a single array input.
Given an original string and an edited string with some constraints, determine the process or transformation. The problem is harder than 'Rearrange Words in a Sentence' but easier than 'Substring with Concatenation of All Words'.
A very hard string problem, related to Suffix Trees, though it cannot be directly solved using a suffix tree. I started with a brute-force solution, then optimized it to O(n^2) complexity. The interviewer asked for further optimization, but a linear complexity solution was noted as very difficult to find.
A complex matrix grid problem that, after discussion, transformed into a graph shortest path finding problem. Similar in concept to Optimize Water Distribution in a Village.
Preparation Tips
Preparation Strategy
I began my preparation in mid-April, dedicating about two months before my screening round. My strategy involved:
- Revising all data structures.
- Attempting LeetCode questions after completing each data structure.
- Practicing top questions from LeetCode.
- Giving around 15-20 mock interviews.
By the final interview, I had solved over 200 LeetCode questions, with a ratio of 40% Easy, 50% Medium, and 10% Hard. Instead of solving many questions of the same pattern, I focused on 1-2 questions for each different pattern. I found useful links about patterns on LeetCode Discuss.
Mock Interviews
- I asked a friend working at Google to conduct one mock round when I felt prepared.
- For the remaining mocks, I primarily used LeetCode's online assessments for Google, Facebook, Amazon, and random company interview sets.
Suggestions for Approaching Problems (Google Meet Specific & General)
For Google Meet Rounds:
- Practice writing code in Google Docs; it's more challenging than paper due to indentation issues.
- If you need to draw or visualize, ask if you can use paper and show it on screen. I did this in some of the rounds.
General Problem-Solving Approach for Google:
The path to the solution is crucial. A perfect algorithm might not suffice without a good thought process.
- Understand the Problem: Clarify edge cases and expected outputs with the interviewer.
- Think Out Loud: Share your thought process, even if unsure. This helps the interviewer guide you if you're off track.
- Start Simple, then Optimize: Begin with a basic approach and then iteratively think about optimizations.
- Code with Edge Cases: Ensure your code covers all edge cases.
- Review/Dry Run: Always review and dry-run your code with test cases before declaring it complete; this helped me find most bugs.
- Don't Give Up: Keep trying and thinking until the very end, even if you don't reach a perfect solution.
Data Structures Covered
I covered a wide range of data structures:
- Array, Vector, List
- Priority Queue (MinHeap, MaxHeap)
- Stack
- Set (Hashset, TreeSet, LinkedHashSet), Multiset/MultiMap
- Map (Hash, Tree, LinkedHash)
- Pair
- Tree (Binary tree, n-ary tree, complete tree, segment tree, red-black tree, AVL tree, Trie)
Algorithms Covered
Key algorithms included:
- Binary Search
- Two Pointer
- BFS/DFS
- All Tree-related algorithms (PreOrder, PostOrder, InOrder, recursive/iterative solutions) and implementations of the mentioned tree types.
- Graph algorithms (Min spanning tree, Shortest path, etc.)
- Trie, Suffix tree
- String manipulation algorithms
- Union Find (with different ways to find cycles in a graph)
- Dynamic Programming patterns and algorithms