Google L4 Interview Experience | USA
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.
Full Experience
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/
Interview Questions (2)
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.
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.