Google Phone Screen - L4 (SWEIII)
Summary
I had a phone screen for a Google SWEIII (L4) role, where I was given a problem to find the first failing commit in a range and multiple follow-up questions exploring optimizations using binary search, multithreading, and parallel API calls. Initially, the recruiter informed me they would not proceed, but later offered a second phone screen opportunity.
Full Experience
University : India
Work Ex : ~3 years
Last Company : MAANG
Question :
Recently, I had my phone screen round with Google, I was asked, Given range of commits (a,b), find the pivot point from where the commit started to fails. 'a' will always pass while b will always fail. Given a api method which you can use to know a specific commit passes or fails.
I started with the Brute force approach of linear Search, then I optimised it with Binary Search.
I exlained the approaches, discussed the time complexity and dry run each of them. After the interviewer was satisfied. He told me to code binary search, which i did in couple of minutes.
He mentioned to think about the edge case, to which i mentioned that the given statement of b will always fail we will have an answer.
Follow up :
The range is very big, how would you approach the problem now.
I thought about it for a moment then mentioned we could use multithreading and divide it into to multiple subRange we will try to find the first failure point for each subrange. and then iterate over the resultant vector to get the first result.
Time Complexity : O(KlogM) K -> number of sub Range, M -> len
He asked me to do optimization. Now the api method can also handle multiple commits at the same time parallely to get the pass and fail for all of them. I thought about it. and came with a better solution that we can use the binarySearch on the subRange as well, We will try to find the failure point for mid subRange if that gives the failure try to look for smaller subRange on left side subRange else go to higher number subRange.
Time Complexity -> O(logKlogM)
Now he asked me K will be also dependent and could be N if M = 1. Which our machine could not handle again.
I thought for a sec and told him we could get the min Failure point for each subRange using the given API method which could make
Time Complexity : O(logK)
In the end, I couldn't anything else and I felt He was not satisfied.
Update :
Recruiter reached out to me mentioning they will not be proceeding further
Update :
I had a call with recruiter. She mentioned they are giving me one more chance with another phone screen.
Interview Questions (4)
Given range of commits (a,b), find the pivot point from where the commit started to fails. 'a' will always pass while b will always fail. Given a api method which you can use to know a specific commit passes or fails.
The range is very big, how would you approach the problem now.
He asked me to do optimization. Now the api method can also handle multiple commits at the same time parallely to get the pass and fail for all of them.
Now he asked me K will be also dependent and could be N if M = 1. Which our machine could not handle again.