Another Google L3 Post | Not what I expected | India | Offer

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.