Y.O.E : 4.5 years
Current Job: Non FAANG
Study: Masters from top university in country
Recruiter reached out me on LinkedIn (although I am not very active there). I scheduled some time with him. We discussed for half hour about my current job, roles & responsibilities. He scheduled phone interview after that. I had around 1 week of time to prepare.
Phone Interview:
- https://leetcode.com/problems/nested-list-weight-sum/
I had seen this question earlier, so answered & coded quickly. Important thing here is, interviewer will not provide any starting code. We have to come up with input & output structure. It took me few second to write input class to represent nested list. - https://leetcode.com/problems/leftmost-column-with-at-least-a-one/
Again I had seen this problem. But provided the O(N.log(N)) solution first (binary search on each row). After that provided O(N) solution. Coded both solution.
Because of Covid-19, virtual interview was setup. I had 1.5 month to prepare.
Round 1 - Coding:
-
https://leetcode.com/problems/valid-palindrome-ii/
I had seen this question so coded it quickly.
Follow up: https://leetcode.com/problems/valid-palindrome-iii/
I had to change same code and make it work. I provided O(N^2 K) solution, where dp will store boolean values. Missed the trick of storing actual modifications for the substring. -
Problem: We have room with multiple jewelry present. We want place camera in one of the corner such that it covers most jewelry. Camera has fix range of angle it can cover.
Doubts I clarified -> Room is 2D. Room is rectangular. We know fixed positions of all jewelry.
I went complete blank, and couldn't think how to procced. I represented room as binary matrix, with jewelry as 1. Interviewer gave hint that there is better way to represent it.
O(N^2) approach -> Fix one corner, say bottom-left. For each jewelry, consider its angle as starting angle, find all jewelry fits into angle range. Do this for each corner.
O(N.log(N)) approach -> Fix one corner. Transform jewelry data to list of sorted angles. Using sliding window approach find best angle. Do it for each corner.
I came up with O(N.log(N)) solution when only 4-5 minutes were left. So couldn't write code for it at all.
Round 2 - System Design:
Problem: We have 10K machines, we can use it however we want. We want download entire wikipedia.
I provided the similar design as web crawler.
-
Tasks will be distributed based on hash of URL, so we can map URL to one of the machine.
-
Each machine will have listening process. It will get URL as input.
-
After getting URL, it will check for duplication.
-
it will download data, and store in the file system. File location can be same as URL pattern.
-
It will look for new URLs in the downloaded data. And send the URLs to possibly other machines (based on hash).
-
To start the whole process, we will have seed URLs. One of the machine will act as driver, it will compute hash of seed URLs and send it appropriate machine.
I think this is the round which gave me rejection. I lost the control of conversation. I talked few things, and interviewer started asking questions on that. So I was drawing the things (on virtual board) that I already talked, and replying to interviewer simultaneously. So couldn't keep focus on one thing. 45 minutes got over way fast than I can imagine.
Round 3 - Motivation:
Usual questions around conflict management, and challenging projects. Even though I prepared specific examples to discuss, it looked like it didn't impress interviewer much.
Round 4 - Coding:
- https://leetcode.com/problems/product-of-array-except-self/
- https://leetcode.com/problems/find-all-anagrams-in-a-string/
Coded both questions in time.
After one week from interview I got rejection email. I didn't schedule the feedback call with recruiter, I was certain that system design gave me rejection.