Google | L4

Background:

After receiving a referral from a friend, a Google recruiter contacted me within a week of my application around mid-March. I had a quick background check call that same week. Following that, I requested about a month for preparation due to commitments in my current organization, which the recruiter accommodated. I appeared for the screening round in the last week of April.

Screening Round:

I received a specific question during this round. My solution involved using a std::set in C++ to store unique floating-point values in a sorted manner. As values streamed in, I checked for valid triplets. If a triplet satisfied the condition |a-b|, |b-c|, |a-c| <= d, I removed those numbers from the set; otherwise, I inserted the current value. The interviewer seemed pleased, and the recruiter scheduled onsite rounds within two days. I requested 20 additional days for preparation, which was granted, scheduling the onsite interviews for mid-May.

Onsite Round #1:

This round involved a partitioning problem. I solved it using recursion with memoization, employing a 1D DP array where dp[i] represented the number of possible partitions starting from index i. My answer was dp[0]. The interviewer was satisfied with my approach and asked a follow-up question along similar lines, which I also answered.

Onsite Round #2:

I faced a question which I attempted to solve with a DP approach, consuming nearly all the available time. I suggested to the interviewer that a greedy solution might exist but admitted I couldn't formulate it precisely at that moment.

Onsite Round #3:

I was given a problem involving two arrays, A and B, of size n, representing signal strengths. The goal was to find the number of valid signals, where a signal is valid if it exists in both arrays within a distance <= D. I solved this using a sliding window of size 2D+1, storing frequencies of signal values from array B. As I iterated through A, I maintained the sliding window and updated frequencies, incrementing my answer when a matching signal was found. The interviewer was content with my solution.

Onsite Round #4:

Due to some confusion with the recruiter, I unexpectedly appeared for another technical onsite round instead of the planned Googleyness round. The recruiter later clarified this was not the original plan. The question was a variation of the Logger Rate Limiter problem. I also tackled a follow-up where I needed to print a message only if it appeared once within a window [t-10, t+10]. My solution involved a sorted map mapping time to messages, marking invalid entries with negative timestamps. The interviewer was very pleased.

I was already in the team matching phase before the Googleyness round and successfully matched with my second team preference.

Googleyness Round:

This was a friendly discussion where I was asked general questions about my experience at Microsoft, including how I handled ambiguities and resolved conflicts with my manager.

It took 10 days to prepare my packet and secure hiring committee approval.