Amazon Software Developer Intern Interview Questions, Process, and Tips

Round duration - 75 Minutes
Round difficulty - Medium

Q1. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider edge cases such as when the matrix is empty or all cells are water (0s).
Answered by AI
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. 
Given a sorted N * N matrix, find the position of a target integer 'X'.
• Iterate over each row and column to search for the target integer 'X'.

• Utilize the sorted nature of the matrix to optimize the search process.

• Return the position of 'X' if found, else return '-1 -1'.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Merge Two Sorted Linked Lists Problem Statement
You are provided with two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the combined linked list.
...read more
Ans. 
Merge two sorted linked lists into a single sorted linked list without using additional space.
• Create a dummy node to start the merged list

• Compare the nodes of both lists and link them accordingly

• Move the pointer to the next node in the merged list

• Handle cases where one list is empty or both lists are empty

• Time complexity: O(n), Space complexity: O(1)
Answered by AI
Add your answer
Q2. 
Pair Sum Problem Statement
You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to find and return a list of all pairs of elements where each sum of a pair equals 'S'.
Note:
...read more
Ans. 
Find pairs of elements in an array that sum up to a given value, sorted in a specific order.
• Iterate through the array and for each element, check if the complement (S - current element) exists in a hash set.

• If the complement exists, add the pair (current element, complement) to the result list.

• Sort the result list based on the first element of each pair, and then based on the second element if the first elements are eq
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

it was pure DSA round, no HR round was there after this

Q1. 
Rat in a Maze Problem Statement
You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N ma...read more
Ans. 
Find all possible paths for a rat in a maze from source to destination.
• Use backtracking to explore all possible paths in the maze.

• Keep track of visited cells to avoid revisiting them.

• Recursively try moving in all directions (up, down, left, right) until reaching the destination.

• Return the valid paths as a list of strings sorted in alphabetical order.
Answered by AI
Add your answer

Round duration - 80 minutes
Round difficulty - Medium

This was Online interview 
this is one and only interview which was based on totally DSA (Problem Solving Skills)
which was held on AMAZE CHIME

Timing : 12pm
Environment was very good

Q1. 
Reverse Linked List Problem Statement
Given a Singly Linked List of integers, your task is to reverse the Linked List by altering the links between the nodes.
Input:
The first line of input is an intege...read more
Ans. 
Reverse a singly linked list by altering the links between nodes.
• Iterate through the linked list and reverse the links between nodes

• Use three pointers to keep track of the previous, current, and next nodes

• Update the links while traversing the list to reverse it

• Return the head of the reversed linked list
Answered by AI
Add your answer
Q2. 
The Celebrity Problem
Imagine there are 'N' people at a party, each assigned a unique ID from 0 to N-1. A celebrity at the party is a person who is known by everyone but knows no one else.
Problem Statem...read more
Ans. 
Identify the celebrity at a party where one person knows everyone but is not known by anyone.
• Use a two-pointer approach to eliminate non-celebrity candidates.

• Start with two pointers at the beginning and end of the party.

• If A knows B, A cannot be the celebrity; move A to B.

• If A does not know B, B cannot be the celebrity; move B to A.

• Repeat until only one person remains; check if this person is known by everyone.

• Return t
Answered by AI
Add your answer

Round duration - 120 Minutes
Round difficulty - Medium

Around 4-5 pm
2 coding questions
7 debugging and output questions
20-30 aptitude questions
A section to test psychology based on various questions and situations.

Q1. 
Clone Linked List with Random Pointer Problem Statement
Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or ...read more
Ans. 
Cloning a linked list with random pointers by creating new nodes rather than copying references.
• Create a deep copy of the linked list by iterating through the original list and creating new nodes with the same values.

• Update the random pointers of the new nodes by mapping the original node's random pointer index to the corresponding new node.

• Ensure the cloned linked list is an exact copy of the original by validating th...read more
Answered by AI
Add your answer
Q2. 
Next Smaller Element Problem Statement
You are provided with an array of integers ARR of length N. Your task is to determine the next smaller element for each array element.
Explanation:
The Next Smalle...read more
Ans. 
Given an array of integers, find the next smaller element for each element in the array.
• Iterate through the array from right to left and use a stack to keep track of elements.

• Pop elements from the stack until a smaller element is found or the stack is empty.

• If no smaller element is found, output -1 for that element.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

Timing - 4pm
Just asked one question based on DSA and asked to make the code modular and well indented.
Didn’t even ask for introduction.

Q1. 
Rotting Oranges Problem Statement
You are given a grid containing oranges where each cell of the grid can contain one of the three integer values:
• 0 - representing an empty cell
• 1 - representing a fre...read more
Ans. 
Find minimum time to rot all fresh oranges in a grid if adjacent to rotten oranges.
• Use Breadth First Search (BFS) to simulate the rotting process of oranges.

• Keep track of the time taken to rot all fresh oranges.

• If at the end there are still fresh oranges left, return -1 as it is impossible to rot all oranges.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Started at 4pm
Interviewer introduced himself and then asked me for a brief introduction.
Went ahead to ask 2 DSA based questions.

Q1. 
Merge k Sorted Linked Lists
You are provided with 'K' sorted linked lists, each sorted in increasing order. Your task is to merge all these lists into one single sorted linked list and return the head of ...read more
Ans. 
Merge k sorted linked lists into one single sorted linked list.
• Create a min-heap to store the heads of all k linked lists.

• Pop the smallest element from the heap and add it to the result list.

• If the popped element has a next element, push it back into the heap.

• Repeat until all elements are merged into a single sorted list.
Answered by AI
Add your answer
Q2. 
Rat in a Maze Problem Statement
You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N ma...read more
Ans. 
Find all possible paths for a rat in a maze from source to destination.
• Use backtracking to explore all possible paths in the maze.

• Keep track of visited cells to avoid revisiting them.

• Recursively try moving in all directions (up, down, left, right) until reaching the destination.

• Add the current direction to the path and backtrack if the path leads to a dead end.

• Return all valid paths found in alphabetical order as an ar
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

It was in the evening, test consists of technical MCQ as well as Aptitude quesitons. There were debugging round of 7 questions and 2 coding questions (medium-hard leetcode level).

Q1. 
Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
...read more
Ans. 
Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.
• Traverse both trees and check if S is a subtree of T at each node

• Use recursion to compare subtrees

• Handle edge cases like empty trees or null nodes
Answered by AI
Add your answer
Q2. 
Clone Linked List with Random Pointer Problem Statement
Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or ...read more
Ans. 
Cloning a linked list with random pointers by creating new nodes rather than copying references.
• Create a deep copy of the linked list by iterating through the original list and creating new nodes with the same values.

• Update the random pointers of the new nodes by mapping the original node's random pointer index to the corresponding new node.

• Ensure the cloned linked list is an exact copy of the original by validating th...read more
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

It was in Morning. Interviewer was SDE-2 and was experienced.

Q1. 
Flip Bit to Win Problem Statement
You are given a task to help ninjas maximize their practice area in a dense forest represented by a sequence of trees (1s) and empty places (0s) in the binary representat...read more
Ans. 
Given an integer representing a binary sequence, find the maximum consecutive ones by flipping one bit.
• Iterate through the binary representation of the integer to find the longest sequence of ones.

• Track the positions of zeros to determine where to flip a bit for maximizing consecutive ones.

• Update the count of consecutive ones after flipping a zero to one.

• Return the maximum length of consecutive ones obtained by flippin
Answered by AI
Add your answer
Q2. 
Saving Money Problem Statement
Ninja is adventurous and loves traveling while being mindful of his expenses. Given a set of 'N' stations connected by 'M' trains, each train starting from station 'A' and r...read more
Ans. 
Given a set of stations connected by trains, find the cheapest fare from a source to a destination with a maximum number of stops allowed.
• Iterate through all possible routes with up to 'K' stops using a graph traversal algorithm like DFS or BFS.

• Keep track of the cost for each route and return the minimum cost found.

• If no route is found within the maximum stops allowed, return '-1'.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

It was in evening. Interviewer was really energetic and funny.

Q1. 
Find the Row with the Maximum Number of 1's
You are given a non-empty grid MAT with 'N' rows and 'M' columns, where each element is either 0 or 1. All rows are sorted in ascending order.
Your task is to ...read more
Ans. 
Find the row with the maximum number of 1's in a grid of 0's and 1's.
• Iterate through each row of the grid and count the number of 1's in each row.

• Keep track of the row index with the maximum number of 1's seen so far.

• Return the index of the row with the maximum number of 1's.
Answered by AI
Add your answer
Q2. 
Knight Probability in Chessboard
Calculate the probability that a knight remains on an N x N chessboard after making K moves. Initially, the knight is placed at a given position on the board. It can move ...read more
Ans. 
Calculate the probability that a knight remains on an N x N chessboard after making K moves.
• Use dynamic programming to calculate the probability of the knight staying on the board after each move.

• Consider all possible moves the knight can make from its current position.

• Keep track of the probabilities at each position on the board after each move.

• Normalize the probabilities at the end to get the final result accurate to
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

There were 30 MCQ and 7 Debugging question and two coding question
Then technical interview 1
Then last technical plus hr Interview

Q1. 
Flatten BST to a Sorted List
The objective is to transform a given Binary Search Tree (BST) into a right-skewed BST, effectively flattening it into a sorted list. In the resulting structure, every node's ...read more
Ans. 
Transform a Binary Search Tree into a right-skewed BST, flattening it into a sorted list.
• Implement a function to flatten the BST into a sorted list by linking nodes through right children.

• Traverse the BST in-order and adjust the pointers to create the right-skewed structure.

• Ensure that every node's left child is NULL in the resulting flattened BST.

• Output the values of nodes in the skewed BST in level order for each tes...read more
Answered by AI
Add your answer
Q2. 
Prerequisite Task Completion Verification
Given a positive integer 'N', representing the number of tasks, and a list of dependency pairs, determine if it is possible to complete all tasks considering thes...read more
Ans. 
Given tasks and dependencies, determine if all tasks can be completed based on prerequisites.
• Create a graph representation of tasks and dependencies.

• Use topological sorting to check if there is a cycle in the graph.

• Return 'Yes' if no cycle is found, 'No' otherwise.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Two questions were given to me and requested to solve in the desired time.

Q1. 
Sort Linked List Based on Actual Values
Given a Singly Linked List of integers that are sorted based on their absolute values, the task is to sort the linked list based on the actual values.
The absolute...read more
Ans. 
Sort a Singly Linked List based on actual values instead of absolute values.
• Traverse the linked list and store the nodes in an array.

• Sort the array based on the actual values of the nodes.

• Reconstruct the linked list using the sorted array.
Answered by AI
Add your answer
Q2. 
Convert a Binary Search Tree (BST) to a Greater Sum Tree
Given a Binary Search Tree of integers, transform it into a Greater Sum Tree where each node's value is replaced with the sum of all node values gr...read more
Ans. 
Convert a Binary Search Tree to a Greater Sum Tree by replacing each node's value with the sum of all node values greater than the current node's value.
• Traverse the BST in reverse inorder (right-root-left) to visit nodes in descending order.

• Keep track of the running sum of visited nodes and update each node's value with this sum.

• Modify the BST in place without creating a new tree.

• Example: For input 11 2 29 1 7 15 40 -1...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Two questions were asked but I don't remember the second one.

Q1. 
Split Array into K Subarrays
You are given an array ARR of size N and an integer K. Your task is to split ARR into K sub-arrays such that the maximum sum obtained from these K subarrays is minimized.
Inp...read more
Ans. 
Split an array into K subarrays to minimize the maximum sum obtained from the subarrays.
• Sort the array in descending order to get the maximum sum possible.

• Use binary search to find the minimum possible value of the maximum sum.

• Consider the constraints to optimize the solution.

• Example: For N=4, K=3, ARR=[1, 2, 3, 4], the minimum possible value of the maximum sum is 4.
Answered by AI
Add your answer

Round duration - 150 Minutes
Round difficulty - Medium

The test was on AMCAT platform.
The test was of 2.5 hours , web-proctored and switching between tabs was not allowed.

Test consist of 4 sections:

1 Debug section which had 7 questions to correct/write the code. (20min)
2 Coding section having 2 questions. (70 min)
3 Logical Reasoning section. (35 min)
4 Workstyle assessment. (20 min)

Q1. 
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. 
Given a sorted N * N matrix, find the position of a target integer 'X'.
• Iterate over each row and column to search for the target integer 'X'.

• Utilize the sorted nature of the matrix to optimize the search process.

• Return the position of 'X' if found, else return '-1 -1'.
Answered by AI
Add your answer
Q2. 
Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
...read more
Ans. 
Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.
• Traverse both trees and check if S is a subtree of T at each node

• Use recursion to compare subtrees

• Handle edge cases like empty trees or null nodes
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Hard

Interview was conducted on Amazon Chime platform and for coding, link was shared on which I had to code.
Two questions were given to me and requested to solve in the desired time. 
Interviewer was friendly and supportive.

Q1. 
Reachable Nodes Problem Statement
You are provided with a graph containing 'N' nodes and 'M' unidirectional edges. Your task is to determine the number of nodes that can be reached from each node 'i', whe...read more
Ans. 
The task is to determine the number of nodes that can be reached from each node in a graph.
• Create an adjacency list to represent the graph.

• Use Depth First Search (DFS) to traverse the graph and count reachable nodes from each node.

• Initialize a count array to store the number of reachable nodes for each node.

• Update the count array while traversing the graph using DFS.

• Output the count array for each test case.
Answered by AI
Add your answer
Q2. 
Squares of a Sorted Array Problem Statement
You are given an array/list ARR consisting of N integers. Your task is to generate a new array/list containing the squares of each element in ARR, with the resu...read more
Ans. 
Given an array of integers, generate a new array with the squares of each element sorted in increasing order.
• Iterate through the array and square each element

• Sort the squared elements in increasing order

• Return the sorted array
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

Interview was conducted on Amazon Chime platform and for coding, link was shared on which I had to code.
Three questions were given to me and requested to solve in the desired time. 
Interviewer was friendly and supportive.

Q1. 
Valid String Problem Statement
Given a string S consisting solely of the characters '(', ')', and '*', determine if it is a valid string.
Definition of Valid String:
1. Every left parenthesis '(' must h...read more
Ans. 
Determine if a given string consisting of '(' , ')' and '*' is valid based on certain rules.
• Iterate through the string and keep track of the count of left parentheses, right parentheses, and stars.

• Use a stack to keep track of the positions of left parentheses.

• If at any point the count of right parentheses exceeds the count of left parentheses + stars, the string is invalid.

• If the stack is not empty at the end, the stri
Answered by AI
Add your answer
Q2. 
Convert a Binary Tree to its Sum Tree
Given a binary tree of integers, convert it to a sum tree where each node is replaced by the sum of the values of its left and right subtrees. Set leaf nodes to zero.
...read more
Ans. 
Convert a binary tree to a sum tree by replacing each node with the sum of its left and right subtrees.
• Traverse the tree in postorder fashion.

• For each node, calculate the sum of its left and right subtrees and update the node's value.

• Set leaf nodes to zero.

• Return the level order traversal of the modified tree.
Answered by AI
Add your answer