Amazon Software Developer Intern Interview Questions, Process, and Tips

Round duration - 145 minutes
Round difficulty - Easy

The online assessment consisted of four components, a code debugging section (20 minutes), a coding test (70 minutes), a workstyles assessment (20 minutes) and a reasoning ability section (35 minutes). Code debugging questions were pretty simple and straightforward. The coding test consisted of 2 questions, first was similar to two Sum problem. Second question was similar to find the critical edges in a graph. The workstyles assessment section contained certain behavioural questions.
Reasoning ability section consisted of aptitude questions. This round was basically to check the problem solving skills of the candidate.

Q1. 
Find All Pairs Adding Up to Target
Given an array of integers ARR of length N and an integer Target, your task is to return all pairs of elements such that they add up to the Target.
Input:
The first line ...read more
Ans. 
This problem was pretty standard. the solution is easily available online.
Answered Anonymously
Add your answer
Q2. 
Bridges in a Graph Problem Statement
In an undirected graph consisting of V vertices and E edges, your task is to identify all the bridges within the graph. A bridge is an edge which, when removed, result...read more
Ans. 
I applied dfs in the above problem with slight modifications.
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

I was asked two coding questions. First question was related to binary tree and second question was to implement LRU cache.
I had to code both questions. The interviewer asked me the time and space complexity for both the questions.

Q1. 
Circular Array Loop Problem Statement
Given a circular array ARR of size N consisting of positive and negative integers, determine if there is a cycle present in the array. You can make movements based on...read more
Ans. 
I solved this problem using DFS and BFS. 
Answered Anonymously
Add your answer
Q2. 
LRU Cache Implementation
Design and implement a Least Recently Used (LRU) cache data structure, which supports the following operations:
• get(key) - Return the value of the key if it exists in the cach...read more
Ans. 
I used a queue, doubly linked list and hashmap to solve this problem in constant time complexity.
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

I was asked two coding questions and some conceptual questions about priority heap data structure. I was able to code the optimized approach for the first question. But second question was a little tricky for me as I had never heard it before. But I explained my approach confidently. The interviewer also helped me and finally I was able to code it.

Q1. 
Connect Ropes with Minimum Cost
Given 'N' ropes, each having different lengths, your task is to connect these ropes into one single rope. The cost to connect two particular ropes is equal to the sum of th...read more
Ans. 
Firstly I solved this problem using greedy approach by using min heap.
After writing the code of this problem, I was asked follow up questions about heap data structure. One question was what if a binary tree was used to store the elements of the heap instead of an array.
Answered Anonymously
Add your answer
Q2. 
Langford Pairing Problem Statement
Given a positive integer N, you are required to generate a list of integers of size 2N such that it contains all the integers from 1 to N, both included, twice. These in...read more
Ans. 
I started explaining my approach to the interviewer starting with brute force approach, then I told him that recursion can be used and finally coded it. It was not the optimized version but still I managed to give an approach that came to my mind.
Answered Anonymously
Add your answer

Round duration - 75 minutes
Round difficulty - Hard

This round was scheduled in the evening hours and all the participants were required to fill a form which was shared 15 minutes prior to the start of the online coding round. This form was filled out probably for the security reasons and to ensure that no one disinterested participant gives the test.

Q1. 
Longest Palindromic Substring Problem Statement
You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palind...read more
Ans. Brute Force
1. Generate substrings of the given string such that substring having greater length will be generated first.
2. To do this, run a loop where iterator ‘LEN’ will go from N to 1, where N is the length of the given string.
3. Run a nested loop and fix an iterator ‘j’ that will point at the starting index of the substring.
4. Get the substring from ‘j’ to ‘j’ + ‘LEN’.
5. If the substring is a palindrome, return the substring (as ...read more
Answered Anonymously
Add your answer
Q2. 
Remove All The Palindromes Problem Statement
Given a string STR consisting only of lowercase letters, your task is to modify the string by replacing the minimum characters such that the string doesn’t con...read more
Ans. Greedy Approach
The basic idea of this approach is to remove all the palindromes of length two and three. The idea is that if there exists a palindromic substring larger than length 3 then a palindrome of length 2 or 3 is present. 

Here is the algorithm:
 
1. Declare a variable ‘COUNT’ which stores the minimum number of replacements.
2. Declaring another variable ‘CHANGECHAR’ which will store the ASCII value of capital ...read more
Answered Anonymously
Add your answer

Round duration - 120 Minutes
Round difficulty - Medium

Round started at 6pm in the evening and had 4 sections.

Q1. 
Fire in the Cells Problem Statement
Given a matrix 'MAT' of size 'N' * 'M', where 'N' is the number of rows and 'M' is the number of columns. A cell with value '0' represents it is initially on fire (at t...read more
Ans. Multisource BFS
With each passing second fire expands and there are multiple cells at fire initially, (at time t = 0). So we will create an auxiliary matrix ‘TIME_OF_FIRE’ of size ‘N’ * ‘M’  to store the minimum time it will take for each cell to catch fire.
 
Iterate through the given matrix ‘MAT’ [][] and set ‘TIME_OF_FIRE’ [][] for a cell ( ‘i’, ‘j’ ) to 0, if ‘MAT’ [‘i’][‘j’]  = 0, (source of fire) beca...read more
Answered Anonymously
Add your answer
Q2. 
Search in a Row-wise and Column-wise Sorted Matrix Problem Statement
You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the positi...read more
Ans. Brute Force
• Run a loop from i = 0 to N - 1, to check each row.
  • Run a loop from j = 0 to N - 1, to check each element of the row.
    • If there is a match, return {i, j}.
• If the element is not found in the entire matrix, return {-1, -1}
Space Complexity: O(1)Explanation:
O(1).
 
Since only constant extra space is required.
Time Complexity: O(n^2)Explanation:
O(N ^ 2), where ‘N’ is the number of rows or columns in the matrix.
&nb...read more
Answered Anonymously
Add your answer

Round duration - 78 minutes
Round difficulty - Medium

The round started at 11 am and was conducted on amazon chime, They provided me a link to live sheet where I had to write all the code. Interviewer was very good at conducting a smooth interview and provided me small hints as I got stuck at some points.

Q1. 
Unique Element In Sorted Array
Nobita wants to impress Shizuka by correctly guessing her lucky number. Shizuka provides a sorted list where every number appears twice, except for her lucky number, which a...read more
Ans. Brute force
The idea here is to use the fact that the array is sorted and the element of the array (‘arr[i]’) is unique if it doesn't have an adjacent element that has the same value as ‘arr[i]’. 
 
Algorithm:
• If the length of the array equal to 1 then return ‘arr[0]’.
• Declare a variable ‘answer’ to store Shizuka’s lucky number.
• Run a loop from i = 0 to the length of the array - 1.
• If ‘arr[i]’ does not have an adjac...read more
Answered Anonymously
Add your answer
Q2. 
Level Order Traversal Problem Statement
Given a binary tree of integers, return the level order traversal of the binary tree.
Input:
The first line contains an integer 'T', representing the number of te...read more
Ans. Breadth First Search
In the level order traversal, we will be using queue data structure which has the property FIRST IN FIRST OUT that’s why which nodes come first in current level the children of that node will also come first for the next level. So, we visit all the nodes one by one of the current level and push into the queue so that when we will be complete with the current level, then we can start exploring nodes ...read more
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

The round started at 4pm and was conducted on amazon chime, They provided me a link to live sheet where I had to write all the code.

Q1. 
Find Duplicate in Array Problem Statement
You are provided with an array of integers 'ARR' consisting of 'N' elements. Each integer is within the range [1, N-1], and the array contains exactly one duplica...read more
Ans. Using Sort
First, we sort the array. Now, the rest of the algorithm becomes fairly simple. We just compare each element to its previous element. As we know there is exactly one repeated element, hence we can simply just return the element, which is equal to its previous element as soon as we find it.
Space Complexity: O(1)Explanation:
O(1) or O(N),
 
We can sort the array either in place or by taking another array if ...read more
Answered Anonymously
Add your answer

Round duration - 215 minutes
Round difficulty - Medium

* Debugging(C, C++, Java, Python) [Time given was quite enough.]
* Coding(Any programming language was allowed. 2 coding questions medium to difficult level 70 mins)
* Psychometric test based on Leadership principle — Don’t take it for granted. I would suggest to pay attention while 
answering to this as well.
* Aptitude and Logical reasoning (Good enough time was given.)

Q1. 
Weird Number Pattern Problem Statement
You are given an integer 'N'. Your task is to print a specific pattern for the given number of rows 'N'.
Input:
The first line contains a single integer ‘T’ repres...read more
Ans. Number Pattern 1
The basic idea of this approach is to print the pattern row-wise. For each row, a pattern is observed: 1 is printed 1 time in the 1st row, 2 times in the 2nd row, 3 times in the 3rd row, and so on. So, a pattern is observed that the number of rows determines how many times 1 is printed in each row.

 Here is the algorithm:
 
1. Run a loop for ‘ROW’ = 0 to ‘N’:
   • Run a loop for ‘COL’ = 0 to equal to ‘ROW...read more
Answered Anonymously
Add your answer
Q2. 
Find All Pairs Adding Up to Target
Given an array of integers ARR of length N and an integer Target, your task is to return all pairs of elements such that they add up to the Target.
Input:
The first line ...read more
Ans. Hashing Solution
• We can store the frequency of every element in the array in a hashmap.
• We will loop over every index i, and check the frequency of (Target - ARR[i]) is the hashmap:
  • If (Target - ARR[i]) is equal to ARR[i], we will check if frequency of ARR[i] . If it is greater than 1 then we will decrease the frequency of ARR[i] by 2 and add a pair (ARR[i] , ARR[i]) to our answer.
  • Else, if the frequency of ARR[i] and Targ...read more
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

(Time — 5.30 p.m.): I introduced myself. My interviewer told me that he would divide the interview into three phases.
Phase 1- Introduction and questions on life instances where I proved my efficiency. (barely 10 minutes, I answered well.)
Phase 2- Data Structures’ Understanding and questions related to it. (Hashing concept and complete conceptual details about it. Internal working, collisions, how to avoid them etc.) (15 minutes, He was satisfied with my answers. Don’t just answer. Explain !)

Q1. 
Longest Unique Substring Problem Statement
Given a string Str consisting of N lowercase Latin letters, you need to determine the longest substring without repeating characters.
A substring is defined as ...read more
Ans. Brute-Force
In this approach, we will consider every substring and check if it can be the longest unique substring. Let’s say we have a variable ‘ans’ that stores the longest unique substring.
 
For every substring, we will make a count array of size 26 that will store the count of each character in the substring. If every character in the substring has a count less than 2, we check if it is the longest unique substr...read more
Answered Anonymously
Add your answer

Round duration - 70 minutes
Round difficulty - Hard

(Time — 7.00 p.m.): I introduced myself. The interviewer directly jumped onto the questions. He asked me two questions. The first question he asked me was: Coding Question

Q1. 
Longest Substring with At Most K Distinct Characters
Given a string S of length N and an integer K, find the length of the longest substring that contains at most K distinct characters.
Input:
The first...read more
Ans. Brute Force
• We will generate all the substrings using 2 nested for loops and we will have a ‘CHECK’ function which returns true if the number of distinct character in the substring is less than equal to K otherwise false.
• We will have an ans variable initialize to 0. We will call the ‘CHECK’ function with every substring and if it returns true then
  • ANS = MAX(ANS , CURRENT_SUBSTRING.SIZE())
• To implement the check function w...read more
Answered Anonymously
Add your answer
Q2. 
Count Set Bits Problem Statement
Given a positive integer N, compute the total number of '1's in the binary representation of all numbers from 1 to N. Return this count modulo 1e9+7 because the result can...read more
Ans. Brute Force
The key idea is to count the number of set bits in each number from 1 to n and return the sum of all set bits.
 
The algorithm will be -
 
• For each i from 1 to N -
  • We find the number of set bits for each i.
  • This can be done using a built-in function (for eg builtin_popcount in c++) or by simply using a loop and left shifting the number and finding if the last place is set or not.
• Finally we store the coun...read more
Answered Anonymously
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

The first Round was held on Hackerrank and the questions were of medium difficulty based on Data Structures and Algorithms.
The time of test was 1:00 PM and it was of 45 minutes with 2 coding questions to be solved.

Q1. 
Merge Overlapping Intervals Problem Statement
Given a specified number of intervals, where each interval is represented by two integers denoting its boundaries, the task is to merge all overlapping interv...read more
Add your answer
Q2. 
Josephus Problem Statement
Consider 'N' individuals standing in a circle, numbered consecutively from 1 to N, in a clockwise direction. Initially, the person at position 1 starts counting and will skip K-...read more
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

A google Doc was shared with us and we were supposed to write code there. 
Use of IDEs was not allowed so we had to write correct code on Google Docs which was later checked by them through online IDEs.
The Interviewer were friendly and observative and helped us through code if we made some silly error.

Q1. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Add your answer
Q2. 
Boundary Traversal of a Binary Tree
Given a binary tree of integers, your task is to return the boundary nodes of the tree in Anti-Clockwise direction starting from the root node.
Input:
The first line ...read more
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

The face to face round was held on Google Meet where initially Interviewer asked a DS/Algo problem and then Later Manager Joined and asked about our resume projects in detail.
The time was 10:00 AM

Q1. 
Maximum Sum Rectangle Problem
Given an M x N matrix of integers ARR, your task is to identify the rectangle within the matrix that has the greatest sum of its elements.
Input:
The first line of input co...read more
Add your answer
Q2. 
Rotated Array Minimum Finder
You are provided with a sorted array that has undergone 'K' rotations (the exact value of 'K' is unknown). A rotation involves shifting each element of the array to the right,...read more
Add your answer