Google L3 Interview Experience
Summary
I interviewed for an L3 position at Google Bangalore, going through several technical rounds covering data structures, algorithms, and system design, along with behavioral questions. The process concluded with a team matching round, which took some time.
Full Experience
My Google L3 Interview Experience
I applied for the L3 position at Google Bangalore through a referral.
TPS Round
The first round focused on a problem involving family members' birthdays. I was asked to devise a data structure or function that could output the name of the member whose birthday is next from a given date, with the sequence being circular. I proposed a simple sorted array based on birthdays. The interviewer was very interested in exploring various modifications to the question and discussing all possible solutions.
Round 1 (Technical)
The first proper technical round started with a graph problem. I was given a graph of cities and travel times between them, and a source city A along with a list of favorite cities. The goal was to find the smallest time taken to reach any of the favorite cities from city A. I solved this using a simple Dijkstra's algorithm.
The follow-up to this question was more complex: in the same network, given city S and city T, and a list of favorite cities, I had to find the shortest path from S to T that must go through at least one of the favorite cities. I presented two approaches: one using Floyd Warshall and another using Dijkstra's algorithm twice (once from S and once from T) and then looping over the favorite cities to find the shortest combined distance.
Round 2 (Technical)
This round involved movies and their ratings within a network where movies with the same genre were connected. I needed to return a list of K most highly rated movies related to a given movie A. My solution involved building a graph from the movie relations and then performing a BFS from movie A while maintaining a Min Heap of size K to keep track of the top-rated movies.
As a follow-up, the interviewer asked me to explain the Quick Select method as an alternative to using a heap for this problem.
Round 3 (Technical)
This round presented a problem with pairs of strings, where each pair had exactly one character mismatch. This mismatch represented a parent-child relationship, forming character chains (e.g., 'abc','abe' -> c->e; 'abe','abf' -> c->e->f). Given a list of these pairs, I had to find the length of the longest such chain, with the constraint that each character would have only one parent and one child.
The follow-up modified the problem: from the pairs of strings, we could now form a Polytree (a tree with multiple children and multiple parents). The task was to find the length of the longest chain in this Polytree. I approached this using dynamic programming to find the longest chain for each child.
Round 4 (Googlyness)
This round consisted of generic behavioral questions, focusing on Google's 'Googlyness' principles.
Team Matching
After the interview rounds, it took about 2-3 months to get to the team matching round. This stage also involved generic behavioral questions to assess fit within potential teams.
Interview Questions (9)
Given a tree of family members and their Date of birth. We have to come up with data structure or fuction which should output the name of member whose birthday is next from given date, the sequence should be circular.
Given graph of cities and time taken to travel between them. You have given source city A and list of favourite cities. Output the smallest time taken to reach any of the favourite cities from city A.
Now in the same network of cities, you have given city S and city T and list of favourite cities. We have to give the shortest path from city S to city T which must go through atleast one of the favourite city.
You have given movies and movies network ( movies which have same genere) and rating for each of these movies. You have to reture list of K most highly rated movies which are related to movie A.
Just explain the quick select method for solving this instead of using the heap.
We have given list of pair of strings. Each pair of string has exatly 1 character mismatch in them. we can assume that the character which are mismatched have parent -> child relation and can from chain of multiple characters.
Eg. ('abc','abe') -> Parent ->child :: c->e
Eg. ('abe','abf') -> Parent ->child :: c->e->f
Form list of these pairs we would get chains of characters. We have to find the lenght of the longest such chain. It is given that the 1 chracter would have only 1 parent and 1 child.
Now from the pairs of strings we can form the Polytree ( tree with multiple child , multiple parents). We have to find length of longest chain.
Generic behaviourial questions.
Generic behaviourial questions.