Status: 2 yr work exp. 2017 CS bach grad.

Google recruiter reached out after I completed my Foobar challenge. My chat with interviewer was for 15 minutes which included a CS rapid fire asking basic questions. He stressed on coding a lot without an IDE and use a single programming language to prep. Recruiter essentially gave me 2 months prep time.

Phone Interview:

• 1 round with an engineer from NYC office at 7:30 pm IST.
• Moving Product from Data Stream

Interviewer comminicated that phone is cleared and scheduled onsite for approx 10 days later.

Onsite

Round 1:

• Interviewer chit-chatted and mentioned he'll ask 2 questions in 45 minutes.
• Sort a Partially Sorted Array
  • I spent some time in giving non-optimal answers and then an optimal answer O(n) hit me.
  • Coded it up on laptop.
  • Ran test case on paper.
  • Took me 30 minutes in total. I felt the interviewer was a bit slow in reacting to my solution as well.
• Transform QR code type matrix to a barcode type matrix. Given a binary matrix (only 0's & 1's) of m x n and numbers x & y, where x <= y. Flip numbers in a column to either 0s or 1s such that a block is either all 0s or all 1s. The resulting block should be atleast x columns & atmost y columns wide. Minimize the number of flips required for this transformation.
  • I could almost instantly tell him that the problem is solvable using DP and gave him the parameter for minimizing the DP solution.
  • I was panicking like anything cuz only 15 minutes were left.
  • The interviewer gave me two hints to keep me on right track. I could essentially scribble recursive code on paper.
  • Since we were out of time, we discussed time complexity of this problem and I mentioned that memoization can be used to optimize this.

Round 2:

• I asked interviewer how many questions does he have and he said depends on my speed.
• Min Diff Between Given Path and Path in the Graph
  • I spent some time on understanding the problem. The fact that we can keep cycling in the graph wasn't mentioned upfront and I had to literally extract that information from the interviewer. This information did throw me offtrack.
  • I mentioned that the solution involves BFS but struggled a bit as I tried to give an optimal solution up front. Interviewer pressed on to give atleast one solution and I came up with a brute force solution. I demonstrated my solution on board and discussed time complexity of the solution. Interviewer was convinced and I coded that.
  • We ran out of time by the time I had coded and had just enough time to dry-run my code. We couldn't discuss an optimal soultion.

Round 3: [Googleyness & Leadership]

• Questions on my recent major project.
• Challenges with my manager.
• How would I work in a team.

Lunch

Round 4:

• This was a strange round. The interviewer seemed to be working most of the time I coded the solution.
• https://leetcode.com/problems/confusing-number-ii/
  • There is only a set of digits which satisfy this criterion and hence all numbers composed of these digits are the answer.
  • I gave a brute force solution which went through all numbers between 1-750 and then a minor optimal solution. However my code for the optimal solution was pretty brutal. Interviewer suggested I present a better code.
  • I suggested a number a generator. Then he proposed a solution and asked me to code it. I was actually surprised when he did this as we were only 10-15 minutes into the interview.
  • I coded it and my interview was over. Since we had some 10 minutes left, I discussed his team and his work at length.

Round 5:

• https://leetcode.com/problems/distribute-coins-in-binary-tree/
  I knew this and could propose a solution almost instantly. I discussed this on board and then coded it. I actually messed up the board solution and had to re-explain after coding it.
• We still had 15 minutes left. We discussed a design based problem where he wanted me to design an API which load tests a wesite. If I can recall correctly he had mentioned that he won't be evaluating me on the solution and purely wanted to gauge my thought process. The discussion was fun. I did give 2 solutions which we discussed at length. Can't say much about what happened here.

Now I'm anxiously waiting for recuriter feedback. I've mixed feelings about round 2 and round 3.