Google L4 | Interview Experience | India | Fullstack

My Google L4 Fullstack interview experience in India involved four rounds. The first three were focused on Data Structures and Algorithms, and the final round was Googlyness. The HR mentioned that Google has shifted to 3 DSA interviews instead of 4, with a perceived increase in question complexity.

Round 1: DSA Round - Hire (Very Positive)

This round involved a problem about inferring player ranks from match results. Given n players with distinct ranks and m match results (a defeated b), the task was to identify which players' ranks could be precisely determined. A player's rank is precise if the sum of stronger and weaker players (stronger_count[i] + weaker_count[i]) equals n - 1. My solution used a graph traversal approach: I treated players as nodes and drew directed edges from winner to loser. For each player, I counted stronger players by traversing the reverse graph and weaker players by traversing the original graph. I provided a dry run with an example (n=5, various matches) to demonstrate how player 2's rank could be precisely determined.

Round 2: DSA Round - Hire (Positive)

The second DSA round presented a problem about generating the Nth license plate from a global sequence. License plates are 5 characters long and are issued in 6 consecutive ranges, varying from 0 letters + 5 digits to 5 letters + 0 digits. The function string getNthPlate(long long n) was required. I solved this by first using a brute-force approach and then optimizing it. My optimized solution involved storing the range counts in a vector and then iterating through these ranges to find where n falls. I then determined the number of digits and letters for that specific range based on the remaining n value. I gave a proper dry run, explaining how n is decremented as ranges are consumed until it's zero, at which point an encode function converts the indices into the final string.

Round 3: DSA Round - No Hire

This was the round that led to my rejection. The problem involved querying the latest application version that supports a given OS version. Each app had a name, minOS, maxOS, and a releaseOrder. For example, given apps like 'v1' (min=14, max=+∞, order=1) and 'v3' (min=12, max=16, order=3), an OS query of '14' should return 'v3'. My brute-force approach involved scanning all apps for each query and tracking the one with the highest release order that supported the OS. I optimized it slightly by sorting apps by release order and checking from the latest. The interviewers asked me to code this, and I couldn't think of a more optimal solution involving advanced data structures at the time. I later realized a sweep line algorithm with disjoint segments would be more efficient, involving converting app ranges into events and maintaining a max-heap of active apps. This would allow for O(log K) query resolution, though I was unsure if a segment tree would be an exact fit or overkill.

Round 4: Googlyness Round - Hire (Positive)

This round was entirely behavioral and lasted about 40 minutes. I received positive feedback for this round.

Final Verdict: Rejected, primarily due to my performance in Round 3.