Hi All,
I recently appeared for Google interviews and wanted to share my interview experience and the entire process. I didn't have to go through the phone screening round as the recruiter told me that some HM is interested in my profile and he/she wanted to fasttrack the process. So, below are the questions that were asked to me during the actual coding rounds.
Round 1:
The farmer owns an N by M meter field and is facing financial challenges. He's considering selling most of the field but wants to keep a 3x3 section while conserving water usage. Each 1x1 plot needs a specific amount of water. Your task is to identify the optimal 3x3 slot for him, considering water efficiency.
Follow up : Now if have to identify a (x,y) sized subplot. What will you change?
- Was able to complete code for both original and follow up questions. For each point in matrix just check what is the usage for that particular 3x3 submatrix and take minimum of that. TC - O(mn). For follow up we have to use the prefix sum on the matrix, TC-O(mn).
Expecting a Hire/Strong Hire
Round 2:
I was able to find the exact same question on leetcode after the interview. Its a LC Hard question https://leetcode.com/problems/time-taken-to-cross-the-door. This seemed easy enough during the interview but had a lot of if-else clauses. In the end, I couldn't complete the code.
Expecting a No Hire or a Lean Hire in the best case for this round.
Round 3:
We have N jobs and C cpus. Each job is specified by startTime and takes a constant time S to complete. What is the minimum time needed to complete all the jobs.
Follow up 1 - If each job takes variable amount of time to complete, then what will we update.
Follow up 2 - What if we have infinite number of CPUs and we need to complete the jobs in the minimum possible time. What is the minimum number of CPUs required.
Answer Approach -
- Simply sort the jobs and take the jobs in the order they are coming in. We can schedule each job on the CPU which is getting free earliest. And since each job is taking constant time, the CPU on which we scheduled the job the earliest will get free. TC (nlog n)
- Use a minHeap to track the CPU which is getting free in the minimum time. TC is still O(nlog n)
- Minimum time to complete jobs = Latest Timestamp for any job+duration of that job. And max #cpus can be equal to the number of jobs and min cpu can be 1, used Binary Search and applied the same logic as 1 to figure our whether job will be completeing in minimum time with x cpus or not. TC(nlog n)
- Completed all the three with code for this round, and the interviewer gave a lot of hints as well to guide me in the correct direction. Expecting a Hire for this round.
Since I had messed up one round, I was expecting a rejection but after some time the recruiter informed me that I had messed up one round and the feedback from the other two rounds was good (He didn't tell me the exact rating). And that I need to go through one additional round in order to progress on the application. So, I went into preparation mode again for one week. So, here comes the final round.
Round 4
It was also a LC Hard question. Something similar to this: https://leetcode.com/problems/meeting-rooms-iii/description/
But with the modification that we don't know the exact number of rooms. And we needed to return the minimum number of rooms needed to complete all meetings and also return the mapping of which meeting was held in which room.
No Follow ups. I was able to complete the code and within the time limit
Expecting a Hire from this round.
Thanks to this community, I got a lot of new problems to work on. Trying to return a small favour.