Background:

• Education: Masters from Tier-1(IIT/NIT/IIIT)
• Years of Experience: 2.2 Years
• Prior Experience: 1 years at a MNC, rest Microsoft
• Was having very sour realtionship with my manager and my team member(only), so had to move out.

One of my linkedin connections liked a post, which said "My team is hiring in Bnagalore". Previously I got referrals from Amazon, but somehow wasn't getting a call. It wasn't really referral for his/her own team (I thought I was blocked from Amazon, lol). Sent that guy connection, pinged him for referral, shared resume and he referred me.

Online Round

Got Hackerrank link for the test. It was 90 mins test.

• Q1: Grid based BFS question. Source, Target, Some objective to fulfil (don't remember exact question, sorry).
  • Approach: BFS using queue.
  • Complexity: O(N*M).
• Q2: Given N points on 2D plane and a source point. Give K nearest points, consider distance as Euclidean or Manhattan (any one of them) distance.
  • Approach: Use priority queue to keep nearest K points. Once a new point comes, check if it is potential nearest one, then keep it in the PQ and remove the farthest one.
  • Complexity: O(NlogK), can be done using sorting the distance in O(NlogN).
• Had to explain the approach with detailed analysis, Try to write using simple english languages without using much code.

Few days later got email saying that I cleared online round, they don't have any dates on September, they'll get back to me once they have dates. I was travelling from Bangalore to my hometown in last week of Sept, so asked recruiter not to consider that weekend. On the Tuesday evening she called me up to tell they have dates on that very Saturday and whether I am interested or not. I initally said no, later called her up to schedule the interview. I took the risk to take the interview since I needed the job badly(MS was unbearable for me, it was affecting me mentally), since I was moving out I hardly had any time to prepare for onsite till Thursday.

Virtual Onsite Round

Round 1

Interviewer were very upfront saying we will discuss 2 questions in 45-50 mins. Last 10 mins for for any questions ( read they'll ask LP questions ).

• Houses are arranged as tree. ith house had fire and at each minute fire propagates to it's neighbours (bothways). After nth minute print all the houses that will be on fire.

  • Approach: Little bit modified tree traversal
  • Complexity: O(N)

• 1209. Remove All Adjacent Duplicates in String II

  • Complexity: O(N)

LP Questions

• Any challanges you faced, how did you overcome it?
• For any technical challanges you faced, how would you handle it?
• Any dive deep situations, any findings from that? How did you fix the bug from that dive deep scenario.

Round 2

Same as last round, 2 questions will be discussed interviewer told me at the very beginning.

• N chocolate boxes are there initially. Each time you eat a chocolate from the ith box, that box gets filled up with floor(c_i/2) no of chocolates. You can have one chocolate box in 1 minute. Maximize the no of chocolates you can have in A mins. Since, she was very new interviewer. Even though I already solved this questions in 7-10 mins, she continued discussing this question some silly things just to allot this question first 25 mins, which could've been helpful for me for the next question.

  • Approach: Maintain priority queue(max heap) and keep eating top element.
  • Complexity: O(NlogN)

• relationship(a,b) defines a and b are friends. If a->b are friends and b->c are friends, then a->c are friends as well. Given q queries, check if x and y are friends or not.

  • Approach: Intially I discussed brute force and BFS kind of approach. Later I proposed DSU with path compression(that took almost 10 mins of discussion). It was difficult to write up complete DSU code from the scratch and later do a dry run on a given example and also make her realize how path compression is helping to reduce complexity.
  • Complexity O(N+Q), can be done using BFS+Indexing in O(Q) (don't know why it didn't click that time, I even discussed using BFS -_- Duh!)

LP Questions

• Any time you move ahead did something extra.
• Any time you did something better to add some values.

Round 3

Recruiter told me earlier, that if my performance are good enough, then I will have 3rd round on the same day as well. I didn't have a proper setup(everything shifted to my hometown due to movement) to give an interview. This round was the mangerial round and was scheduled around 6:30PM in the evening. Interviewer was really nice and friendly. He intially thanked and apologized for scheduling such a hectic interview schedule on weekend.

• Lots of situational based LP questions. We almost discussed for good 20 mins.
• 277. Find the Celebrity , Never solved this one before, so needed a hint from his side to solve in O(N).
  I wasn't even sure after this round that I will get selected, because we wrapped up within 40-45 mins. I wasn't sure it was because of weekend, IPL beginning or I was hopeless :p.

I got a call on Monday evening saying, I cleared all the rounds and I will have my last round on Thursday on 9AM. That was my last week on Bangalore and I was staying with one of my friends, because I had no amenities in my flat. So woke that guy, kick him out of his room (Sorry bro :P ) and had my last interview.

Round 4

• Why leave MS? Quite lengthy discussion on this topic.

• Give me an example where manager said it was okay, but you were not satisfied with the result and move ahead to did something extra.

• Snakes and Ladders very higher level API/system design.

Finally got the call on next Monday that I got selected and it was such a relief for me. Later we negotiated on compensation and now just serving my notice period in MS.

Some tips:

• Be very much prepared with LP, I was more scared about LP questions, then DS/Algo questions. Had some background with CP and been doing Leetcode for the last few months.
• 283 Solved - Easy 88 Medium 166 Hard 29