Google India Software Engineer L4 Interview Experience

Hi everyone, I'm excited to share that I'll be joining Google as SDE III. This community has been really useful in helping me prepare for the interview. So, I would like to give back to the community by putting my interview experience.

The overall process took close to 4 months starting from the application. The below questions are simplified from the actual question as I can’t be disclosing the actual question.

Phone Screen Given a stream of float values, find the mean of last n values. Follow up - Given a value k, find the mean of last n values excluding k highest values from the n values.

Solution - Solved it using a running sum for the first question. For the follow up I used a max heap along with the running sum to exclude k highest values every time we need to compute the mean.

Verdict - Pass

Interview 1 A graph of movies is given where each movie also has a rating. Two movies are similar if they are connected in the graph. Task is given a movie, we need to find the top N similar movies with highest rating. Follow up - Movies are added dynamically and we need to do same task as above in between. How do you modify the code?

Solution - Solved it with doing a BFS from the given movie, and using a min heap to track the top N movies found so far. I did not have very much time left to answer the follow up but suggested a DSU approach to keep track of similar movies and looping through all movies to find the top N movies using the same min heap approach and modified the existing code.

Verdict - Lean Hire Feedback - There were some issues identified with testing and debugging. I think it was mostly due to the coding of follow up being incomplete.

Interview 2 https://leetcode.com/problems/minimum-window-substring/description/ Same question is copy pasted along with the same test cases.

Solution Gave a sliding window solution where I keep track of frequencies of chars on the window. As I slide the window I will modify the frequencies and I will check the validity of window by comparing the frequencies with the string t.

Verdict - Hire Feedback - Made a couple of implementation mistakes while coding, but I was able to correct some of them by doing dry run on my own. I think this lead to Hire instead of Lean Hire.

Interview 3 Given two n-ary trees A and B where each node has a key K and a value V. We need to create a new tree following the below rules If A just has node (K, V1), B just has node (K, V2), the new node will be (K, V2) If nodes on A and B has same key, the merged node will have it’s children also follow the same rule and the order should follow the order of A first and then followed by order of B.

Ex:

A:
  K1: U1
  |-- K11: U11
  |-- K12: U12
  |-- K13: U13
  K2: U2
B:
  K1: V1
  |--K11: V11
  |--K21: V21
  |--K22: V22
  K13: V13

Merged Node
  K1: V1
  |--K11: V11
  |--K12: U12
  |--K13: U13
  |--K21: V21
  |--K22: V22
  K2: U2

Solution - Solved it using recursion and keeping a hash map of keys and values of B nodes’ children at each call. We’ll then loop through A nodes’ children and construct merged nodes using recursion. If any child node key in A is not present on B, we can just add to merged node. Otherwise, merged node obtained from recursion is added. After all this, we can add remaining B’s child nodes.

Verdict - Strong Hire (Self Verdict) Feedback - I felt this was my best round, where I made a very minor mistake in base case, I was able to figure out some implementation mistakes on my own in the dry run.

Interview 4 - Googlyness I was asked questions on my projects on my resume, and also tested in depth on some of the projects. Then some behaviourial questions are asked. If you follow the STAR pattern and answer the questions, that would suffice.