Google | L4 | Interview Experience
Summary
I interviewed for an L4 position at Google in Bengaluru, successfully navigating a phone screen, three challenging onsite technical rounds, and a behavioral conversation, which ultimately led to an offer.
Full Experience
I got a call from a recruiter in Nov 24 for an L4 position in Bengaluru. Took some time to prepare and started interviewing in January.
Phone Screen: Same questions as this. Was able to explain my solution (multi source BFS), estimate TC and SC, then write code. Did the same for the follow up.
Onsite 1: Given a file_path to chat logs, and a number K, return the K most talkative users (word count) from the logs. An example of the logs can be found here.
Asked a lot of questions to understand edge cases, collision handling, etc., coz it seemed too simple. Found out i had to write the parser logic for the file. Also found out that in case of tie for the last position on top k list, we had to include all tied users in the result. Explained a heap solution, and wrote code for it. Was asked to write up different test scenarios for this problem.
Onsite 2: You are given a network of teleporters(nodes) (N - number of teleporters, edges - connections b/n teleporters). Some of them are broken. A broken teleporter/node cannot take you to another teleporter/node.
Q1: Get the shortest path from A to B avoiding broken teleporters (expected output is list of nodes in travel sequence). If no path exists, return an empty list. I used BFS for this.
Q2: Suppose the the broken teleporters are partially fixed. Travelling from a working teleporter is instantaneous. But teleporting from a fixed/partially working teleporter takes 1 day's time. Get the shortest path from A to B while minimizing use of partially fixed teleporters.
My first instinct was to use BFS with priority queue (Djikstra's). But interviewer mentioned there is a better approach. I realized the answer was a 0-1 BFS, and implelmented that.
Onsite 3: Beautiful Path: You're given a footpath of n blocks, each painted with one of k colors. Guests walk along the path, and each has a favorite color c. The beauty of the path for a guest is the length of the longest contiguous footpath segment painted in their favorite color.
Q1: Find the longest continuous streak of color c.
Used a simple iteration to solve this.
Q2: Suppose we have many guests now, each with their own fav color. For each guest, return the max beauty based on their favorite color.
Used one map to track the maxBeauty for each guest. As we iterate over the blockColors, we keep track of curColor and curStreak for curColor. If the color is not curColor, we reset curColor and curStreak. If the color is curColor, we update curStreak. At each step, we check and store maxStreak for curColor.
Q3: Let's go back to having 1 guest. Suppose you could repaint m blocks to any color. Find the max beauty value if we could repainit m blocks.
Used a sliding window approach, with the window limited by having not more than m non fav color blocks.
Follow ups were likely to continue until we ran out of time.
Behavioural Round: It was more of a conversation, so I don't remember the exact questions. But the conversations was fun and interactive.
Verdict: Cleared all DSA rounds. My recruiter didnt share ratings for any interviews.
Offer: https://leetcode.com/discuss/post/6749999/google-l4-bengaluru-by-anonymous_user-deyh/
This was my 3rd interview with Google.
Interview Questions (6)
Given a file_path to chat logs, and a number K, return the K most talkative users (word count) from the logs. An example of the logs can be found here. Asked a lot of questions to understand edge cases, collision handling, etc., coz it seemed too simple. Found out i had to write the parser logic for the file. Also found out that in case of tie for the last position on top k list, we had to include all tied users in the result.
You are given a network of teleporters(nodes) (N - number of teleporters, edges - connections b/n teleporters). Some of them are broken. A broken teleporter/node cannot take you to another teleporter/node. Get the shortest path from A to B avoiding broken teleporters (expected output is list of nodes in travel sequence). If no path exists, return an empty list.
Suppose the the broken teleporters are partially fixed. Travelling from a working teleporter is instantaneous. But teleporting from a fixed/partially working teleporter takes 1 day's time. Get the shortest path from A to B while minimizing use of partially fixed teleporters.
You're given a footpath of n blocks, each painted with one of k colors. Guests walk along the path, and each has a favorite color c. The beauty of the path for a guest is the length of the longest contiguous footpath segment painted in their favorite color. Find the longest continuous streak of color c.
Suppose we have many guests now, each with their own fav color. For each guest, return the max beauty based on their favorite color.
Let's go back to having 1 guest. Suppose you could repaint m blocks to any color. Find the max beauty value if we could repainit m blocks.
Preparation Tips
My DSA prep => Neetcode 150 + problmes from Google Interview Experiences from Leetcode (Google has a lot of repeated questions).
What I have realized so far is that your code is just half of what interviewers are looking for. Here's the rest:
- Ask questions. You are an engineer. You are expected to ask relevant questions and get the full picture. Never expect the given problem to be the full problem.
- Specify all the scenarios/edge cases that you are considering while building the solution.
- Explain your thought process while building/explaining the solution, like, why you think this is a sliding window/graph/binary search/whatever problem, what the algo are you planning to use, why did you chose BFS over DFS, etc. Justify the solutions/trade-offs/ decisions you make.
- Be verbal while coding, like, I am using a map here to save/track the maxBeautyValue for each guest, I am using this FOR loop to build my adjacency list, etc.
- Use clean and relevant variable names.
- Calculate TC and SC for your solution. They may ask this before you start coding as well.
The main point here is, BE COMMUNICATIVE. DO NOT TAKE LONG PAUSES. If you don't know the solution immediately, just communicate what angle you are looking at the problem from. If you realise that prespective was wrong, communicate that. The interviewer will give hints if you are taking too long, which is fine, but try not to take more than 1 hint, as that can push you towards a Lean Hire or worse.
Final TIP: Ask good/personal questions to all interviews at the end of the interview. This is your last chance to make a good impression on your interviewer. Don't ask generic questions like "What is your tech stack?". So prepare a list of questions that force the interviewer to put in some effort to answer (more likely to remember you/leave a good impression), something that they may enjoy answering, and is personal to their experience. Ex:, why did you choose to work at your current team? what has been the best day at Google for you? can you tell me about an incident that made you shine at work, like a really good work memory? What has been your most important learning from working at Google? How has your perception of google shifted from before joining vs now?