Recently I got the chance to get interviewed by Google. I applied directly on the career portal and post that the recruiter reached out to me. I was given 1 month to prepare for the same.
Round 1 : Screening round 1
It started with a brief introduction and then the panelist jumped to the question. I have already added a post for the same https://leetcode.com/discuss/interview-question/4978447/google-coding-interview-experience
There were slight mis-communication where the interview didn't asked for something but it was expected from my end, which was to further optimize the solution. The recuirter mentioned that the feedback was not negative so I can have another round or I can reapply after the cooling period. I asked for another round.
Feedback: Neither positive nor negative
Round 2 : Screening round 2
Gven set of points in a X-Y plane representing rectangles, find a vertical line which divides the plane into two halfs of equal areas.
NOTE:
- Given rectangles can overlap with each other
- The veritical line can pass through the rectangles
It was an open ended question and things were expected to get clarified by asking questions. I pictured out the question as shown below
It was challenging to come out with an approach. Eventually I was able to solve the question using Binary Search and the interviwer was happy with the solution.
I have added the solution here : https://leetcode.com/discuss/interview-question/5587195/Google-interview-experience-or-Screening-round
After few days I got the call from the recruiter that I have cleared the screening round and they want to proceed with the onsite rounds.
Feedback: positive
The onsite rounds were scheduled after 2 weeks.
Round 3: Onsite round 1
It started with a brief introduction and then the interviewer posted the problem.
Given an array of numbers, find all the subarrays which are forming good arithmetic sequence(AP).A good arithmetic sequence is a sequence of numbers having common difference equals to -1 or 1.
E.g {1,2,3} and {3,2,1} are good arithmethic sequence with common difference 1 & -1 respectively.
I came up with a brute force solution. The interviewer asked me to further optimize the solution. I was able to come up with an O(n) soliution and the interviewer was happy with the solution.
Further, I was asked to write the use cases for unit testing the same code.
Feedback: positive
Round 4: Onsite round 2
It started with a brief introduction and then the interviewer posted the problem. (I have tried to frame the question from the things I was able to recall)
There is a class given which has below APIs available.
- countWords()
- isTaskCompeleted()
The API countWords()s blocking in nature and need not imply that the job is done. The other API - isTaskCompeleted() tells whether the job is actually completed or not.
A task is represented as the number of words in a given document. There are N machines present where the job can be scheduled. Implement a method which is responsible to schedule jobs on these machines. (1 machine can handle 1 job at a time)
NOTES:
- Make sure scheduling is correct among all the machines.
- Make sure to optimize the time for the jobs to be completed.
- Make sure to use the available APIs minimal number of times (as they are blocking calls).
I used the round robin mechanism to schedule the tasks on different machines. Also, used queue to keep track of the next available machine. Also, added a method to check whether the job on the machine got completed or not( by using the given APIs ) to maintain the free pool machine list.
The interviewer asked follow up questions on the same to optimize the solution and also tweaked the question little bit to check how am I going to solve the scenario.
Feedback: positive
Round 5: Onsite round 3
Design a music playlist shuffler (music are represented as array of anything(can be integer, string, etc))
- It should always return a random music.
- The returned music should not be returned again for the next K plays.
Randomness was expected similar to what rand() method provide in C++. I came up a solution using a Queue having time complexity of O(n) and space complexity of O(n).
The interviewer asked me to furhter optimize the same. I was able to come up a O(1) solution having O(K) space complexity.
Further, I was asked to write the use cases for unit testing the same code.
Feedback: positive
Round 6: Googlyness
It was a very short round. I was asked about my current role and some team based questions like
- How would you build a team?
- You are being appointed as a manager of an underperforming team, how would you handle the team and what will be your approach to increase the efficiency of the team?
- How would you resolve a conflict within a team?
After 1 week I got the call from recruiter mentioning that feedback of all rounds have came in and they would like to proceed with the application. The next step was to connect with a manager for team matching round.
Round 7: Team matching
It started with brief introduction about self which then moved to the current role in the company, the job that I am responsible for, why am I looking for a change.
Then 1 HLD problem was asked to see how I approach the problem. Only high level flow was expected. There were few hiccups here when the manager asked particular question about the solution I came up with but overall the discussion went well.
Finally, the manager briefed about the current team and roles & responsibilities.
Feedback: That the manager is okay and we can proceed with the application.
Now this is where things started to get in the wrong direction. I got the call from the recruiter mentioning that there seems to be an issue with the eligibility criteria for the job I applied to. This was mainly towards the YOE I was having. I was having experience of 2 years & 10 months and the recruiter mentioned that the eligibility criteria has now become very strict and they can't proceed with the application if its not having 3 years of experience. To be honest, all my expectations were shattered & I lost hope here.
I was being asked whether I will be willing to wait for 2 months or not. I specifically asked what is going to happen after 2 months and got to know that the application will be resumed post 2 months and then the final verdict will be decided.
I got the call after 1 & half months saying that they want to have another round to proceed with the application.
Round 8: Extended round
Same as previous rounds, the interviewer started with a brief intro and jumped on to the question. He specifically mentioned that he is not looking for the implementation and only for the approach on the question.
I was being asked to design a library to solve a boolean expression and return whether the boolean expression can be evaluated to TRUE or not in any case.
E.g:
- ( (a || b ) && c ) : The expression will evaluate for TRUE when value for c is TRUE and any one of a & b is TRUE.
- a && ~a : This expression can never be evaluated to TRUE.
The expectations were:
- How would a person who doesn't know how to code the underlying logic & only good with Maths going to use the Library to get the desired result ?
- How the input should be ?
- How the libarary will be invoked ?
- which data structures are going to be used & why (need to be cautious about the space & time complexity) ?
- Can you write the associated Classes & APIs for the same (only declarations) ?
- Can you code the final logic on how the expression will be evaluated ? ( we can assume we have helper APIs available to check for format & errors)
- What is the expected space & time complexity of the algorithm for part 6?
I wrote the associated Classes, APIs, and the expression evaluation logic. Since, the question asked for all the possible scenarios where the expression can evaluate to true, we had to proced with 2^n approach where each variable can have 2 possible values (0 & 1) and there are N number of variables in a given expression.
The discussion went well and the interviewer looked happy with the solution.
Again, the process took a hit and I was being asked to wait until further communication.
I got a call from recruiter after 1 month and the verdict was that the feeback on the Extended round didn't went well and they can't proceed with the application.
Overall the process took around 6 months. I wanted to keep my focus intact & hence, I didn't applied to any other jobs (I now realize that it turned out to be a mistake). I was so determined and confident after all the rounds, but the final decision didn't go in my favor. Post this, I am trying to get over with this and hopefully I should be able to land a job with good offer soon :-) .
I had thought of writing this post after getting selected, but it's okay; I won't give up and will come back stronger.