google logo
Google· SDE II

Google L4 Interview Experience | USA

Location
USA
Posted
22 Apr 2025
405 reads

Summary

I participated in two onsite rounds for a Google L4 position in the USA, where I tackled specific algorithm and data structure problems. Despite some initial missteps in my solutions and complexity analysis, both rounds were positively received, and I successfully passed the Hiring Committee.

How it went

Onsite round 1:

We have an undirected, connected network of cities labeled by uppercase letters. Alice starts at city A and Bob starts at city B; both want to end up in city D. They pay by the distinct roads (edges) they cross—if they ever share a cab along the same road, that road only counts once. We need to pick routes for Alice and Bob so that the total number of distinct roads either of them ever crosses is as small as possible.

This is a repeated question on Google previous interviews. IIRC, there should be LC quesiton similar to it also.

https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/description/

I gave the 3 BFS solution for this but missed the case of disconnected graphs. The interviewer gave me a nudge with the edge case and I was able to correct the answer. I made a big blunder on the TC caluclation and called it O(V*E). The interviewer corrected me for O(V+E).

Apart from these there were no other issues on my code.

Not sure how Id rate this interview. If the interviwerer wants to be harsh he could reduce me to LH-H for those mistakes. But I'd say it should be a H - LSH.

Update

The recruiter told me this was a borderline round.

Onsite round 2:

We need a data structure that lets us insert arbitrary 64‑bit integers one at a time and, at any moment, return a “loose median.” The loose median is defined so that if the true median is not itself a power of two (say it lies between two powers of two), you can return any integer between those two powers; if the true median is exactly a power of two, you can return any integer between the next lower and next higher powers of two. We only need to guarantee that our returned number lies in that allowable interval—we don’t have to pick the exact median.

We have to implement insert(x) and getMedian() methods.

This is also a previous Google question (I have seen it somewhere in LC discussions).

I gave an answer that involves counting the buckets frequency. The interviewer wanted me write Testcases do Exception handling for everything.

We initially only included positive integers and later added 0, and later -ve integers to the questions and I have updated the code to accomodate it.

The TC and SC for this is O(1) as we only traverse 64 buckets. I thought of a better alternative of using Segment tree after the interview. Wont improve the TC but is faster.

One miss is while inserting the value I have missed the bucket variable from k to k+1.

This might reduce my interview performance.

Expecting H - SH.

Update

The recuriter told me this round was positve.

update 2 HC passed waiting for comp discussions.

R3 -

https://leetcode.com/discuss/post/6684774/google-l4-interview-experience-usa-by-an-bre1/

Questions asked (2)

  1. 01

    Minimum Distinct Roads for Two Travelers

    Data Structures & Algorithms · Hard

    We have an undirected, connected network of cities labeled by uppercase letters. Alice starts at city A and Bob starts at city B; both want to end up in city D. They pay by the distinct roads (edges) they cross—if they ever share a cab along the same road, that road only counts once. We need to pick routes for Alice and Bob so that the total number of distinct roads either of them ever crosses is as small as possible.

    Open the problem
  2. 02

    Loose Median Data Structure

    Data Structures & Algorithms · Hard

    We need a data structure that lets us insert arbitrary 64‑bit integers one at a time and, at any moment, return a “loose median.” The loose median is defined so that if the true median is not itself a power of two (say it lies between two powers of two), you can return any integer between those two powers; if the true median is exactly a power of two, you can return any integer between the next lower and next higher powers of two. We only need to guarantee that our returned number lies in that allowable interval—we don’t have to pick the exact median.

    We have to implement insert(x) and getMedian() methods.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!