Amazon Interview Experience

I interviewed with amazon for SDE-1 role. Here is my experience for the same.

I was invited to their Hyderabad campus for the interviews. In all rounds, their main focus was to test programming skills and knowledge about Data Structures & Algorithms. I was asked to write production-level working code for all the questions in all rounds.

Round 1:

Duration: 60–90 mins: 2 questions

2.) Given a set of sticks of varying length, combine them into 1 single stick. The cost to connect two sticks is the sum of their lengths. We need to connect the sticks with minimum cost.

(Tip: The interviewer was speaking very soft and low, don’t hesitate to ask your doubts multiple times until they are solved. Interviewers are very friendly and they are there to help)

Round 2:

Duration: 60–90 mins: 3 questions

1.) Given a linked list, find its length.

At 1st on hearing the question, I almost laughed (thinking who will ask this question in amazon interview :P) and so did both the interviewers. I confirmed what I just heard was correct or not. The interviewer confirmed giving some hint, that you will only get a pointer to head node of the list, your code should be capable to work in all scenarios. I got the hint, this was an open-ended question, where the interviewee is expected to ask questions to narrow down the scope of the question. Questions which I asked were whether it is singly/doubly linked list, is there any loop in the linked list, is it circular? This helped to narrow down the scope to a singly linked list with a possible loop.

2.) Given k sorted arrays, merge them all in a single sorted array.

3.) Given an infinite stream of words, output all set of possible anagrams at any point in time. Let’s suppose stream is like cat, act, dog, god, abc, tac at this moment possible set of anagrams are act → [cat,tac,act], dog → [god, dog].

As it was an infinite stream of words, I need to use a data structure where I can map & store words with all its anagrams. So I used hashmap (String, Set<String>) to solve the problem. I would sort the incoming word in its alphabetical order (cat → act), check if it is present in the hashmap. If no I would insert it as a key (act) and add the original word (cat) as value to the set of the string corresponding to it. If the alphabetically sorted word (tac → act) is already present in the hashmap (act is already present), I will just add the original word (tac) to the set of the string corresponding to it. At this point, for the example taken here map will look like (act → [cat, tac])

(Tip: Be alert to pick up hints given by interviewers. Don’t directly jump to the solution without dry-running your logic on multiple test cases)

Round 3:

Duration 90–120 mins.

In this round, I was asked many DBMS, OS & OOPs questions. Also some questions on the programming language I mentioned in my resume (Java & Python). Few of them which I could recall were deadlocks in OS, conditions to prevent deadlocks, threading, the difference between runtime & compile time, how does JVM work, how python works, comparison between both the languages and many similar questions.

Then I was asked a programming question.

Amazon wants to design an algorithm for their delivery system. Given a Fulfillment Centre (FC) as the root of the tree, we need to deliver packages to all the destination cities (leaf nodes) of the tree. There is a budget of X units assigned for this task, it costs 1 unit to travel 1 road (edge) of the tree. Provide the best possible solution so that maximum packages can be delivered to different cites. Exactly 1 package is to be delivered to each city. Also, exactly 1 unit can be sent in 1 shipment from FC. It is assumed that it doesn’t cost any unit to come back to the root (FC) of the tree after delivering the package.

As we need to deliver maximum possible packages in a limited budget, I thought of the solution where we would be targeting closest cites to FC first and then gradually target cites that are away from the root in a top-down fashion. Distance and cost would also increase as we move down the tree. I came up with a level order traversal approach where packages will be delivered to cites at level 1 → level 2 → level 3 and so on until the budget is exhausted. The interviewer asked to explain & dry run the logic on a few sample test cases. He was satisfied with the solution & time/space complexity.

(Tip: There were a few questions that I was not able to answer in 1st half of this round as I was not aware of the concepts. Please let your interviewer about the same instead of remaining silent. It will set clear expectations for an interviewer & will help him to focus on other concepts you know)

Round 4:

Duration 60–75 mins. Online BR (Bar Raiser) Round

After 2 weeks, I was invited for online BR round which was also the last round. I was interviewed by a senior engineering manager. The main focus in this round was to test tech knowledge, previous projects, design concepts & leadership principles. In the beginning, I was asked about business and tech involved in my past company projects. Many questions were asked to check if I clearly understand the business and how my projects were impacting the business.

Post that I was provided with a link for online coding platform which was internal to amazon similar to coderpad. Given a singly linked list, swap adjacent nodes and write the code for the same on the online editor. Also, the BR was expecting to think out loud even about the brainstorming for solving the problem. After explaining the approach was asked to code it.

Next, I was asked to design multilevel parking where each parking slot will be of the same size. It was an open-ended question, it was expected from me to ask questions to define the boundaries. I asked questions like how many entry/exit gates, how will vehicles be allocated parking, etc.

There was exactly 1 entry & exit gate, at each entry gate machine has been installed which would provide the user with the token number indicating empty slot in the parking. I was also asked to design an algorithm for the same. After I provided the solution & coded it, as an extension I was asked what if parking slots are of different sizes like Small, Medium & Large. How would you scale your solution with minimal design & code change? I was able to solve it doing minimal code changes.

(Tip: Try to design systems keeping in mind the scalability, modularity & other design principles)

I was contacted by HR after 3–4 weeks of duration about the further procedure.

Verdict: Selected :)

Related posts:

I recently did business with an agency. I needed a fairly high-risk-of-failure project accomplished. I had no idea if we could pull it off, but we had to try. So they listened to what I wanted. Asked…

When we were much younger people, my cousin ran into some engine problems with her car. I asked where she was going for repairs, and she said, “Oh, I’ll probably take it to the Sturdy Girls.” The…