Amazon Interview Experience SDE-1

Round 1 (Online on HackerRank)
Duration: 90 minutes
20 MCQ questions mostly based on Operating System, Data Structures and Algorithms and a few puzzles.

2 coding questions:

1. I don’t remember the exact problem statement but it boils down to finding the cycle in an directed graph .
2. It was a no-brainer basic implementation question on strings. (Don’t remember the problem statement).

We were called On-Site in Hyderabad for further F2F rounds.

Round 2 (F2F) Duration= 70 minutes : Started with my resume asked few questions for about 5 minutes and started with the Problem statements.

So there were 3 questions asked in this round:

1. Given an array and a positive integer k, find the first negative integer for each and every window(contiguous subarray) of size k.

Started with the naive approach then gave the optimized solution similar to the Sliding Window Maximum.

2. Given a matrix of size M x N, there are a large number of queries to find submatrix sums. Inputs to queries are left top and right bottom indexes of submatrix whose sum is to find out. For each query, we have to find the sum in O(1).

After solving these 2 questions the interviewer had still some time so he asked the third question.

3. Consider a pipe of length L. The pipe has N water droplets at N different positions within it. Each water droplet is moving towards the end of the pipe(x=L) at different rates. When a water droplet mixes with another water droplet, it assumes the speed of the water droplet it is mixing with. Determine the no of droplets that come out of the end of the pipe.

I was not able to understand the problem statement in one go after all the clarifications required I gave the mathematical approach to solve this problem. He was convinced with the solution but was emphasizing as to which data structure could come in more handy for solving this particular problem. After a few hints, I told that it can be solved using stacks.

Round 3 (F2F) Duration= 75 minutes: He started with few questions on my previous job experience but it hardly lasted for 5 minutes and then interviewers started with the questions.

2 questions were asked in this round :

1. Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.

I gave the very first approach of using a hashmap and Dequeue for solving this but the interviewer told he didn’t want to do any processing for the result and this approach would require polling the characters from the dequeue if they are repeated. After that, I gave an approach of using a Hashmap where each character will be mapped to a Node of a Doubly Linked List. If we encounter a repeated character in our stream then we can delete that character from the DLL as we can get the node address from the hashmap. The head of the DLL will be our result.

Almost half an hour was consumed by this question.

2. Print the longest leaf to leaf path in a Binary tree.

I gave the most optimized solution as the time consumed on the first question was high.

Round 4 (F2F) Duration= 70-80 minutes: Started with my resume and previous work experience. Questions were asked on OOPS and SDLC(which was mentioned in my resume). After 10 minutes he started with the problem-solving questions.

2 questions were asked in this round:

1. Sort the LinkedList .

I gave the solution of merge-sort on the linked list.

2. Given that to prepare a certain ingredient we may require another ingredient i.e.
   • To prepare ingredient A we require ingredient B.(A -> B)
   • To prepare ingredient B we require ingredient C.(B -> C)
   • To prepare ingredient C we require ingredient A.(C -> A)

We have to determine if we will be able to prepare the dish or not. So it boils down to finding the loop in the directed graph. After the 3 On-site round, selected candidates were told that they will have a video call round(Bar raiser). The bar raiser round was conducted after a long wait of about a month.

Round 5 bar raiser round= 70-80 minutes: Started with the introduction interviewer then told that he will ask few questions then I have to answer them with an example from my previous company experience. Following that he will ask one coding question.

So the questions asked by the interviewer were :

1. Tell me a situation where the customer was pushing really hard and you have to deliver the results very fast because of the same.
2. Tell me a problem you solved in your previous organization? After that, he asked why did I choose this particular problem only.

After around 30 minutes of discussion, he gave a coding question that was to solve on the code editor that was shared.

1. We have to rotate an array of size n by r. He was expecting an O(n) in-place solution. I gave the Juggling algorithm solution for this particular problem.

After around a week I received an mail saying “Congratulations! We are pleased to inform you that Amazon is making an Offer for the role of Software Development Engineer”.