I was approached on linkedin by a recruiter to appear for google interview for the position on Software Engineer , Machine Learning.

1. Phone Interview (Did'nt knew this would be the only tough round and cleared it just on boundary)

Define the MEX of an array to be the minimum non negative integer that is not contained in that array. for ex. [1,2,3] => 0
Given an array of length n that contains unique integer from 0 to n-1, return an array of length n+1 where array[i] = the number of contiguous subarray of arr such that mex(subarray) = i

For ex. if arr = [3,0,2,1] output = [4,4,0,1,1]
(four subarrays have mex 0, four subarray have mex 1 and so on.)

My Solution:
I was only able to come up with brute force solution. (Kindly help me find better solution ;( )

-> write two loops to get all the contiguous subarray.
-> loop from 0 to max number present in that subarray to get the MEX.
-> update the output array which stores the count for each index.
-> break the inner loop.

My onsite interview was scheduled after one month from my phone interview.

2. Coding Round 1

It was Question 4 from https://leetcode.com/discuss/interview-question/2006734/Google-or-Onsite-or-L4-or-Rejected/1378407

I am yet to find optimised solution for this. If anyone comes up with python solution. Kindly post it on comments.

3. Coding Round 2

In how many ways you can build a tower of height n, using 1X3, 2X3, and 3X3 blocks.
You can use any number of blocks, and rotations are counted as different.
Examples:

n=1 : only way we can build a tower of height 1 and width 3 is by picking 1 1X3 matrix.

n=2 : 2 ways, i.e chose 2 blocks of 1X3 or 1 block of 2X3.

rotation don't really count as they'd be the same orientaion in the above base cases.

n=3 : 6 ways

Answer:
This was simple recursion problem with base case to be predefined till N = 3

dp[4] = func(4-1) + func(4-2) + func(4-3)

Here func(4-1) is for the case where we chose one 1X3 block...and so on.

4. Coding Round 3

This was not typical coding round, but interviewer was just checking my way of approach on api design.
The requirement of api was to build a system where if a user is making a query, our system should suggest them recent N query made in past.

5. Behavioural Round

This was general Googlyness and leadership round.