Google | L4 | Selected

Background:
I took a referral from a friend and then was reached out by a recruiter (~mid march) from Google within one week of applying. Was asked to have a quick background check call which also happened in the same week. Post that, I asked the recruiter to allow me about a month's time for preparation as I have some strict commitments in my current org. Finally appeared for the screening round in the last week of April.

Screening round:
Got this exact same question: https://leetcode.com/discuss/interview-question/4964533/Google-Phone-Interview-Question.

My solution: Since all floating values will be unique, used a set in c++ to store all the values in a sorted manner. As the floating point values continue to come in the stream, will look for any valid triplet. If a valid triplet is found, remove them from the set. Else, store the current floating point integer from the stream in the set.

Suppose the current set looks like: X1,X2,X3,X4,X5,X6,......Xm
And the current floating point integer received from stream is F. Then for a valid triplet to be removed from the set, we need to consider 2 elements immediately smaller than F and 2 elements immediately greater than F.
X2,X3,F,X4,X5
3 possible triplets could be:

X2,X3,F
X3,F,X4
F,X4,X5
If any of the above holds the condition |a-b|,|b-c|,|a-c| <=d as true, remove the numbers Xi(s) from the set and return them. Else, insert F into the set.

Time complexity: O(logn) - general insert,find,erase operations in a set.

Verdict: Not sure about rating but the interviewer seemed happy and the recruiter reached out after 2 days to schedule the onsite rounds.

Follow up: Had asked her to give me 20 days time because of current commitments, to which she agreed and scheduled the interviews mid-May.

Onsite Round #1
Question: https://leetcode.com/discuss/interview-question/4574669/Google-or-Onsite-or-Find-partitions/

Solved this using recursion with memoization. Took a 1D dp array where dp[i] represents the number of possible partitions starting from an index i. Our answer will be dp[0]. (Look at the solution in the comments in the linked article from overkillerxd.

Interviewer was happy with the solution and asked a follow-up along the same lines. Answered that as well.

Onsite Round #2
Question: https://leetcode.com/discuss/interview-question/4173795/MAANG-interview-question/

Was not able to come up with the greedy solution. Came up with a dp solution - took up almost the entire time. Had suggested the interviewer, we could use some greedy solution but right now I am not able to exactly come up with a solution.

Onsite Round #3
Question: Given two arrays A and B, each of size n, where A[i], B[j] represent the strength of a signal received from 2 antennas placed at two different places. A signal is considered to be valid if it is present in both the arrays A & B at a distance <= D. Find the number of valid signals.

Example: A=[1,3,4,3,4,5,6], B=[4,1,8,7,6,3,2], D=2
Answer: The valid signals are A[0] (=B[1]), A[2] (=B[0]), A[3] (=B[5]). Hence the answer is 3.

Solution: Solved using a sliding window of size 2d+1 storing the frequency of each signal value from B. Start traversing the array A and as we move forward to element A[i], add the element B[i+d] to the sliding window and remove element B[i-d] from the silding window. If the frequency for A[i]>0 in the current sliding window, increment the answer and decrease the frequency for A[i] in the window.

Interviewer was happy with the solution.

Onsite Round #4
There was some confusion with the recruiter. Was supposed to appear for the googleyness round but instead appeared for another onsite round. The recruiter clarified later that this was not the plan.

Question: https://leetcode.com/problems/logger-rate-limiter/description/
Was also asked a follow-up where I needed to print message only when it appears once in a window [t-10,t+10]. Solved it using a map (sorted) storing mapping from time to message. If a message appears at a time T1 and appears again at a time T2 where T2<=T1+10, I mark the entry with negative timestamp in the map to indicate the entry is invalid and should not be printed. At every shouldPrintMessage call, will call another method which will print all the valid messages (with time value positive in the map) which appeared at a time <=timestamp-10.

Interviewer was very happy with the solution.

Was already into team matching before scheduling the Googleyness round. Matched with the second team.

Googleyness Round
Was asked general questions about my experience at Microsoft. How I solved ambiguties, about a time when I had a conflict with my manager. Was a very friendly discussion.

Took 10 days to prepare my packet, get the hiring committee approval.

Verdict: Selected.

Compensation post: https://leetcode.com/discuss/compensation/5348790/google-l4-hyderabad/2472338