• Status: Undergrad, BTech Computer Engg., Tier 2 College
• Position: L3 - Software Engineer at Google
• Location: Bangalore, India
• Date of Onsite Interviews: November, 2019

Process
Applied for the SWE Role at Bangalore and Hyderabad offices on Google’s Career Site. Soon after 2 weeks a recruiter reached out for a phone conversation with me.

• HR Phone Screen [45 mins]:
  Mostly intro, about this role, my experience related and expectations from role related questions with basic 8-10 technical mcqs on ds-algo-maths and finally some prep related discussion. In the end I was asked for five slots for next phone interviews.

• Technical Phone Screen [45 mins]:
  [1.5 months later]
  Just one Algorithmic Question: Given 2 strings of hexadecimal digits, return a string containing hexadecimal digits of their sum. For example, add_hex("12", "18") returns "2a".
  The functional code for the above problem was to be written on shared google docs.

Approach: Used 2 pointers to traverse strings from the end and adding digit by digit to get the result

Result: After 2 days I was informed that I was selected for the onsites.

• On-Site Interviews [45 mins each]:
  [3 weeks later]

  • Round 1: Behavioural

    • What are the major Differences you experienced while being in an organization as an Employee and in University as a Student?
    • What is according to you, a bad work culture in an organization? How will you improve it if you join such an org as Employee and then as a High Level Executive?
    • If you are a developer and there is an urgent need to fix an issue in your product say voice lag in Alexa and a bug in a game on Alexa, how will you prioritize the order in which you will deal with them? why? and how will you fix it? Also later, tell me about your past experience where you needed to urgently come up with a fix for your existing project?
    • Tell me about an experience in which there was a change required in the project implementation as it deviated from your goal and how did you tackle the situation?
      PS: Interview was taken by a Software Engg.

  • Round 2: Technical

    • This is a game, where given an array of length N, consisting of 1s and 0s where each block contains either 0 or 1 value. 0 represents empty/safe block, 1 represents plant/danger block. We are given a jump range [min, max] where (0<min<=max<=N). So we have a player which starts the game from block at index 0, and has to reach last block with index N-1. If the player is at index ‘i’, then he can jump on next block directly (i.e. ‘i+1’) or can jump on one of the blocks within range of [i+min, i+max]. Given, player can jump onto a block only if it has value 0 i.e. it should be empty/safe. Last and first block always have value 0. Determine if its possible for the player to reach the last block i.e. block having the index N-1.

    Eg. say we have an
    array of blocks - [0, 0, 1, 1, 1, 1, 0, 1, 0]
    jump range= [2, 5]
    ans: true
    explanation: 0 -> [ jump to next block ] 1 -> [ jump on i+5 ] 6 -> [ jump on i+2] 8 [Reached]
    Eg. for array [0, 1,1,1,1,0] , range = [2,3], ans: false

    Approach: Solved with Memoization from end of the arr, checking from which indices its possible to get to any index ‘i’, then tried to do this recursively for every possible index till we get to the index 0.

    PS: Time Complexity for my solution was O(N^2) with space complexity of O(N).

  • Round 3: Technical

    • Like Candy crush, if 3 or more same type of candies form a linear cluster, they explode/break/disappear. In a similar fashion, you are given an array of candies say [1, 2, 2, 2, 1, 1, 3], find the final configuration of the candies when the candies are crushed. At a time, if multiple clusters with more than 3 candies exist, choose any 1 of the cluster and break it. If there are multiple answers, print any one.

    Eg. for above config - [1,2,2,2,1,1,3] -> burst the candies with 2,2,2 cluster -> [1,1,1,3] -> burst the candies with 1,1,1, which is newly formed -> [3]
    Thus the only answer for the above config of candies is [3].
    Eg. for config - [1,1,1,2,2,2,1], you can burst either first cluster with [2,2,2] or [1,1,1].
    thus one of the answer will be [] if [2,2,2] is crushed first and then cluster with [1,1,1,1]

    • Follow up for the above Question, given an integer K, do this break operation only if cluster has K or more same candies

    Approach: My approach for this was similar to the one for the Q. below using Stack and Compression - https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

    PS: Time Complexity for my solution was O(N) with space complexity O(N) for both.

  • Round 4: Technical

    • Given a gird of NxN cells, with Integer cell values, we can define a path effort of a path from source (0,0) to destination (N-1, N-1) as the max of the absolute differences of the adjacent cell values. While traversing, you can move up, down, left and right - 4 moves from current cell in grid. For a given Threshold value, find if it is possible to have a path in such a matrix with effort not greater than the threshold value, from source to destination.

    Eg. if we have a 3x3 matrix as follows -
    [[1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]]
    Lets say threshold is 3.
    Result: true
    One of the path is : 1 -> 2 -> 5 -> 8 -> 9. the abs differences of the adj cells in this path is - [1, 3, 3, 1], max of them is 3 => thus the path has an effort 3.

    • Follow - up: Find the Minimum value of the path effort out of all the possible paths from source to destination.

    Approach: I discussed and coded the Brute force solution discussing as to how the time complexity will be exponential, it was backtracking based solution.

    PS: Time Complexity for my solution was Exponential for both Questions.

  • Round 5: Technical

    • Given a building with floors numbered from [0 to N], and source floor X, destination floor Y, ( 0 < X, Y <= N ) given range of jumps [up, down], i.e. say you are at floor ‘i’, then you may jump to any one of the floors in 1 move i.e. to -> i+1, i+2, … , min(i+up, N) in upwards direction, or to -> i-1, i-2, …, max(i-down, 0) in downwards direction. Find how many minimum jumps you need to reach the destination floor Y, starting from source floor X.

    Eg: say building from floor 0 to N (left to right) - [ 0, 1, 2, 3, 4 ] (Ignore the array values, those are just the floor numbers for reference)
    , X=0, Y=4, jumps=[3, 1]
    result: 2
    explanation: 0 -> 3 [up] -> 4 [up]

    • Follow Up - 1 : Instead now with up and down values you may jump only on min([i+up], N)th floor or max(0, [i-down])th floor. Find if its possible to reach Y from floor X, and if yes print min no. of jumps required to do so, else print -1 if not possible.

    Eg: building - [0, 1, 2, 3, 4]
    X=1, Y=4, jumps=[3,1]
    result: 2
    explanation: 1-> 4 [up] -> 3 [down]

    Approach: One approach that I thought was, suppose if floor Y is above X and that it is not possible to directly reach Y with few ‘up’ jumps then, starting from Xth floor we continue to use the ‘up’ no. of jumps until we pass the Yth floor, once Y is passed then check the diff between Yth and current floor. If the diff is divisible by down then its the min. ans, else keep on adding jumps to the current floor till the diff is not divisible by ‘down’. We also start to keep track of the remainder of division [diff / down] every time ‘up’ is added in current floor after Yth floor is surpassed. If at any time the remainder that we get is visited earlier then we are getting into loop and need to stop. Apply this same approach when Yth floor is below X, up and down values are changed, else everything remains the same. This approach has O(N) time and O(N) space complexity in the worst case. I coded this solution and then interviewer again modified the Q.

    • Follow Up - 2 : Same rules apply for up/down jump but now, X and [up, down] jump values are fixed, and you are fired a query for destination floor Y, so for every query for floor Y, find the min no. of jumps.

    Approach: After discussion, the interviewer gave a hint to think about and traversals, and then I came up with the BFS solution. Here if we are at ith floor with x jumps then there are 2 choices going at (i+up)th floor and (i-down)th floor in x+1 jumps if those floors are unvisited. So this is true for every floor when starting to traverse from floor X. Do this until we get till floor Y. If reaching the floor Y is not possible even after visiting all the possible floors, then its not possible to reach. Else the count of jumps when the floor Y first is visited in BFS traversal will be the min. jumps as required.

    PS: Time Complexity of my solution for the last Q. was O(N) for preprocessing and then O(1) for each query, with Space Complexity of O(N).

Results:
After a month later recruiter called, said that the reason for my rejection was that I had mixed feedbacks, 60% positive and 40% negative sort of, was also informed that coding quality could have been better, was able to arrive at solution but needed a lot of hints and said that I struggled with the speed of solving problem. Apart from that even though I was able to communicate my thought process very well & knew how Solution would look like, it didn’t convert into when I started to code it on the chromebook.

Preparation:
Practised for around 2 and a Half months before on-sites.

Solved 159 LC problems - 11 easy | 108 Medium | 40 Hard

GFG for basic ds algo top topics,
LINK: https://www.geeksforgeeks.org/interview-preparation-for-software-developer/

Tushar roy Youtube Channel for solutions - https://www.youtube.com/user/tusharroy2525
Feel free to explore and see what best suites your prep needs.

Additionally you can refer to -
https://github.com/donnemartin/system-design-primer#index-of-system-design-topics
youtube playlist https://www.youtube.com/playlist?list=PLkQkbY7JNJuBoTemzQfjym0sqbOHt5fnV
for basic system design prep.