Hey folks, Namaste.
I am a Software Engineer(2021 graduate) working as a Backend Dev at a product mid size startup. I was reached out by a google recruiter in November on LinkedIn for an L4.
I took 1 month of time to prep and scheduled my phone screen interview in Januray 2024.
PS: I am sharing the questions as I didn't sign any NDA and they are not any new questions. You would have heard almost all of them.
Phone Screen
Duration: 45 minutes
Questions asked: 1
Problem Statement: You are given an infinite stream of integers, and you need to find the median of this running stream and report it.
Discussion: Firstly I gave a brute solution to store them in array, sort and give median. Then told them that this won't fit in memory and give OOM. So I asked them if there are any constraints on range of the numbers in stream. To which they asked, how would that help. So I said we can store the numbers count in an array and find the median.
They asked me to assume the range [0, 1 million]. I quickly spitted a solution using Segment Tree + Binary search.
Solution: For any i, Segment Tree will store the sum of frequency of [0, i]. Then to find median I simply need to find an i where sum[i] is >= total elements / 2. That is our median, I did so via Binary search and the solution is of O(Log^2(N)) time complexity.
I implemented the binary search solution. They asked me to not implement Segment Tree and just assume its instance exists and use it.
Feedback: Hire for L4, Strong hire for L3. They mentioned in feedback that code could have been more modular.
Now there were 3 more coding rounds which I scheduled on same day with 1-1.5 hrs gap between them.
Coding Round 1:
Duration: 45 minutes
Problems asked: 1
Problem Statement: Build a google search like feature. Two method to implement
- Search a keyword.
- return the most recent N searches. N is fixed across all queries.
Discussion: I gave a solution using Doubly linkedList to store most recent N searches, some map etc(tbh don't remember exactly). It is straight forward, but it's implemetation was not(atleast for me). But thankfully I comlpeted the implementation on time and made sure that my code is modular, the interviewer seemed satisfied.
Feedback: Hire for L4, they written like good code and debugging skills etc.
Coding Round 2:
Duration: 45 minutes
Problems asked: 1
Problem Statement: Given a list of integers, answer Q queries of type [l, r]. Each query needs to return the maximum element in the given range. Simple, right?
Discussion: I gave a brute solution first. Then gave a Segment tree solution and explained about the time complexity. Now during explanation he asked me to prove why search is logN, which I explained intuitively(like we divide the array in half each time and store answer, max height of tree will be logN). He said if during search query(l, r) you are going max(query(l, mid), query(mid+1, r)), here you are going both side of tree so how come it will be logN. I said it will go left/right some constant number of times and eventually some range will satisfy and it won't go further.
but then he said "I understand what you are saying, but your answer is not conclusive and you need to prove mathematically". Which I tried and couldn't do.
Then during implementation it took me 4-5 minutes to write build function (last time I implemented it was in 2019 :( ) and missed the base condition, he pointed it out and I fixed it. Solution was completed. He said looks good.
Feedback: No Hire
- Gave solution but couldn't explain time complexity. fine.
- He exaggerated the base condition miss in feedback : "implemented a solution which would run infinitely and candidate fixed it only after explicitly pointing out...". Even though during interview he simply asked me, when will this function stop and I quickly realised, explained and fixed it.
Coding Round 3:
Duration: 45 minutes
Problems asked: 2
Problem Statement 1: Given some intervals, find their intersection. Easy enough, took some time to explain to him as I was having some issue understanding his accent and vice-versa. Implemented it. 20 minutes went by already.
Problem Statement 2: Modification of 1. It was some greedy approach which I explained and implemented. He was satisfied and time was up.
Feedback: Lean Hire for L4, because the recruiter said that the interviewer had 1 more question to ask apparantly and due to time constraint they couldn't.
Behavioural Round:
Duration: 45 minutes
Super nice guy from US. Asked me largely related to my work:
- Tell me about a time your manager assigned you something, whihc u did not have much context and they went on leave for a week. How would you handle such a situation.
- A time when you delievered a critical project under time constraint.
- How would you handle if u join a team where everyone's working style is differnt than yours etc.
and a few other similiar questions.
Feedback: The recruiter just said the feedback is positive and the Interviewer has written good things only.
Now, due to one No Hire and Lean hire my chances were low so I asked the recruiter if a follow up round can be done to compensate the no hire. they said they will try.
They scheduled one more coding round.
Coding Round 4:
Duration: 45 minutes
Problems asked: 1
Problem Statement: Given N remote machines which do some processing and return a future. You have to process Q queries and each query takes some amount of time. I have to find total time to process all queries. A query can be ran on any machine.
Discussion: I gave a solution and while explaining gave wrong time complexity to which he gave a hint. then I corrected it and coded the solution.
Feedback: Recruiter didn't tell in terms of hire/no hire. they just told what was positive and what was negative(i.e. needed guidance to correct time complexity).
As my feedback was not very good for coding rounds, the Recruiter said we will have some team matching rounds to some Hiring manager feedback to strong your case(pardon for my english).
Hiring Manager Round 1:
The HM was from US, but team was based out of banglore. Just regular talk like what I am looking for, why looking for a change and mostly about what team does.
Feedback: The recruiter said the HM gave good feedback and they are interested in my profile. But a few days later the recruiter said that the position is filled.
Hiring Manager Round 2:
In parallel I had other HM round from a team based out of Hyderabad. Same questions asked. This HM asked more questions similiar to behavioural round and about my projects as well.
Feedback: Same, the recruiter said the HM gave good feedback and they are interested in my profile. After approval from HM's manager my packet moved to Hiring committee.
The moment of truth: Hiring Committee:
HC gave No Hire for L4, Hire for L3. Laugh on me.
The recuriter mentioned that the No Hire round led to this decision as the feedback was very poor from coding round 2. The HC did not consider the additional round(coding round 4) for same reason.
Final Decision:
The HM which approved were not going ahead as they wanted L4 only. So my recruiter said they will do more team match if I join for L3. I asked recruiter about comp. for L3 and she said max they can do for first year is (40-45 L including base + variable + stocks), verbal offer only. Also my recuriter said that there will be a cooldown of 1 year if I decline.
After a lot of thought and discussion with some friends at Google, they suggested to not go as L3 at almost 3 years experience and try later or join somewhere else.
PS: My recruiter was very helpful through out the process.
So I declined the offer.
the final verdict came in April first week. Successful waste of almost 4 months :) But anyways, until next time ...