Here is the link.
Take my notes in the following:
Facts or arguments:
If you have not explained your approach, reached at right optimality and written code for 2 problems in a round, consider that interview as a doomed. No one will tell you this, but yes you are expected to do 2 questions flawlessly to get a HIRE verdict. Follow-ups may not be expected to be super correct but 2 questions must be coded and explained without their follow up variants. This comes from my extensive research and own experience.
My Background
- Final year student, B.Tech. CSE from a well known tier-2 college in India.
- Good amount of dev experience in Full Stack, Mobile and Embedded Linux.
- Internship in an AR hardware startup.
- Have an offer from a Unicorn Startup (Campus Placements).
- Decent academic record and did competitive coding for about an year (Not including LeetCode).
How I got the interview?
Recruiter approached me through email in the month of June (before my campus placements started) asked for fresh copy of my CV. Later in August I was contacted for a Google meet briefing and was told that I have been shortlisted for first round of Telephonic Interview, what's the process is going to be further and so on.
I don't know exact details of why I was approached by recruiter in the first place, but that could be due to Resume/LinkedIn profile/Kickstart performances. Try to maintain all three IMHO.
Preparation Style and Skill Level
At present and just before onsites, I had completed 607 questions with a split of 131 easy, 372 medium and 104 hard questions, Apart from this as I mentioned, I have some competitive coding experience of about 20-25 contests on Codeforces/Codechef.
My LeetCode contest rating is about 1800, with 25 contests so far.
Before telephonic rounds I had completed around a 500 questions. I don't remember the exact ratio of E:M:H but it was quite similar to what it is now.
My grinding intensified in first 3-4 months of lockdown, but I was more or less regular after that too.
The Telephonic Round
It was scheduled sometime around August end or September start.
I was asked 2 questions with follow up on 2nd question after some modifications.
First question was just a warmup, really easy implementation based. Second was a modified form of multisource parallel BFS. Kinda similar to Rotten Oranges, but with an element of parallelism involved where you had to run multisource BFS for two different sides (or lets say, two teams).
For this BFS question a matrix was provided initially, after I completed my solution he gave me a follow up that do we really need to pass a matrix to our function to solve this? He basically wanted an approach where you can only access matrix from an API and can't edit any cells.
Tip 1: This happens a lot in Google interviews, they want production level code from you in very first go actually. By production level I mean, use of APIs, proper abstractions and Iterator patterns (if problem involves iterating over some data). Using static variables or any other stuff like that will give nothing but wrong impression and will result in a NO-HIRE verdict irrespective of the fact that you were able to solve problem or not.
Tip 2: Follow ups in Google interviews are much more common than any other firms (or for those which I have interviewed with). You should keep that in mind that solving the initial question alone will almost never be enough and a follow up is waiting for you surely.
This round went well, I was able to solve everything nicely.
Recruiter called few days later and gave me my feedback. Although it was a green signal for on-sites, review wasn't really what I was expecting.
Review for Telephonic Interview
They said although my thinking and algorithmic skills were fine, I had done few syntax errors on the way. And even though I was able to rectify my code at the time of dry run or debug phase, It's not expected to be like that and should be perfect on the first go.
Yes you heard me right, They knit pick everything and why won't they. When you have a huge pool of talented applicants, things like these happen. So make sure you keep your mind and eyes open at all the times as this almost costed me onsites.
Onsites
Initially onsites were supposed to happen the very next week but my new point of contact advised me to take as much time as I needed for preparation as there will be a 9 month cool-down if I get rejected now. I then asked for 2 weeks time and he was okay with it.
For those who don't know, for onsites Google has 5 total rounds. 4 tech interviews, 1 Googlyness round.
Timeline: 3 tech rounds on one day, and remaining 1 tech + Googlyness round on some other day only if review is positive from first three rounds.
Onsite Interview 1
Question 1
Given an array A, where A[i] = j denotes the fact that player j finished the race before player i, and for the winner of race let's say player k, A[k]=-1. You need to print the order of the positions of players after race finishes Follow up: What if the data (array A) got courrupted, how will you take care of that. Return -1 if there data is courrupted and order of player otherwise.Pretty easy warmup question. First version of the problem is pretty easy, just create an inverse mapping of array values and index and everything else is basically clear.
For the second part I suggested that we can visualize this mapping as a dependency graph and then apply topological sort on it. If there is an error like cycle etc, it will be detected.
He looked satisfied with this approach however I could clearly see that he knows that there exists a simple solution for this. My hunch is that this includes some kind a case work to enumerate all the possible error cases. Topological sort just felt natural to me at the moment.
Question 2
This was a hard one for me. As a matter of fact this problem appeared in a contest very next day of my interview.
Window Queries Problem.
Idea here is a tricky modification of merge intervals and sliding window.This is in fact a classic example of how Google interview questions are like, they are hardly ever about a hard CS concept, an algo or a fancy DS. But they are all about observation and application.
I came close to solving this problem, finally gave right idea but at that point only 5 minutes were remaining so he asked me to code just the brute force solution.
Before I forget, I would like to add that no matter what anyone says, If you have not explained your approach, reached at right optimality and written code for 2 problems in a round, consider that interview as a doomed. No one will tell you this, but yes you are expected to do 2 questions flawlessly to get a HIRE verdict. Follow-ups may not be expected to be super correct but 2 questions must be coded and explained without their follow up variants. This comes from my extensive research and own experience.
Onsite Interview 2
This was 30 minutes after the first one.
Okay this was one of my worst interview performances ever, primarily because of bad taste from first interview as a result of not being able to code 2nd problem.
Given an array A, and the Q queries with each query having an integer K,
Return an interval A[i:j] that minimizes the following expression for each query/given K
| sum(A[i:j])-K |
Quickly gave a sub optimal, improved brute force solution involving prefix sums to calculate all the possible sum values of intervals, use a hashmap of these sum->intervals and binary search over keys of the hashmap to find value nearest to K
She needed a better approach. I should have given up, but I did a pretty bad thing, went on to try a wrong idea without thoroughly exploring it and checking it for correctness, so in middle of it I realize that its wrong and finally went with sub optimal solution. This interview was bombed for sure.
Here people have discussed a nice approach to this problem.
Onsite Interview 3
This was an enjoyable interview, but then again I was able to do only one question, actually the interviewer kept modifying it so you can say it was one questions with a lot of follow ups.
The question was exactly the same - Maximum Points You Can Obtain from Cards
Without wasting anytime I threw a DP solution with code, O(NK). He asked if I could do any better. I was confused at first, and reason for that is my skillset/background. I have solved problems on OJs, and not given many interviews. For me a problem like this screems dynamic programming if you have not given me any constarints to start with. And that is how situation was at that point. Immediate idea was to try my greedy hypothesis, and that failed as expected. Over next 5 minutes I came up with some micro optimization on DP solution but he finally said that linear time is possible and I should think in that direction. He said my core idea was right, but one insight is missing. This hint was enough and I came up with expeted approach. He asked me to code it, went over it and did some more micro optimizations.
Then he asked some follow ups.
Overall this was a good interview but I knew that even this one is practically screwed as I took alot of time in supposedly warmup variant of this question.
Tip 3: Interviewers will be happy to provide you with hints when you are stuck but keep in mind that every hint is a -10 points on your score cards in reality.
Onsites Review
Immediately after this final interview I had chat with my recruiter. She shared review and as expected overall it was not positive. Feedback stated that my coding style was nice, it was clean and upto the standard but my algorithmic skills were not up to the mark.
Well ofcourse I was sad, questioned my abilities and luck as any normal human being would do. But I accepted verdict nicely. For the next several days I went on to see what I missed in my preparation and what went wrong.
So here is what I lacked.
What went wrong/missing?
If you open up LinkedIn and see most of new grad or L3 engineers at Google India, you will find one thing common. All of them have extensive Competitve Coding profiles. Many of them are Candidate Masters or even Masters at codeforces.
In a country which produces millions of software engineers a year, competition is bound to be tough. We in India are at a point where competitve coding is compulsory to get a job and not a mind sport anymore.
So yes, a hardcore competitve coding experience was missing from my profile but that is not the only reason I failed, it was something else, it had something to do with my style of preparation.
- Most of my preparation was focussed on getting a campus placement and not an offcampus job. Oncampus placements have only one hurdle, online assessment. Once you clear OA, rest of the interviews are damn easy. But here in campus drives, OAs are focused on DS/Concept heavy questions for example having knowledge of articulation points, Bell's numbers and DP with bitmasking.
- This is quite opposite to Google interviews which are all ad-hoc, and logic focused
- I am now quite good with all these fancy DPs and complicated algorithms. But I suck at greedy problems.
- Even knowing that I lack ability to crack greedy/constructive problems, I ignored it (There is less chance that a non classic greedy problem would appear in any OA, and classic greedy problems I have got covered)
- Leetcode contests are helpful, but these days they are not, atleast for India. The easy first problems are sometimes about string formatting or running a loop, this will never appear in any companie's recruitments in India. The other problems at last are almost 3x difficulty of first two sometimes and hence whole contest becomes imbalanced.
So how will I prepare now?
Having seen that recruitment at Google requires alot that I dont have, a smart thing would be to work on that.
For the time being I will shift to websites like Binary Search and AtCoder where problem statements are short and don't require pointless mathematics that codeforces/codechef requires and at the same time helps in building good reasoning and logic.
I would still give weekly contests here, and hope they improve and become balanced.
Word of suggestion to LeetCode
There is a great need of content that is India focused, level of interviews here is just a little harder than west world. Maybe leetcode-in or something like that would be helpful as I am sure there is a huge Indian traffic on this site.
PS: Thanks LeetCode for the job offer I have right now, It might not be sufficient but for sure is a neccessary resource for coding interviews :).
Word of advice to New-Grads aspiring for Google
Stop wasting time in anything else you are doing right now, start today because when this interview chance knocks on your door, you might not be ready and wished you had started training a year earlier.
Extensive competive coding experience + lesser dev experience is often better that lesser competitve coding experience and more dev experience atleast for freshers.
Feel free to comment if you agree/disagree with my thoughts. Also if you have any better approaches for any of the above problems, please share. Thankyou
No comments:
Post a Comment