Round 1
Questions:
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?
Candidate's Approach
- Was able to complete code for both original and follow up questions.
- For each point in the matrix, checked the water usage for that particular 3x3 submatrix and took the minimum of that.
- Time Complexity: O(mn).
- For the follow-up, used the prefix sum on the matrix.
- Time Complexity: O(mn).
Interviewer's Feedback
No feedback provided.
Round 2
Questions: I was able to find the exact same question on Leetcode after the interview. It's a LC Hard question 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.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 3
Questions:
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 an infinite number of CPUs and we need to complete the jobs in the minimum possible time? What is the minimum number of CPUs required?
Candidate's Approach
- Simply sort the jobs and take the jobs in the order they are coming in. Scheduled each job on the CPU which is getting free earliest. Since each job is taking constant time, the CPU on which we scheduled the job the earliest will get free. Time Complexity: O(n log n).
- Used a minHeap to track the CPU which is getting free in the minimum time. Time Complexity is still O(n log n).
- Minimum time to complete jobs = Latest Timestamp for any job + duration of that job. 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 out whether the job will be completing in minimum time with x CPUs or not. Time Complexity: O(n log n).
- Completed all three with code for this round, and the interviewer gave a lot of hints to guide me in the correct direction.
Interviewer's Feedback
No feedback provided.
Round 4
Questions:
It was also a LC Hard question. Something similar to this: Meeting Rooms III, but with the modification that we don’t know the exact number of rooms. 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.
Candidate's Approach
- Was able to complete the code and within the time limit.
Interviewer's Feedback
No feedback provided.