Google | L4 | Offer

Background:
I asked a friend who was also interviewing at that time to give my details to the recruiter, the recruiter reached out via LinkedIn. Had the phone screening round in the same week. Took about a month's time to prepare for onsite rounds.

Screening round:
The recruiter asked several one word questions. I can't recall the exact questions but they were centered around different types of Algorithms, like how to get shortest path from one vertex to all other vertices (Dijkstra's algorithm). Was also asked time complexity of some sorting algorithms, best case, worst case and average. All in all this was a quick screening round with some 10-12 questions. The recruiter was satisfied by my answers and explained the further interview process and asked how much time would I like to take for preparation.

Verdict: Interviewer seemed pretty happy with the answers and started processing me for L4.

Onsite Round #1
Question: https://leetcode.com/problems/check-if-word-can-be-placed-in-crossword/description/

Solved this using 2 pointer approach. We had some discussions around the time complexity, the interviewer seemed satisfied by my answers.

Follow-up: If there was a list of strings in the input and you had to filter out the strings that can be placed.

I used streams to utilise the already created method to filter words from the input list. The interviewer was happy with the solution

Verdict: Hire

Onsite Round #2
Question: Implement the word suggestion engine we see in querty keyboards on phone. This was in my opinion the best interview I had. In the keyboards on our phone if we want to type out a word, we can swipe over the letters and it will suggest the best matching word. The interviewer asked me to implement this algorithm.

Was given list of strings as disctionary and a string input which this denotes all the characters falling under the swipe on the keyboard.

Two main inputs

User path
E.g. "qwertyuiujhgcvghbnjk"
List of dictionary words
E.g [aardvark, angel, dog, quick, quickly, quickening, TikTok, zebra]

Ans: qwertyuiujhgcvghbnjk
quick

This question seemed very difficult at first, but given that we are working with a dictionary I was sure Tries would come into the picture here. I came up with an approach using tries within a few minutes and discussed the algorithm with the interviewer. I then implemented the solution and pointed out that building the Tries in memory can be done as part of a boot up proccess instead of doing it everytime we want a suggestion. The interviewer was very satisfied with the approach and the solution provided.

Follow Up: How would you take into account any mistake made by user in the input.
I modified my approach to consider every character a mistake and possibly correct.

Verdict: Hire

Onsite Round #3
Question was similar to: https://leetcode.com/problems/merge-intervals/description/

This was a straigth forward question had already solved this before. But, I made one mistake in the implementation and got stuck at one point in the interview with 1 simple edge case. This mistake was not unnoticed by the interviewer and even though I was able to come out of it later on, the interviewer seemed not very happy with that fact.

Verdict: Lean No Hire

These interviews are very strict on how you are thinking about your logic, and communicating your thoughts. Always think out loud in such situations so that the interviewer is also on the same page.

Onsite Round #4
Question was a variation of: https://leetcode.com/problems/random-pick-with-weight/description/
Given a key and its weight as integer, create a Weighted Random Key generator.

It took me sometime to come up with the solution, was able to solve it in given time then. The interviewer was not satisfied with my first approach as it was not at all space optimised but later was able to come up with a better approach.

Follow up:
Input weight is float instead of int

Follow up:
Implement proper error handling and check for corner cases or wrong inputs. (like weight is 0.0 or negative)

Verdict: Hire

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

Verdict: Hire

Took a lot of time in the team matching phase (about 2 months). Matched with 2 teams and later selected one of them. 10 days to prepare my packet, got an SOS from the HM and got the HC approval. The entire process took more than 5 months.

Verdict: Selected.

Compensation post: https://leetcode.com/discuss/compensation/5384612/Google-or-L4-or-Bangalore-Accepted