Previous Education and Experience
Education: MS in CS from USA
Company: Amazon
Position: SDE I
Tenure: 2.5 years
Location: Seattle

Had to move back to India for some personal reasons and took a break from work for some time before I applied to MS. I initally applied to a few roles on the career site but didn't get any call back. HR randomly found me on LinkedIn and connected with me to interview for the current role which is not among the ones I applied for.

Round 0: (OA - Codility - 90 min):

1. Fix bugs in prewritten code without changing more than 4 lines.

   Don't remember the exact program but it was something simple like finding the maximum number in an array and it was failing edge cases. It was pretty easy to fix.

2. A variation of https://leetcode.com/problems/longest-happy-string/ - there were no cases provided by the OJ to test your code against but they said the code need not hit all cases, it's enough if it can pass a minimum threshold number of cases (maybe 50%).

   This is a greedy problem and because there were no test cases for reference it was a little tricky. I coded for happy path and a few edge cases and that seemed to have made it past the bar.

HR reached out to say I cleared the bar and scheduled the virtual interviews which would be 3 rounds and 1 hour was allocated for each (they gave me an option to choose all on one day or on different days, I chose different days as it wouldn't be as much mental load):

Round 1 (DSA/Problem Solving/Coding + Domain Knowledge Questions):

Coding Question:

1. https://leetcode.com/problems/shortest-palindrome/

   Solved it in O(n) time O(n) space by finding the longest palindrome that is a substring of the input starting with the first character, copy the rest of the string reverse and append to the beginning. This one was tricky as the OJ provided for interviewing - codility also had the ability to run the code and test for different cases. There were a couple of bugs which I fixed once I saw it wasn't passing all cases the interviewer provided. I did many coding interviews in my career but this was the first time the code I wrote was tested live against test cases in the interview which added an extra element of difficulty.

2. A minor variation of https://leetcode.com/problems/word-break/ - gave me number strings instead of alphabet strings.

   This threw me off intially and I suggested only a recursive solution, but after a few minutes noticed that it's a variation of the above problem and so suggested the DP approach. Was not required to code it due to time constraint.

Domain Knowledge:

1. Explain the Factory and Singleton Design Patterns, asked me different nuances and how to code different variations of Singleton - only correctly answered the Factory pattern portion, I didn't know many nuances of Singleton.
2. Can you ascertain if an API is REST API just by looking at the URL? - couldn't answer this either
3. How to run a Java program without a main method inside the class? - answered no but not sure if there is a way to do it
4. What happens if we provide the wrong signature for main method? - Answered that the class will compile but it won't treat the method named main as the main method of the class, which I think is correct

The interview was alloted for 1 hour and took up the whole hour as there was a quite a bit of stuff to get through

Round 2 (DSA/Problem Solving/Coding):

1. Not sure if this problem exists in Leetcode, I couldn't find it but if any of you do please leave a comment with the link and I'll add it in. Given a BST and an integer range (min, max) delete all nodes in it that do not fall in the range, need to do it by editing the input Tree and retaining the structure as much as you can and not by returning a new Tree.

   Initially suggested an iterative approach that does not work in some cases, then came up with recursive approach: Call the function recursively on left and right children, if node value is in range don't do anything, if not the if node value is less that min then return right child (because the right child could have some nodes that are in the range), if node value is greater than max then return left child. No need for helper as the main function itself returns a tree node. Took a minor hint at one point but solved it correctly in the end.

2. https://leetcode.com/problems/generate-parentheses/

   Standard backtracking question, coded it without much hassle. Code had a minor bug which the interviewer pointed out and I fixed it immediately.

The alloted time was 1 hour but interview took only 35 mins including time for asking the interviewer any questions about the Company. Felt this one was much smoother overall compared to Round 1.

Round 3 (System Design):

1. Started off with asking me about a project that I worked on recently

   I described a proxy recommendation system that I designed and built and there were some followups.

2. Design a Weather App, that let's you see the current tempurature, Air Quality Index and the forcasted weather type (rainy, cloudy, sunny) for the next week.

   Felt this was relatively easy compared to other SD problems out there like Design FB, Instagram, Whatsapp etc. They asked me to use any sketching software that I had (which I didn't so ended up using MS paint which is very basic, I advice others to have some sketching software available with them for interviews like this)

   Initially discussed a simple triangulating algorithm for the user's location and then sketched out a simple HLD with Load Balancers, servers, databases. The interviewer followed up with how to optimize the performance at which point I suggested we have a global cache that stores the most requested GPS coordinates for faster retrieval times. Later I also suggested that we could have data centers globally with caches for each location storing and serving only locations in the neighborhood of the datacenter location (this also serves as an efficient sharding strategy for the Database). Later they asked me about the schema for database, and I suggested NoSQL as we only store a simple key-value pair (location to temperature) and we can have indexes on the key for faster search times. Next question was about the eviction policy of the cache for which I suggested we use a combination of LRU and LFU. Final question was what would you do if the sensors/data gathering system went down, I said we could have an ML based predictive model for predicting the weather for the next hour/week. They asked me to suggest another approach if that also fails, at which point I couldn't give any answer. Overall this interview was also more or less smooth with me answering most of the questions within time. The interview lasted for 50 mins.

The HR took 2 weeks to reach out to me after this to schedule further rounds and I took another two weeks as I was down with a sickness.

Final Round (System Design + Past Experience):

System Design:

1. Asked me about a system I recently designed that I was proud of (gave the same answer as Round 3) and there were a lot of follow ups like how would you globalize this service to serve users across the globe who consume content in non-english languages.

   Suggested we use a third party API like Google translate to english translate content to local langauge (which many popular web services provide) or outsource translation to a local contractor.

2. Design a system that acts as middleman for multiple e-commerce websites and suggests things like best price for any product across all the e-commerce platforms.

   I delved into the security aspect first like systems for storing credit card information etc. Then went into HLD similar to Round 3, and then described a happy path solution and failure edge cases, like what to do if the failure happened between the customer and our system or if it happened between our system and the e-commerce vendor.

Past Experience Questions:

1. Name an instance where you made a design decision that influenced your whole team. Spoke of an example from work where I designed a Data structure for a custom object that we used to pass data around through multiple layers of tech stacks.

Both categories of questions were intersperced and were not sequential.

The early next morning I got an email from HR asking for more documentation and details about my current work situation, 10 days later they came back with an offer. Find compensation details here:
https://leetcode.com/discuss/compensation/1849884/microsoft-sde-2-l61-hyderabad-accepted/1309937