Google interview experiences | SDE | Set-2

Question

All interview experiences for Google  can be found using the tag "google_interview_experiences" in the search bar.

Here is the link :  https://www.desiqna.in/tag/google_interview_experiences

Answer 1

Recently, I got an opportunity to interview for Graduate Software Engineer Role at Google for Warsaw Location.

 

The recruitment process started with initial 15 minutes discussion, where the HR asked about my past work experiences and internships I did. She did'nt asked any technical question on Data Structures or Algorithms like TC of any algo or something like that since she was from non-tech background.

 

Then, I was asked to give some possible dates for the first phone screening round which I gave and my phone interview was scheduled on one of the date which I gave.

 

Phone Interview started with sharing of brief introduction at both ends.

 

Then the interviewer gave this question :-

 

You are given a function :-

f(n) = 3*n + 1, when n is odd,
f(n) = n/2, when n is even.

Find the minimum number of steps to reach 1.

7 -> 22 -> 11 -> 34 -> 17 ->52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -.> 2 -> 1

Minimum Steps = 16

 

I was able to write an efficient code for this problem in 15 minutes, while simultaneously explaining the approach to the interviewer.

 

He was satisfied with the code I gave.
Then he gave me a follow - up question for the above question.

 

Follow Up :-

 

You are given a range of numbers from 1 to N, find the number which will give maximum minimum number of steps using the above function.

Suppose N = 4

1 = 0 steps
2 -> 1 = 1 steps
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 = 7 steps
4 -> 2 -> 1 = 2 steps


Here, the output will be (3, 7) where 3 is that number and 7 is the maximum minimum number of steps

 

I was able to give the approach for this as well, and after the interviewer agreed with my approach, I coded my approach.

 

Then he told that for large values of N, it will take a lot of computation steps, to calculate minimum steps, so can you optimize it ?

 

Then I realized that there are overlapping sub - problems, like when we are calculating minimum steps for N = 3, we reach at a point when N becomes 2, so for 2 we have already calculated min steps, so why we are calculating again ?

 

So, without even delaying a second, I told I can use Dynamic Programming to optimize my code, we can use memoization to store the results we have already calculated.

 

But till then only 5 minutes were left, so I tried to code the dynamic programming approach, anyhow I was able to code in that timespan as well, by modifying my existing code, he then found a bug in the code, then after dry running a testcase I was able to figure out the bug and corrected it.

 

But then, at last, he said that I am worried I can't test your code on other testcases since no time was left. So, he closed the technical discussion there only.

 

Then, he allowed me to ask some questions if I had, so I asked about his contributions and on what technology he is working. This discussion took 5 more minutes and he left the meeting after wishing me good luck for the results.

 

After 4 days, I got a mail from the HR, that they are not moving forward with my application at this point, and asked me to book some time to discuss about the feedback.

 

Feedback :-

 

In the feedback she told me that in the follow - up question, interviewer was directly expecting the optimized approach rather than starting from brute force approach, and I did'nt asked the required question from the interviewer wether I should start from brute force or optimized approach.

 

Though, she also told that the interviewer was quite impressed by the thought process I was having, and how clearly I was explaining each and every line of code which I was writing, and she also praised about the quality of code I wrote since I tried my best to use relevant variables and made the code as much modular as I can.

 

My thought proces was to start with the brute force and gradually optimize my approach till end, this way of thinking can work for all other companies but not for Google.

 

Overall, it was a great experience, interviewing for Google, I'll apply again once the cool down period ends.

 

Some piece of advice for candidates having their Google interviews scheduled :-

 

1.  

   When you are explaining your approach to the interviewer, explain all the approaches from brute force to optimized at once, but directly code the optimized approach only, don't make the mistake of coding the brute force approach.

    

2.  

   Keep the quality of your code high, use relevant variables and make it as much modular as you can. Because, this is a very important criteria on which they judge.

    

3.  

   Try to give as much mock interviews as possible before the actual interviews, that helps in lowering the stress in the actual interview.

    

4.  

   Always try to code as fast as you can so that there is some time left for testing and discussing the code.

    

5.  

   Lastly, cover all the topics of DSA, don't leave any, because you don't know when your day is bad, and you get a question from the topic which you have left. Believe me, that hurts more than a breakup :-)