Status: Final year CSE, IIT
Position: Software Engineer
Location: Banglore, India
Date: December 1st, 2020
Mode: On-campus Placements
Compensation: here
Process:

• 1: online test (2 questions)
• 4: Coding interview round
• 1: googleyness round

32 students from 290+ were selected for interviews based on the test score and resume.

I recieved an email invitation to a session to help me prepare for google interview. That's how I came to know that i was shortlisted for interviewing with google On-campus. Then after a couple of days, I got a call from an HR describing the interview process. She also sent me some material to prepare for the interview. (It had links to sites like leetcode).

I had 3 Technical rounds on 24th Nov.

1st: Coding

The interviewer told me to open the doc rightaway and gave me a question.

Q1: A single processor system has some process scheduled, with some startTime and Duration. given a new process can we schedule it with out removing some pre-scheduled process.

I shared BS based approach
Interviewer asked me to implement it
I did, she asked me to use lower_bound instead of actually implementing BS.
She asked me to find some bugs in the code.
I found and fixed one.
Then she pointed another one, i fixed that too.
Then she asked me to write the time and space complexity.

Q2. After that she asked a follow up saying that now the computer has 4 processors, how will we check if a new process can be scheduled to any of the processsor?

I shared an approach involving cordinate compressing the start and end time, then making an array and intializing it with 0, then for each process doing arr[start]++, arr[end+1]--. where start and end are the compressed representation of original values. then it told that i would build a segment tree to find the range. And finally I told her that i'll find the smalles interval containing our process from the compressed co-ordinates using Binary Seach then i'll find the range max in that range if it is 4 then we can't schedule the process else we can.
She didn't ask me to code this But told me to write the time and space complexity of my solution.

Overall the round went pretty well.

2nd: Coding

He told me a bit about himself and asked me to describe my thesis project. After that he told me to open the coding doc and started asking questions.

Q1: The interview told me to find no. of ways to make 'K' non-empty set from 'N' unique objects.

He gave some sample like 1, 1 -> 1; 3, 2 -> 1; 4, 2 -> 2.
Seeing the samples it was pretty clear that the objects are not unique. When i pointed that out and asked the interview that is this problem equivalent to the no. of ways we can fill N identical balls into K identical bags such that each has atleast one ball?
To which he replied yes, He was not thorough with the problem himself. I asked him about the range of N to which he replied
1 < N <= 1e6, K <= N
I dropped the idea of any DP based solution and started focusing on solving this using PnC. But the interview told me to come up with a reccurence relation, I was really drawing blank at that point and told him that even if we find a relation in terms of N, K we would have N x K states.
I failed to find any correct recurrence relation. and the interviewer also told me to forget this and moved on to the next question. After the round i found the relation online.

Q2: There's a directed graph find the shortest cycle from a source node.

I told a dfs based solution using the standard cycle finding algorithm and storing length of cycle whenever we encounter one and returning the min value. He told me do write the time and space complexity of my solution
He told me to imporve my complexity, i was drawing blank. He suggested to use BFS. I agreed and wrote the time complexity for that as well
The he asked me to code the solution but now i have to return the nodes of the shortest cycle starting from the source. I coded the BFS and kept parent array to retrive the nodes of the cycle when we found it.

After this he asked me to ask any question that i had, i did, he answered. interview ended.

Overall this round could have gone better, I thought 1st question was really hard.

The HR called me and said that i have a 3rd round and it is a deal breaker.

3rd: Coding

The interviewer told me about himself, his work. and asked me to introduce myself, after which we moved staraight to the interview.

Q1: Given a 2D matrix, The cost to move to an adjacent cell(4 direction, up, left, down, right) is defined as the absolute difference between the values in the cell. A path's cost is defined as the maximum cost of any step taken to traverse that path.
Given a cost find if we can move from top-left to bottom-right in cost less or equal to that.

I told and implemented a BFS based solution, he asked me to write the time and space complexity.

Q2: Follow up to the first question find the least cost to go from top left to bottom right.

I told him that if we plot a graph of cost vs is_possible in the last problem, it would be like step funtion's graph and the inflection point would be our answer. And we can find the inflection point using Binary Search. He agreed.

I coded the solution using the function in the previous question as the check function. He asked me to do the TC, Space analysis, I did.

I solved these 2 questions pretty quickly so he decided to ask another one.

Q3: Given an API getTower(int n, int m) -> {int, int} that returns a location in a field of NxM dimensions. Initially the field is empty, we have to call the api several times and set towers at the given locations, two towers are connected if they are adjacent to each other (4 directions). Find the no. of times we call this api before the left side of the field is connected to the right side.

Ex:
Not connected

##T
#TT
T##

Connected
#TT
TT#
##T

I shared a DSU based approach where for each reprentative of the set we can also keep a pair of booleans denoting wheather they are connected with left/right. Whenever a set is connected to both sides we can return the count of towers. I coded the solution
Interviewer was satisfied with the solution.

He asked me to ask him some questions, he also asked me some behavioural and situational questions.

This round went great, the codes were bug free and i had the optimal approaches for each question very quickly

On 25th Nov, I got a call for an HR stating that they would need to conduct another round to reach a verdict (Damn that second round).

4th: Coding

The interviewer introduced herself, her work and asked my introduction.
After that she asked me to find the no. of subarrays in an array to which i replied (n+1)C(2) where n is the size of the array.
Then she gave the full question.

Q1. Given an array find the no. of pairs of non-overlapping subarrays having elements greater the K.
With a little thinking, i proposed an O(n) solution
The solution involved breaking array into continous chunks of arrays that contain elements greater than K.
and then finding cross_pairs (the no. of pairs where the two sub arrays are from differenct chunks) this is trivial.
and finding same_pairs (the no. of pairs where the two sub arrays are from the same chunk). This required an O(n) pass.
and at each juncture 'i', add to the sum the no. of subarrays ending at i -> (i+1) and all subarrays that can be formed with the remaining elements in the chunk (for size n) (n - i)C(2).
I coded the soluion, dry ran it.
There were no bugs

She asked me to write space and time complexity.
She seemed pretty satisfied overall.

She asked me to ask her some question, i did.

This round was pretty great as well.

7/32 Candidates were shortlisted for the HR round to be held on Dec 1

5th: Googleyness

The person interviewing me was an HR.
He introduced himself. Asked me to introduce myself. aksed me to tell something that was not on my resume.
Asked me to describe a situation where i had different opinon with someone and how i resolved it.
He gave me a situation where a collegue want's to try a solution which I've already tried and failed at what will i do?
We also had a discussion about some otherthings that i do not remember.
He asked me to ask him a question

The round was 20-25 minutes. and went great.

Dec 1: The placement cell released the results 4/7 people got the offer, i was luck enough to be one of them.