Another Google L3 Post | Not what I expected | India | Offer
- Result
- Offer
- Location
- india
- Experience
- 2 years
- Posted
- 13 Apr 2025
Summary
I successfully cleared the Google L3 interviews in India, receiving an offer despite my current compensation being higher. The interview process spanned several months and included unexpected questions beyond typical DSA problems, such as estimation and design and test rounds.
How it went
My journey through the Google L3 interviews was quite an experience, not entirely what I expected. It took 3-4 months from start to finish, and honestly, by the end, my interest had waned.
Phone Screen [Elimination Round]
My phone screen involved a problem where I had a very large number and an integer k, and I needed to find the largest k-digit number that was a subsequence of the original. I initially proposed a digit DP solution, but while coding, I realized a better monotonic stack approach existed. There might have been some communication issues on my end, so I ended up optimizing the digit DP. However, I eventually explained the monotonic stack idea, and the interviewer agreed it would've been better. Surprisingly, I cleared this round.
Onsite 1
For the first onsite round, I encountered a unique problem: given the shift timings of several waiters, I had to find all non-overlapping intervals during which the set of waiters on duty remained constant. I implemented a basic O(N^2) solution. The interviewer didn't ask for optimizations, and I didn't think of one at the time, although I later solved it in O(N log N). Follow-ups included handling duplicate entries and a full dry run with TC/SC analysis.
Onsite 2
This round challenged me to design, implement, and test a custom tree structure. Given a list of strings, the rule was that if one string was a prefix of another, the shorter string became the parent of the longer one, choosing the longest prefix as the parent if multiple existed. I considered both a map-based solution and a Trie but opted for the map for quicker implementation. The interview was split into three parts: design discussion, coding implementation with interviewer feedback, and finally, writing comprehensive test cases, which was a new experience for me.
Onsite 3
The third onsite round presented a real-life problem: scaling the Android pattern lock to an N*M grid. I had to count the number of different patterns possible under specific rules (at least 2 dots, 4-directional movement, one dot used once, any length). I approached this using backtracking and a visited grid, solving it with relative ease. A recursive dry run was required, which was quite challenging. Follow-up questions included estimating the size of the final answer, modifying the code for 8-directional movement, and finally, a simplified scenario where any dot could connect to any other, which I solved using permutations and combinations.
G&L Round
The G&L round was a standard behavioral interview, but it was intense. I was asked 5-6 questions and felt heavily scrutinized, especially during the last two. I made sure to use the STAR method to structure my answers.
Questions asked (5)
- 01
Find Largest K-Digit Subsequence
Data Structures & Algorithms
You have a very very big number
2123470299109372and a given integerk[let's sayk=6], you need to find largestkdigit number which is asubsequenceof theoriginal number. For example, if the number is2123470299109372andk=6, the answer is999372. - 02
Find Non-Overlapping Intervals of Waiter Shifts
Data Structures & Algorithms
You are given the shift timings of several waiters in a restaurant. Each waiter has a shift start time, and a shift end time. Your task is to find all non-overlapping intervals during which the set of waiters on duty remains the same.
Input:Name Start Time End Time Harry Puttar 10 100 Tony Bhai Stark 60 120 Sherlock Bholmes 30 70 Katniss Devi 150 300
Output:Start Time End Time Waiters on Duty 10 30 Harry Puttar 30 60 Harry Puttar, Sherlock Bholmes 60 70 Harry Puttar, Sherlock Bholmes, Tony Bhai Stark 70 100 Harry Puttar, Tony Bhai Stark 100 120 Tony Bhai Stark 150 300 Katniss Devi - 03
Design and Implement Prefix Tree
Data Structures & Algorithms
Design, Implement and Test a Tree, which is built on the following rules: You are given a list of strings:
["apple", "app", "bat", "batter", "battle", "cat"]. The root of the tree is an empty string. For any string in the list, if there exists another string that is a prefix of it, then the shorter string becomes the parent node of the longer string. If there are multiple possible parents, choose the longest prefix as the parent. For example,"app"is a prefix of"apple", so"app"becomes the parent of"apple". Your task is to build and represent this tree structure."" / |
app bat cat / /
apple batter battle - 04
Android Pattern Lock Paths
Data Structures & Algorithms
This was a real-life question: if the Android pattern lock was scaled to have
N*Mdots (Nrows andMcolumns), how many different patterns could be created? The rules were: at least 2 dots must be connected, dots can be connected in 4 directions (left, right, top, bottom), one dot can be used only once, and the pattern can be of any length. - 05
Behavioral Questions (G&L Round)
Behavioral
5-6 behavioral questions were asked. I was thoroughly challenged, especially with the last two questions. The STAR method was essential for effectively answering these questions.
How they prepared
I used to be an Expert in Codeforces and a Guardian in LeetCode. Although the interview process also included Pnc, answer estimation, and design and test questions, my primary preparation involved competitive programming.