Round 1 - Coding and Algo
Duration - 1 hr
Given a sorted array with duplicates and a number, find the range in the form of (startIndex, endIndex) of that number.
::> Gave O(logn) approach
Same as this question -
https://leetcode.com/discuss/interview-question/125018/Amazon-interview-question-Add-Interval
::> I gave O(n) approach since we were running out of time. Although, I think we can save solve it mor efficiently using segment tree.
Round 2 - Coding and Algo
Duration - 1 hr
Given two sorted lists of positive integers, find out the first k pairs with the smallest product. Each pair contains one number from each lists.
::> Gave O(klogn) approach with priority queue.
https://leetcode.com/problems/all-oone-data-structure/
::> Solved using DLL.
Round 3 - Software Design and architecture
Duration - 1 hr
Design misspelled word detector to be used in word processors. Also, how can we provide suggestions.
::> As you may have already realised, the architecture for this isn't very hifi. But, i think interviewer wanted to discuss various topics like load balancer, consistent hashing, caching, handling of frequently used words, API design, microservice, etc used in the design.
::> Suggestions part didn't very well for me, though I gave the high level approach. For those who are curious, edit distance is the answer.
Round 5 - Technical Communication
Duration - 1 hr
It was discussion on my previous experience and past projects. We mainly deep dived on what systems I have worked on, my specific contributions, some of my design decisions, what could I have done better, etc.
Round 3 - Host Manager
Duration - 45 min
It was a discussion on previous experience, past projects, expectations, why moving out and other usual HM questions.
Interviewer also asked to design "people you may know feature". Not the e2e design, but the high level idea and how would I calculate the required information.
::> For those who are curious, I included following points in my answer:
1. Generate tags for users based on their education, experience, interests, activity, etc.
2. Run ML algorithms to find similar users based on the tags.
3. Sort the users based on the similarity score found.
4. All this should be pre-processed.
Overall
All the interviewers seemed friendly and engaging.
HR experience was also good.
Didn't like the work of the team I was being offered the role for.
Also, linkedin is going to be doing infra migration to azure for next few years. (we all know why :p)