Amazon Interview Experience for SDE-II (Virtual Rounds)

Amazon Interview Experience for SDE-II (Virtual Rounds)I got a call from an Amazon recruiter as I was referred by one of my friends for the role. She sent me the coding test link which I had to complete within a week. Once I completed the test, I got a call to schedule the interviews in two weeks. 3 interviews were held on Amazon Chime as per schedule. Post that after 4-5 days, the hr informed me that they would like to proceed with the final bar raiser round, which happened in a couple of days. Following are the questions that were asked:Online Round (Coding Test – 90 mins)We are given the costs of a list of pants, shirts, shoes, skirts. We have a certain amount of cash with us, we need to determine the total number of possible combinations which we can buy given that we must buy one and only one of each type.Eg: pants=[3, 5, 7], shirts = [4, 7, 8],
skirts = [5, 8], shoes = [3], budget = 25So in the above e.g., apart from the combination [7, 8, 8, 3], all others are possible.Hint: Since we have to buy all, we can combine the first two lists and the last two lists, so we would have cost lists like pants_shirts = […] and skirts_shoes = […], now we can just iterate over one list and binary search the remaining amount over the other list and add accordingly.It was quite trivial so don’t remember exactly.Round 1:The interviewer gave his introduction, asked me a bit on the kind of projects I’ve worked on. Then he started with a data structure problem.Given a binary tree with the following TreeNode, create a copy of the tree without using any extra space. TreeNode{
left*, right*, random*, val
}My solution: I first told a hashmap solution where I would maintain a mapping from the original node to the copy node in the new tree, and in the second traversal, I would be able to assign the random pointers as well. The interviewer agreed that this would work, but he wanted me to do this without the hashmap. It took me around 15-20 more mins to come up with the final code. I first appended the duplicate node to the left child of the original node something like: A A
B C -> A’ C
B C’
B’This way on iterating over the original nodes, we can assign the left and right pointers, and we need one more traversal to assign the random pointer.We are given N solar systems, each solar system with M planets. We can move to any other planet of the same solar system in 1 light year.We can move from Mth planet of Kth solar system to 1st planet of (K + 1)th solar system in 1 light year. Apart from this we are also given a list of wormholes, where each wormhole specifies the entry planet and exit planet. Passing through a wormhole would also take 1 light year.Now given the X-starting planet, and Y-destination planet, we need to find the minimum number of light-years that we would take to travel.My Solution:I told him that I would create a graph(which was quite a ridiculous suggestion tbh :p) and then do bfs. He asked the time complexity of creating a graph and then applying my approach. Complexity was pretty bad, so I moved to a new solution. I suggested starting from X, add all the neigbouring planets at a distance 1 and if any wormholes are present from the planet and do bfs on the fly without creating graph. Since the time was less(as I had spent around 35-40 mins in the first question), I just coded a level-wise bfs and the interviewer seemed convinced.Round 2:This was taken by an engineering manager who asked me regarding my projects for around 10-15 mins and then we moved to a system design problem. He asked me to design Slack messenger.I started by listing the functional and non-functional requirements(on which he questioned me a bit), then I moved to draw the high-level architecture. The components which I drew were the clients, gateway service(LB + authentication, etc), Messaging Service, User Service, Web Socket Manager service, Fan Out service(I added this for the group messages thing, but he didn’t interrogate much on that).He asked me what would be the schema of my messages table and the scenarios in which the recipient user is online/offline.Also asked about the partitioning key and primary key of the 2-3 tables which I had made.Round 3:This was taken by an SDE III guy, who again asked me about my projects for like 10 mins and then moved on to a low level design question.He asked me to design the HackerRank platform.Again I started with listing down the usecases which I would cover, the interviewer asked me to write all the APIs which I would need to expose.I made various classes like Question(subclassed into MCQ and CodingQuestion), Answer, Candidate, Test, QuestionBank, etc.Surprisingly(since this was an LLD round) he asked me the schema of the tables and which SQL/NoSQL would I choose and why. Then he asked me the case when the question gets changed, I couldn’t answer that, later he mentioned that he was expecting something like and EditHistory inside each Test Entity.Round 4(Bar Raiser):This was again taken by an engineering manager who discussed my projects in depth for around 20-25 mins. In the remaining time he asked me 2 dsa questions. (Yes I too was surprised that he didn’t ask anything regarding design).Given a list of strings, group the anagrams together. (https://www.geeksforgeeks.org/given-a-sequence-of-words-print-all-anagrams-together/)Given two linked list L1 and L2 where head of the linked list points to the most significant digit, return a the linked list creating after subtracting these two lists. (https://www.geeksforgeeks.org/subtract-two-numbers-represented-as-linked-lists/)NOTE:In almost all the rounds, I was asked questions related to Amazon Leadership principles, so do make sure you go through those before sitting for the interview process. You can refer to this link(https://kraftshala.com/what-questions-to-expect-in-amazon-interview/) for practicing the same, I found it useful. In the design rounds, interviewer doesn’t expect the most ideal answer from you and unless your choice of technology is outrageously wrong, he won’t pinpoint that.