Google Onsite Round L4 Experience | India
Summary
I successfully received an L4 Software Engineer offer from Google India after a series of interview rounds, including a phone screen, three technical onsites, and a behavioral round.
Full Experience
It was great to finally receive an offer from Google! This community has been incredibly helpful, so I wanted to share my experience. My journey started with a phone screen back in January 2022. After that, I had a gap and then went through my onsite rounds in July and August.
Phone Screen: I don't remember the exact problem, but it was similar to finding if all airports are connected by paths and adding minimum paths if not. I initially used connected components, and for a follow-up about adding airports and paths, I used Prim's algorithm with a dummy node. I received feedback that my solution was optimal but missed one edge case (which I corrected during the call) and could have used better data structures. I was asked to re-interview in a few months, skipping the phone screen.
Onsite Round 1: This round focused on finding the Kth largest element in an infinite stream. For a constant K, I used a min-heap. The follow-up involved a variable K, for which I proposed a binary search on prefix sums followed by a segment tree approach. The interviewer seemed satisfied.
Onsite Round 2: I was asked to find the sum of all subarrays that are arithmetic progressions. My initial solution was O(N) time and O(N) space, which I then optimized to O(1) space after being prompted. The interviewer was satisfied with the optimality. Feedback suggested my solution was optimal, with minor callouts about communication and average problem-solving speed.
Onsite Round 3: This question involved finding the shortest path in an n*m grid with 0s (free) and 1s (obstacles), starting from the top-left to the bottom-right, allowing 8-directional movement and removing at most K obstacles. I used BFS + DP. The follow-up introduced removing obstacles in '+' or 'X' forms with associated costs, which I handled with BFS + DP with slight tweaks in transitions.
Onsite Round 4: This was a behavioral round where I discussed my experience and leadership qualities.
After all rounds, the recruiter confirmed good feedback, but getting a Headcount slot was challenging, so I was placed in a wait queue. Eventually, I received the offer!
Interview Questions (7)
Given a set of airports and existing paths between them, determine if all airports are reachable from each other. If not, find the minimum number of additional paths needed to connect all airports such that they become fully connected. A follow-up involved handling the dynamic addition of airports and paths.
Design a data structure or algorithm to efficiently find the Kth largest element from an infinite stream of integers, where K is a constant value.
Extend the previous problem: design a data structure or algorithm to efficiently find the Kth largest element from an infinite stream of integers, where K is now a variable that can change with each new integer arriving in the stream.
Given an integer array, find the sum of all subarrays that are arithmetic progressions. An arithmetic progression is a sequence of numbers such that the difference between consecutive terms is constant.
Example:
Input: [7, 4, 5, 6, 5]
Output: 86
Explanation:
Arithmetic subarrays are:[7], [4], [5], [6], [5][4, 5], [5, 6], [6, 5][4, 5, 6]
Sum of all is 86
Given an n*m grid where each cell is either 0 (free path) or 1 (obstacle). Starting from the top-left cell, find the shortest path to the bottom-right cell. You can move in any of 8 directions (horizontally, vertically, or diagonally). You are allowed to remove at most K obstacles along your path.
Extend the previous problem: You can now remove obstacles in specific patterns ('+' form or 'X' form), with an associated cost for each removal. Find the shortest path from top-left to bottom-right.
This round focused on standard behavioral questions, probing into my past experiences and evaluating my leadership qualities.
Preparation Tips
I had a background in competitive programming from college and solved around 140 LeetCode questions: 90 Medium, 40 Hard, and the rest Easy. I continued practicing between my phone screen and onsite rounds.