100+ Amazon Software Developer Intern Interview Questions and Answers

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.

Return the postorder traversal of a binary tree given its root node.

• Traverse left subtree

• Traverse right subtree

• Visit root node

• Use recursion to solve

• Example: [4, 5, 2, 3, 1]

Find the position of the rightmost set bit in a given number's binary representation.

• Convert the number to binary representation.

• Find the position of the rightmost set bit by counting from the right.

• Return the position as output.

Count the number of subarrays where the number of 0s is equal to the number of 1s in a given array of 0s and 1s.

• Iterate through the array and keep track of the count of 0s and 1s encountered so far.

• Use a hashmap to store the difference between the counts of 0s and 1s seen at each index.

• Increment the count of subarrays whenever the difference between the counts seen before matches the current difference.

Find the rectangle within a matrix with the greatest sum of elements.

• Iterate through all possible rectangles within the matrix and calculate their sums

• Use Kadane's algorithm to find the maximum sum subarray for each row combination

• Keep track of the maximum sum found so far

Find the minimum number in a rotated sorted array efficiently.

• Use binary search to find the minimum element in the rotated array.

• Compare mid element with the last element to determine which half to search.

• Adjust the search space based on the comparison to find the minimum element efficiently.

The task is to return the spiral path of elements in a given matrix.

• Iterate through the matrix in a spiral path by keeping track of boundaries.

• Print elements in the order of top, right, bottom, and left sides of the matrix.

• Handle cases where the matrix is not a square matrix separately.

• Consider edge cases like single row or single column matrices.

Reorder a singly linked list such that even-valued nodes appear before odd-valued nodes while preserving the original order.

• Create two separate linked lists for even and odd nodes.

• Traverse the original list and append nodes to their respective lists based on their values.

• Finally, merge the even list followed by the odd list to get the desired order.

Find the maximum GCD of a pair of elements in an array of positive integers.

• Iterate through all pairs of elements in the array to find their GCD.

• Keep track of the maximum GCD found so far.

• Use Euclidean algorithm to calculate GCD efficiently.

• Return the maximum GCD value found.

Find the distance between two nodes in a binary tree.

• Traverse the binary tree to find the paths from the root to each node.

• Find the lowest common ancestor of the two nodes.

• Calculate the distance by adding the distances from the nodes to the common ancestor.

The problem involves finding the length of the longest common subsequence between two given strings.

• Implement a function to find the longest common subsequence length between two strings.

• Use dynamic programming to solve the problem efficiently.

• Iterate through the strings and build a matrix to store the lengths of common subsequences.

• Return the value in the bottom-right cell of the matrix as the result.

Add two numbers represented by linked lists and return the head of the sum list.

• Traverse both linked lists simultaneously while keeping track of carry from previous sum

• Create a new linked list to store the sum of the two numbers

• Handle cases where one linked list is longer than the other by padding with zeros

• Update the sum and carry at each node while iterating through the linked lists

Given a sorted alien dictionary in an array of strings, determine the character order of the alien language.

• Iterate through the dictionary to build a graph of character dependencies.

• Perform a topological sort on the graph to determine the character order.

• Return the character array representing the order of characters in the alien language.

Given an array of unique binary strings representing integers from 0 to N, find and return the missing integer's binary representation.

• Iterate through the binary strings and convert them to integers.

• Calculate the sum of integers from 0 to N using the formula (N * (N + 1)) / 2.

• Subtract the sum of the integers in the array from the total sum to find the missing integer.

• Convert the missing integer to binary and return it as a string without leading zeros.

Diagonal traversal of a binary tree involves printing nodes at the same diagonal in a specific order.

• Traverse the tree in a diagonal manner, starting from the root node and moving towards the right child and then the left child.

• Use a queue to keep track of nodes at each level of the tree.

• Print the nodes in the order they are encountered while traversing the tree diagonally.

Check if a given singly linked list is a palindrome or not.

• Use two pointers approach to find the middle of the linked list

• Reverse the second half of the linked list

• Compare the first half with the reversed second half to determine if it's a palindrome

Find the length of the longest consecutive sequence in an unsorted array.

• Iterate through the array and store all elements in a set for constant time lookup.

• For each element, check if it is the start of a sequence by looking for previous consecutive elements in the set.

• Update the length of the current consecutive sequence and track the maximum length found so far.

• Return the maximum length as the result.

Print a specific pattern of '1's for a given number of rows 'N'.

• Read the number of test cases 'T'

• For each test case, read the number of rows 'N'

• Print '1' repeated i times for each line i from 1 to N

Construct a strict binary tree from preorder traversal and leaf/non-leaf indicators.

• Create a binary tree node class with value and left/right pointers.

• Use a stack to keep track of parent nodes while constructing the tree.

• Check if the current node is a leaf or non-leaf based on 'TYPENL' list.

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.

Find the majority element in an array, return -1 if no majority element exists.

• Iterate through the array and keep track of the count of each element using a hashmap.

• Check if any element's count is greater than floor(N/2) to determine the majority element.

• Return the majority element or -1 if no majority element exists.

Return the boundary nodes of a binary tree in Anti-Clockwise direction starting from the root node.

• Traverse the left boundary nodes in top-down order

• Traverse the leaf nodes in left-right order

• Traverse the right boundary nodes in bottom-up order

• Handle duplicates in boundary nodes by including them only once

Print the boundary nodes of a binary tree in an anti-clockwise direction starting from the root node.

• Traverse the left boundary nodes in a top-down manner

• Traverse the leaf nodes from left to right

• Traverse the right boundary nodes in a bottom-up manner

• Avoid duplicates while printing the boundary nodes

Sort an array in a wave-like pattern where each element is greater than or equal to its neighbors.

• Iterate through the array and swap elements to form the wave pattern.

• Start by sorting the array in non-decreasing order.

• Swap adjacent elements to form the wave pattern.

• Return the modified array as the output.

Given 'N' ropes of varying lengths, find the minimum cost to connect all ropes into one single rope.

• Sort the lengths of ropes in ascending order.

• Keep connecting the two shortest ropes at each step.

• Add the cost of connecting the two ropes to the total cost.

• Repeat until all ropes are connected.

• Return the total cost as the minimum cost to connect all ropes.

The task is to find the Next Greater Element (NGE) for each element in an array.

• Iterate through the array from right to left and use a stack to keep track of elements.

• For each element, pop elements from the stack until finding a greater element.

• Store the next greater element in a result array, if no greater element is found, store -1.

• Time complexity can be optimized to O(N) using a stack.

• Example: For input array [1, 3, 2], the output should be [3, -1, -1].

Find the longest path in a Directed Acyclic Graph (DAG) from a given source vertex.

• Use Topological Sorting to find the longest path in the DAG.

• Initialize distances to all vertices as minus infinite except the source vertex which is 0.

• Update distances of all adjacent vertices of the current vertex by considering the edge weight.

• Repeat the process until all vertices are visited and return the maximum distance found.

Given a string and an integer K, create a new string by selecting the smallest character from the first K characters of the input string and repeating the process until the input string is empty.

• Iterate through the input string while there are characters left

• For each iteration, select the smallest character from the first K characters

• Remove the selected character from the input string and append it to the new string

• Repeat until the input string is empty

• Output the final new st...read more

Delete the middle element from a stack to reduce its size by one.

• Identify the middle element based on whether the stack size is odd or even

• Remove the middle element from the stack

• Adjust the stack size to N by deleting the middle element

Allocate tanks to battalions to minimize maximum ratio of soldiers per tank.

• Calculate the ratio of soldiers to tanks for each battalion.

• Sort the ratios in ascending order.

• Return the maximum ratio from the sorted list.

Calculate the total amount of rainwater that can be trapped between given elevations in an array.

• Iterate through the array and calculate the maximum height on the left and right of each bar.

• Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.

• Sum up the trapped water at each bar to get the total trapped water for the entire array.

Search for integers in a rotated sorted array efficiently.

• Use binary search to efficiently search for each query in the rotated sorted array.

• Keep track of the mid element and adjust the search based on the rotation.

• Return the index of the query if found, else return -1.

Given a string, find the longest substring without repeating characters.

• Use a sliding window approach to keep track of the longest substring without repeating characters.

• Use a hashmap to store the index of each character as it appears in the string.

• Update the start index of the window when a repeating character is found.

• Keep track of the longest substring length and its starting index.

• Return the substring starting from the longest substring's starting index with the longest l...read more

Validate if a given binary tree is a Binary Search Tree (BST) or not.

• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Recursively check if both the left and right subtrees are also binary search trees.

• Example: For a tree with root 4, left subtree (2, 1, 3) < 4, right subtree (5) > 4.

Implement a Stack data structure using a Singly Linked List with operations in O(1) time.

• Create a class named Stack with getSize, isEmpty, push, pop, and getTop methods.

• Use a Singly Linked List to store the elements of the stack.

• Ensure each operation runs in O(1) time complexity.

• Handle edge cases like empty stack appropriately.

• Test the implementation with sample queries to verify correctness.

Merge overlapping intervals and return sorted list of merged intervals.

• Identify overlapping intervals based on start and end times

• Merge overlapping intervals to form new intervals

• Sort the merged intervals in ascending order of start times

The Josephus problem involves eliminating individuals in a circle until only one remains, based on a specific counting rule.

• Start counting from position 1, skip K-1 individuals, eliminate the Kth person, and continue until only one person remains.

• The position of the last surviving person can be determined based on the initial numbering and the value of K.

• Example: For N=5 and K=2, the last person standing is at position 3.

Given a matrix representing cells on fire or safe, determine if a person can reach an escape cell without stepping on fire.

• Check if the person can move to adjacent safe cells without stepping on fire

• If the person can reach an escape cell, return the time taken; otherwise, return -1

• Consider the constraints and note that escape cells are on matrix boundaries

Level order traversal of a binary tree is returned for each test case.

• Implement a function to perform level order traversal of a binary tree

• Use a queue data structure to keep track of nodes at each level

• Print the node values in level order traversal

The task is to modify a string by replacing minimum characters to remove all palindromic substrings.

• Identify palindromic substrings in the given string

• Replace characters in the string to remove palindromic substrings

• Count the minimum number of characters replaced

Find the least common ancestor of two nodes in a binary tree.

• Traverse the tree to find the paths from the root to each node, then compare the paths to find the LCA.

• Use recursion to traverse the tree efficiently and find the LCA.

• Handle cases where one or both nodes are not present in the tree by checking for NULL references.

• The LCA is the node where the paths to the two nodes diverge in the tree.

Detect cycle in a directed graph and return true if cycle exists, false otherwise.

• Use Depth First Search (DFS) to detect cycles in the directed graph.

• Maintain a visited array to keep track of visited vertices and a recursion stack to keep track of vertices in the current path.

• If a vertex is visited and is in the recursion stack, then a cycle exists.

• Return true if a cycle is found, false otherwise.

Calculate minimum steps for a Knight to reach target position on a chessboard.

• Use BFS algorithm to find shortest path from Knight's starting position to target position.

• Consider all possible moves of the Knight on the chessboard.

• Track visited positions to avoid revisiting them during traversal.

Count the total number of unique pairs in an array whose elements sum up to a given value.

• Use a hashmap to store the frequency of each element in the array.

• Iterate through the array and for each element, check if (Sum - current element) exists in the hashmap.

• Increment the count of pairs if the complement exists in the hashmap.

Zigzag level order traversal of a binary tree alternating directions at each level.

• Use a queue to perform level order traversal of the binary tree.

• Maintain a flag to alternate the direction of traversal at each level.

• Store nodes at each level in separate lists and reverse the list if traversal direction is right to left.

Given a 2D array, return a linear array storing elements in a 'wave' pattern.

• Read the array elements row-wise and store in wave pattern

• Alternate direction for storing elements from each row

• Handle edge cases like single row or single column arrays

• Use nested loops to iterate through the 2D array

Given preorder traversal and node type information, construct a strict binary tree and return the root node.

• Create a binary tree using preorder traversal and node type information

• Use recursion to construct the tree

• Handle leaf and non-leaf nodes separately

• Ensure each node has 0 or 2 children

Implement a function to delete N nodes after M nodes in a linked list.

• Traverse the linked list while retaining M nodes and deleting N nodes after each M nodes.

• Use two pointers to keep track of the nodes to be retained and deleted.

• Update the next pointers accordingly to skip the nodes to be deleted.

• Repeat the process until the end of the linked list is reached.

Print elements of a 2D array in a sine wave order.

• Traverse the array in a zigzag pattern, alternating between top to bottom and bottom to top for each column.

• Use two pointers to keep track of the current row and column while printing the elements.

• Handle edge cases such as empty arrays or arrays with only one row or column.

• Example: For input [[1, 2], [3, 4]], the output should be [1, 3, 2, 4].

Rearrange array elements to form the largest number possible by concatenating them.

• Sort the array elements in a custom way where the concatenation of two numbers results in a larger number.

• Use a custom comparator function to sort the array elements.

• Convert the sorted array elements to a single string to get the largest possible number.

Given a BST and a target value, find if there exists a pair of node values in the BST whose sum equals the target.

• Traverse the BST in-order to get a sorted array of node values.

• Use two pointers approach to find if there exists a pair summing up to the target value.

• Consider edge cases like negative numbers and duplicates in the BST.

Check if a permutation of a string can form a palindrome.

• Create a frequency map of characters in the string.

• Count the number of characters with odd frequencies.

• If there is at most one character with an odd frequency, the string can form a palindrome.

Find the remainder when a given number is divided by 11.

• Convert the string number to an integer for easier calculation.

• Use the property that the remainder when a number is divided by 11 is the same as the remainder when the alternating sum of its digits is divided by 11.

• Repeat the process until you get a single digit number as the result.

Implement a round-robin scheduling algorithm to determine completion time for each process.

• Implement a round-robin scheduling algorithm with the given time quantum.

• Execute processes based on arrival time and process ID if arrival times are the same.

• Calculate completion time for each process based on burst time and time quantum.

Given a string, partition it into palindromes and return all possible configurations.

• Use backtracking to generate all possible palindrome partitions

• Check if each substring is a palindrome before adding it to the partition

• Return all valid partitions as an array of strings

Count the number of groups of sizes 2 and 3 with sum divisible by 3 from a given list of integers.

• Iterate through the array and check all possible combinations of 2 and 3 integers.

• For each combination, check if the sum is divisible by 3.

• Keep track of the valid groups and return the count at the end.

Given a string with brackets, print the number associated with each bracket pair.

• Iterate through the string and maintain a stack to keep track of opening brackets

• Assign a number to each pair of opening and closing brackets

• Print the assigned numbers for each bracket pair

Return the K most frequent words from an array of words sorted by frequency.

• Use a hashmap to store word frequencies.

• Use a priority queue to keep track of the K most frequent words.

• Sort the words in the priority queue based on frequency and lexicographical order.

• Return the K most frequent words from the priority queue.

Calculate and print the median after each new integer is added to the stream.

• Use a min heap to store the larger half of the numbers and a max heap to store the smaller half.

• Keep the sizes of the two heaps balanced to efficiently calculate the median.

• If the total number of elements is odd, the median is the top element of the max heap.

• If the total number of elements is even, the median is the average of the top elements of both heaps.

Solve for the missing number 'x' in an equation involving addition of two numbers.

• Identify the summands and the result in the equation.

• Subtract the known summand from the result to find the missing number 'x'.

• Return the value of 'x' as the output.

ACID properties ensure database transactions are processed reliably and consistently.

• Atomicity: Ensures that either all operations in a transaction are completed successfully or none at all.

• Consistency: Ensures that the database remains in a valid state before and after the transaction.

• Isolation: Ensures that transactions are executed independently and do not interfere with each other.

• Durability: Ensures that once a transaction is committed, its changes are permanent and cann...read more

Use a hash set to store unique emails and remove duplicates from the data.

• Iterate through the array of emails

• For each email, check if it is already present in the hash set

• If not present, add it to the hash set

• If present, remove the duplicate entry from the data array

ACID properties are a set of properties that guarantee the reliability of transactions in a database management system.

• Atomicity: Ensures that either all operations in a transaction are completed successfully or none at all.

• Consistency: Ensures that the database remains in a consistent state before and after the transaction.

• Isolation: Ensures that the execution of multiple transactions concurrently does not interfere with each other.

• Durability: Ensures that once a transaction...read more

Implement a data structure to show the three last watched movies on Amazon Prime.

• Use an array data structure to store the last watched movies.

• Keep track of the order in which the movies were watched to display the most recent ones first.

• Update the array whenever a new movie is watched, shifting older movies to make room for the new ones.

Given a binary string, find zeroes to flip to maximize consecutive 1's.

• Iterate through the string and count the number of consecutive 1's.

• When a zero is encountered, calculate the length of the current consecutive 1's and store it.

• Flip the zero and continue counting consecutive 1's from the flipped position.

• Compare the lengths of consecutive 1's before and after flipping the zero.

• Return the position of the zero that maximizes the consecutive 1's.

• If there are multiple position...read more

Use Breadth First Search algorithm to find the shortest distance between 2 points in a matrix.

• Implement Breadth First Search algorithm to traverse the matrix

• Keep track of visited cells to avoid revisiting them

• Stop the search when the destination point is reached

ACID properties in DBMS ensure data integrity and consistency.

• Atomicity: All operations in a transaction are treated as a single unit of work. Either all operations are successfully completed or none are.

• Consistency: Database remains in a consistent state before and after the transaction. Constraints are enforced to maintain data integrity.

• Isolation: Transactions are executed independently without interference from other transactions. Ensures data integrity and prevents data ...read more

I have strong programming skills in Java and Python, but I struggle with time management and communication.

• Strong programming skills in Java and Python

• Experience with data structures and algorithms

• Struggle with time management and communication

Algorithm to find maximum profit by buying and selling a stock at most twice

• Find the maximum profit by buying and selling the stock once from left to right

• Find the maximum profit by buying and selling the stock once from right to left

• Add the two maximum profits obtained above to get the maximum profit by buying and selling the stock at most twice

Algorithm to find the first circular tour that visits all petrol pumps.

• Calculate the difference between petrol and distance at each pump

• If the difference is negative, start from the next pump

• If the total difference is positive, a circular tour is possible

• Start from the first pump with positive difference and complete the tour

• Use a queue to keep track of the pumps visited

Find pair of adjacent elements with largest product in an array of integers

• Iterate through the array and calculate the product of each pair of adjacent elements

• Keep track of the pair with the largest product as you iterate

• Return the largest product found

Sliding window problem where you can only pick fruits from two different baskets

• Use a sliding window approach to keep track of the maximum number of fruits in two baskets

• Keep track of the types of fruits and their counts in the window

• Update the window by removing fruits from the beginning and adding fruits from the end

• Keep track of the maximum number of fruits seen so far

Virtual memory is a memory management technique that allows a computer to compensate for physical memory shortages by temporarily transferring data from RAM to disk storage.

• Virtual memory allows programs to use more memory than is physically available on the system.

• It helps in running multiple programs simultaneously by allocating a portion of the hard drive as additional RAM.

• Virtual memory uses a combination of RAM and disk space to store data that may not be immediately nee...read more

BST stands for Binary Search Tree, a data structure used for efficient searching, insertion, and deletion operations.

• BST is a binary tree where each node has at most two children, referred to as the left child and the right child.

• The key in each node must be greater than all keys stored in the left subtree and less than all keys in the right subtree.

• Example: In a BST, the left child of a node contains keys less than the node's key, and the right child contains keys greater th...read more

Traverse a tree to display only nodes from the right side

• Start traversal from the root node

• Visit the right child node first before the left child node

• Use a stack or queue data structure for traversal

• Example: Inorder traversal with right child first

To find the n'th node from the end of a Linked List, use two pointers approach.

• Use two pointers, one moving n steps ahead of the other.

• When the first pointer reaches the end, the second pointer will be at the n'th node from the end.

• Handle edge cases like n being greater than the length of the Linked List.

Semaphores are synchronization primitives used to control access to shared resources in a multi-threaded environment.

• Semaphores can be used to limit the number of threads accessing a resource simultaneously.

• They can be binary (mutex) or counting semaphores.

• Operations on semaphores include wait (P) and signal (V).

• Example: In a producer-consumer problem, semaphores can be used to control access to a shared buffer.

Merge sort has a time complexity of O(n log n).

• Merge sort is a divide-and-conquer algorithm.

• It recursively divides the input array into two halves.

• Then it sorts each half and merges them back together.

• The time complexity is O(n log n) in all cases.

• It is a stable sorting algorithm and can handle large data sets efficiently.

Count the number of connected components in a grid

• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the grid

• Keep track of visited nodes to avoid revisiting them

• Each connected component will have its own set of connected nodes

Find the longest substring without repeating characters in a given string.

• Use a sliding window approach to keep track of the current substring without repeating characters.

• Use a hash set to store the characters in the current substring and check for duplicates.

• Update the start index of the window when a duplicate character is found to maintain the longest substring without repeating characters.

Finding the median of a data stream efficiently

• Use two heaps - a max heap to store the smaller half of the data and a min heap to store the larger half

• Keep the two heaps balanced by ensuring the size difference is at most 1

• If the total number of elements is odd, the median is the top element of the larger heap. If even, it's the average of the top elements of both heaps

Find the cousin of a node in a binary tree.

• Cousins are nodes at the same level but with different parents.

• Traverse the tree to find the level and parent of the given node.

• Traverse the tree again to find all nodes at the same level with different parents.

• Return the cousin node if found, else return null.

Reverse a given linked list

• Iteratively swap the next and previous pointers of each node

• Recursively swap the next and previous pointers of each node

• Use a stack to push each node and then pop them to create the reversed list

The diameter of a tree is the longest path between two nodes in a tree.

• Calculate the longest path between two leaf nodes in the tree.

• The diameter of a tree can be found by calculating the height of the left subtree, the height of the right subtree, and the sum of the heights plus 1 for the root node.

• Example: For the tree 1 -> 2 -> 3 -> 4, the diameter is 3 (from node 4 to node 2).

Moldy oranges

• Rotten oranges can develop mold due to the growth of fungi on their surface

• Moldy oranges are not safe to eat and should be discarded

• The presence of mold on oranges can indicate spoilage and decay

Find the minimum sum of a subarray within an array of integers.

• Iterate through the array and keep track of the current sum of subarray

• Update the minimum sum if a smaller sum is found

• Consider using Kadane's algorithm for an efficient solution

Two-pointer technique is used to solve problems involving arrays or linked lists by using two pointers to traverse the data structure.

• Start with two pointers at different positions in the array or linked list

• Move the pointers based on the problem requirements (e.g. one pointer moves faster than the other)

• Commonly used in problems like finding a pair of elements that sum up to a target value