Phone Screening Round :
The interviewer asked about a quick introduction of myself. She asked basic questions about my role and my current organization and what was my contribution in the current team that I was a part of.
Question 1 : Given a CPU schedule with starting & ending time of processes. This schedule is used by the server to run the processes. When a new process comes into the scheduler, it is first checked with this scheduler if it can be accommodated or not.
You have to return a boolean value if the incoming process can be accommodated into the process schedule or not. If it can be accommodated, then the scheduler has to be updated with the new process being a part of the schedule and if not then return false.
Note : The time is given as a string input and is military time. (00:00-23:59)
Input :
schedule : [[“10:00”,”11:00”],[“14:00”,”16:00”],[“23:00”,”23:30”]]
incomingProcesses : [[“11:00”,”11:30”],[“12:00”:”15:00”],[“11:15”,”13:43”],[“17:00”,”18:40”]]
Output : [true, false, false, true]
Explanation :
11:00 - 11:30 can be accommodated by the processor hence it is added as a part of the scheduler.
12:00 - 15:00 cannot be accommodated as a process is already starting at 12:00 therefore a clash will happen.
Since 11:00-11:30 is a part of the scheduler, 11:15-13:43 will clash.
17:00 - 18:40 can be accommodated as a part of the scheduler.
Follow up question : How will you handle the case if multiple cores of CPU are in present?
After a week from the day I gave my phone screening round, they wanted to take my virtual on site interview. I was given with a list of dates from which I could choose the date. I decided to take two weeks to prepare.
I was a little bummed out with the fact that I will not be able to get the on-campus experience.
Day 1 :
Virtual Onsite Round 1 :
The interviewer straight up jumped to the question. I was first asked if I was aware of what a complete binary tree is, although I knew it was I decided to listen from my interviewer about it once again.
He explained to me what a complete binary tree is and then asked the question as mentioned below.
Question 1 : Given a complete binary tree, write a function to add a new node to it.
( Assumption : since it was an open ended question I first asked if the given Tree is always going to be a complete binary tree, and then what will be the structure of the TreeNode and a few more questions, after I cleared myself with all such doubts, I discussed a few approaches with my interviewer and then I wrote the code for the problem. )
I wasn’t asked any follow up question in this round.
Virtual Onsite Round 2 :
The interviewer followed a similar pattern and jumped straight to the problem statement as he wanted me to utilise all the 45 minutes to solve the problem.
Question 2 : Write a program that takes a map of a maze as input and outputs the length of the longest path from the top to the bottom.
Conditions and constraints:
- The map is a two-dimensional, rectangular board.
- You can only visit each cell once.
- You are not allowed to go up, only left, right or down.
- You can start on any cell at the top row that is not a wall.
- You can exit on any cell at the bottom row that is not a wall.
Examples: (“.” is empty space, “#" is a wall)
Input = tuple([
"..",
".."])
Output = 4
Input = tuple([
"#.#..#",
"#.#..#",
"#.##.#",
"#..#.#",
"#..#.#",
"#..#.#",
])
Output = 9
I wasn’t asked any follow up question to this as well, because I utilized all my time in answering this question itself.
After giving these two rounds, I didn’t get any response from the recruiter and I started reading all the articles about rejection from Google. I knew that my second round didn’t go well as it was expected. After waiting for about two weeks, I finally got a call from my recruiter that they had decided to move forward with my application but because of my second round they wanted to conduct another round to test my technical skills. I was more than excited after hearing that.
I asked my recruiter to give me time for two more weeks to prepare and I started going through all the topics which I felt were important.
Day 2 :
On this day I was supposed to have 3 rounds (1 GnL + 2 tech rounds)
Googlyness Round : The interviewer explained to me about the round and started asking me all sorts of questions about my past experiences and my contribution in the project. He was interested only in the behavioral aspect of me. So I suggest to all the candidates that please be thorough about the projects that you have worked on. I was put in difficult situations but I managed to answer all the questions with my past experience and I was honest with all my answers. This round went on for 45 minutes as well. After this round, the interviewer wished me good luck for the coming tech rounds and ended the call.
Virtual Onsite Round 3 :
Question 1 : Given a complete binary tree and an index (ind), return if the complete binary tree has that index present in it or not. All the nodes in the complete binary tree are indexed as 1,2,3,4 and so on.
Example : Tree - A (The nodes are indexed as shown in the diagram)
Input: TreeNodeA, index = 12 (Consider the root of the tree as shown above.)
Output: False
Input: TreeNodeA, index = 7
Output: True
I discussed about 3 approaches and I came with an approach with a complexity of O(logn).
Follow up question : Using the function to check the index, find out the size of the tree.
Virtual Onsite Round 4:
Question 1 : We would like to design an alerting system for a server. The input to the system is error rates of the server over time.
For example, 5, 10, 7, 15, 0, 60, 55, 60, 60, 60, 0, 5, 5 will be interpreted as the server having error rate of 5% during the 1st second, 10% during the 2nd second, 7% during the 3rd second, and so on. We would like to know if the server was unhealthy at a given time p.
Please write a program that returns True iff there is an interval of s seconds that includes p and during which the error rate is never below r. The input consists of an array of error rates, and the values for p, s and r.
I gave a simple O(n) solution to this problem and the interviewer made me write the code for the same.
Follow up question: Instead of giving you s and r, you are given a threshold t. Your program should return True iff there is an interval for which s * r >= t
(i.e. we tolerate very short bursts of high error rates or long periods of very low error rates).
The input consists of an array of error rates and t. We want to see if there was any time when the server was unhealthy (i.e. p is not given). The input consists of an array of error rates and t, looking for an element which is lesser than r.
This was a very tricky follow up, I took about 10 minutes to fully understand what the question was asking for and once I did, I gave a O(n^2) solution to the problem. The interviewer asked me to code the problem statement and after it’s completion the interviewer asked me if I could improve the time complexity of my code. After reiterating through my approach I was able to think in a direction which was improving the time complexity. The interviewer gave me a hint to use another data structure. As soon as he said that, I was able to come up with the answer with a time complexity of to O(n) and I was able to code it as well.
My take from the interview
I was really happy with all the rounds that I gave and I was really hoping for a positive feedback.
After a couple of days I got a call from the recruiter and she informed me that it was a close call and the hiring committee has decided not to continue with my application this time. The reason that they gave was efficacy which was a little disappointing to me, but I will definitely consider this a constructive criticism and look forward to practice even harder this time.
My advice to all my fellow leet-coders out there would be to not to get disheartened on failures. It's okay to fail but one should always learn from the mistakes and not give up. Work hard everyday to get better and you will definitely achieve your dream.
All the best! :)