Round1 : Online Coding Test (2 questions - 120 minutes)
Q1 : https://leetcode.com/problems/cheapest-flights-within-k-stops/
Q2 : https://leetcode.com/problems/critical-connections-in-a-network/
The language of these questions were different,and were changed to something like Amazon has a retail business/transport business, how would you calculate cheapest flights or important connections.
Solved both within 2 hours.
Called for Round 2 and Round 3 after a month or so which happened on same day via Chime
Round2 :
Q1 : Given a binary tree, replace the node value to its left subtree sum.
Solved this using recursion, the interviewer was happy with time complexity and space complexity analysis which is O(n) time and O(n) space if we consider the recursion stack.
Q2: Next greater element in an array : https://leetcode.com/problems/next-greater-element-ii/
solved this using stack O(n) for both time and space complexity.
Some discussion on the Amazon leadership principles.
The Whole interview took around 60 minutes.
Round3:
Happened after 3 hours.
We started later than allocated time.
Started with 3-4 leadership principles questions, answered them based on experience.
Q1 : Given an array you have to choose k elements either from starting or ending of the array such that the sum is maximum.
We discussed some time on the question because it was difficult to understand based on the problem statement, I recognized this question as a sliding window based question and solved this 2 pointers approach.
Approach : Start with last k elements and its sum, keep first pointer at (n-k)th element and second at starting element, now keep subtracting first pointer from sum and keep adding second pointer element, update pointer and keep track of maximum sum.
Time Complexity = O(n) and Space = O(1)
The Interviewer was satisfied with the approach and asked me to code the same.
Whole interview lasted for 45 minutes.
Round 4 :
Manager Round, this happened next week after the last 2 interviews.
Most of the interview was based on leadership principles.
In last 15 minutes he asked one coding question
Q1 : Remove all duplicates from a String (order also needs to be maintained).
Solved this using StringBuilder and hashSet, O(n) space and time complexity.
Round 5 :
Coding Round : This happened a week after the managerial round
Spent some time on leadership principles before moving on to the questions.
Q1: https://leetcode.com/problems/meeting-rooms-ii/
solved this using 2 min heaps for start and end time. Ran some tests with the interviewer and he was happy. He asked If I could optimize space a bit, I told we have use only one heap in that case and sort the array. He was satisfied with the approach and we moved onto the next question.
Q2 : https://leetcode.com/problems/kth-missing-positive-number/
Since the array was sorted and we have to find the kth element, binary search is the first thing that came to my head, and told the interviewer the same. He told let's start with brute force first, the wrote the linear O(n) code which he was ok with, he asked me what change we needed O(n) approach, I told him my binary search approach which he agreed upon
Got acceptance mail from Amazon HR one week after the last interview round.