Cracking the top Amazon coding interview questions

View the find the missing number solution in C++, Java, JavaScript, and Ruby.

A naive solution is to simply search for every integer between 1 and n in the input array, stopping the search as soon as there is a missing number. However we can do better. Here is a linear, $O(n)$, solution that uses the arithmetic series sum formula.​​  Follow the steps below to find the missing number:

• Find the sum sum_of_elements of all the numbers in the array.

• Then, find the sum actual_sum of the first n numbers using the arithmetic series sum formula $n(n+1)/2$.

• The difference between these, i.e., actual_sum - sum_of_elements, is the missing number in the array.

Runtime complexity: Linear, $𝑂(𝑛)$

Memory complexity: Constant, $𝑂(1)$

View the sum of two integers solution in C++, Java, JavaScript, and Ruby.

We can use the following algorithm to find a pair that adds up to target.

• Scan the whole array once and store visited elements in a hash set.

• During the scan, for every element num in the array, we check if target - num is present in the hash set, i.e., target - num is already visited.

• If target - num is found in the hash set, it means there is a pair (num, target - num) in the array whose sum is equal to the given target, so we return TRUE.

• If we have exhausted all elements in the array and found no such pair, the function will return FALSE.

Runtime complexity: Linear, $O(n)$

Memory complexity: Linear, $O(n)$

View the merge two sorted linked lists solution in C++, Java, JavaScript, and Ruby.

Given that head1 and head2 are pointing to the head nodes of the given linked lists, respectively, if one of them is None, return the other as the merged list. Otherwise, perform the following steps:

1. Compare the data of the first nodes of both lists and initialize the merged_head to the smaller of the two nodes. Also, initialize merged_tail as merged_head. Move the smaller node pointer (head1 or head2) to the next node.

2. Perform the following steps until either head1 or head2 is NULL:

   1. Compare the data of the current nodes pointed by head1 and head2, append the smaller node to merged_tail, and move the corresponding pointer forward.

   2. Update merged_tail to the appended node.

3. After exiting the loop, if either list has remaining nodes, append the remaining nodes to the end of the merged list. Do this by updating the next pointer of merged_tail to point to the remaining nodes.

4. Return merged_head, which represents the head of the merged list.

Runtime complexity: Linear, $𝑂(𝑚+𝑛)$, where $m$ and $n$ are lengths of both linked lists.

Memory complexity: Constant, $𝑂(1)$

View the copy linked list solution in C++, Java, JavaScript, and Ruby.

1. If the given linked list’s head is NULL, return NULL as the copied list.

2. Initialize a current pointer with head to traverse the original linked list. Also, initialize new_head and new_prev pointers to NULL to keep track of the copied list. Additionally, create an empty dictionary (hashmap) named ht to map nodes in the original and copied lists.

3. Traverse the original linked list while creating a copy of each node. For each node:

   1. Create a new_node with the same data as the current node.

   2. Copy the arbitrary pointer of the current node to the new_node. Therefore, for now, we are pointing the arbitrary pointer of the new_node to where it is pointing in the original node.

   3. If new_node is the first node in the copied list, set new_head and new_prev to new_node. Otherwise, connect the new_node to the copied list by setting new_prev.next to new_node and set new_prev to new_node.

   4. Store copied node new_node in the ht with the key current. This will help us point the arbitrary pointer of the copied nodes to the correct new nodes in the copied list.

4. For now, the arbitrary pointers in the new nodes point to nodes in the original list. To update them, we traverse the new list using new_current, utilize the hashmap ht to find the corresponding copied node for each original node pointed to by the arbitrary pointer, and then update the arbitrary pointer of the current node to point to this copied node.

5. Once all arbitrary pointers are updated, return new_head, which represents the head of the copied list.

Runtime complexity: Linear, $O(n)$

Memory complexity: Linear, $O(n)$

View the level order traversal of binary tree solution in C++, Java, JavaScript, and Ruby.

1. Initialize a queue, queue, with the root node.

2. Iterate over the queue until it’s empty:

   1. For each level, calculate the size (level_size) of the queue.

   2. Initialize an empty list level_nodes.

   3. Iterate level_size times:

      1. Dequeue a node from the queue.

      2. Append the value of the dequeued node in level_nodes.

      3. Enqueue the left child and the right child of the dequeued node in queue, if they exist.

   4. Convert level_nodes to a comma-separated string and store it in result.

3. Return the result.

Runtime complexity: Linear, $O(n)$

Memory complexity: Linear, $O(n)$

View the binary tree solution in C++, Java, JavaScript, and Ruby.

We use a recursive method to explore the binary tree while keeping track of the allowed range for each node’s value. At the start, the root node’s value can be any number. As we go down the tree, we adjust this range. For a left child, the value must be smaller than its parent’s value. For a right child, the value must be larger than its parent’s value. By doing this, we make sure that each node’s value is within the acceptable range set by its parent. If we find any node with a value outside this range, it means the tree doesn’t follow the rules of a binary search tree and is not valid as a BST.

Define a recursive function is_bst_rec that takes a node, min_val, and max_val as parameters.

Inside the function:

1. Check if the node is NULL. If so, return TRUE.

2. Verify if the current node’s value node.val lies within the acceptable range defined by min_val (exclusive) and max_val (exclusive). If not, return FALSE.

3. Recursively call is_valid for the left subtree with the updated max_val as the current node’s value and for the right subtree with the updated min_val as the current node’s value.

Initialize the range by calling is_bst_rec with the root node, setting min_val to negative infinity and max_val to positive infinity.

Runtime complexity: Linear, $O(n)$

Memory complexity: Linear, $O(n)$

View the string segmentation solution in C++, Java, JavaScript, and Ruby.

The algorithm iteratively checks substrings of the input string against the dictionary. Starting with an empty string being segmentable, it gradually builds up segmentability information for larger substrings by considering all possible substrings and checking if they exist in the dictionary. Once we determine that a substring can be segmented into words from the dictionary, we mark the corresponding entry in an array dp array as TRUE. Subsequently, when processing longer substrings, we use dp to check whether shorter substrings within them have already been determined to be segmentable, avoiding recomputations.

1. Initialize a variable n with the length of the input word and create a boolean array dp with a size of n + 1. Initialize all values of dp to FALSE.

2. Set dp[0] to TRUE to indicate that the empty string can be segmented.

3. Iterate over the indexes of the word from 1 to n.

4. For each index i, iterate over the indexes j from 0 to i - 1.

   1. Check if dp[j] is TRUE and if the substring word[j:i] exists in the dictionary.

   2. If both conditions are met, set dp[i] to TRUE.

5. After completing the iterations, return dp[n] to indicate whether the entire word can be segmented.

Runtime complexity: Polynomial, $O(n^3)$

Memory complexity: Linear, $O(n)$

View the reverse words in a sentence solution in C++, Java, JavaScript, and Ruby.

The essence of this algorithm is to reverse the words in a string by a two-step method using two pointers, effectively manipulating the string in place. Initially, the entire string is reversed, which correctly repositions the words in reverse order. However, due to this reversal of the string, the corresponding characters of words are also reversed. To correct the order of the characters, iterate through the string, and identify the start and end of each word, considering space as a delimiter between words. Set two pointers at the start and end of the word to reverse the characters within that word. By repeating this process for each word, the method effectively achieves the goal without requiring additional memory.

1. Convert the string, sentence, into a list of characters and store it back in sentence.

2. Get the length of the sentence and store it in str_len.

3. Define a str_rev function to reverse the entire list of characters sentence.

4. Set the start pointer start to 0 and iterate over the range from 0 to str_len + 1 using the pointer end.

   1. When encountering a space or reaching the end of a word, reverse the characters of the word using the str_rev function with sentence, start, and end - 1 as arguments.

   2. Update the start pointer start to end + 1.

5. Join the list of characters back into a string using join(sentence).

6. Return the reversed string.

Runtime complexity: Linear, $O(n)$

Memory complexity: Constant, $O(1)$

View the coin changing problem solution in C++, Java, JavaScript, and Ruby.

We can use dynamic programming to build simple coin change solutions, store them, and utilize them in larger coin change amounts. We start by considering the simplest case, which is making change for an amount of zero. At this stage, there’s only one way to make a change, which is by using no coins. Then, we proceed to compute the number of ways to make change for larger amounts by considering each coin denomination one by one. For each denomination, we iterate through the possible amounts starting from the denomination value up to the target amount. At each step, we update the count of ways to make change for the current amount by incorporating the count for smaller amounts. This iterative process ensures that we exhaustively explore all valid combinations of coins, leading to an accurate count of the total number of ways to make change for the target amount.

• Initialize an array dp of size (amount + 1) to track the number of ways to make change.

• Set dp[0] = 1 to denote the one way to make change for an amount of zero.

• Iterate through each coin denomination:

  • For each denomination den, iterate from den to amount.

  • Update dp[i] by adding dp[i - den] to account for the current denomination.

• After processing all denominations and amounts, dp[amount] holds the total number of ways to make change.

Runtime complexity: Quadratic, $𝑂(𝑚∗𝑛)$

Memory complexity: Linear, $𝑂(𝑛)$

View the find Kth permutation solution in C++, Java, JavaScript, and Ruby.

We can divide all possible permutations into blocks, where each block represents a group of permutations sharing the same first element, and determine which block the target permutation belongs to by dividing the target position by the number of permutations within each block (block size).

Next, we can determine the first element of the permutation, based on the block’s position within all permutations and add it to our result. We also remove the selected element from the original set of elements to prevent duplication in the permutation.

Now, we can repeat the same process to find the remaining elements of the required permutation using the now reduced set of elements. We skipped the $block\_size * \# of blocks$ we passed over. This tells us how many permutations we’ve missed. So, within the chosen block, we’re now looking for the $(k - skipped permutations)th$ permutation. We can adjust k this way and repeat the same process on the updated, smaller block of numbers.

To implement the algorithm:

1. Start by defining a function called find_kth_permutation. This takes three parameters: v (the input list), k (the target position), and result (the result string).

2. Check if v is empty. If so, return.

3. Calculate the number of permutations starting with the first digit of v and store it in count. This is done by computing the factorial of (n - 1) using the function factorial, where n is the length of v .

4. Determine the target block by dividing k-1 by the number of blocks count and save in selected.

5. Add the selected element v[selected] to result, and remove it from v.

6. Update k to reflect the remaining permutations by subtracting count multiplied by selected from k.

7. Recursively call the function with the updated parameters until v is empty or k is 0.

Runtime complexity: Quadratic, $𝑂(𝑛^2)$

Memory complexity: Linear, $O(n)$

View the find all subsets solution in C++, Java, JavaScript, and Ruby.

Instead of using nested loops to generate all possible combinations, this algorithm employs binary representation to efficiently derive all subsets of a given set. There are $2^n$ subsets, where$n$ represents the size of the original set. The algorithm decodes the binary representation of each number, ranging from $0$ to $2^n-1$, determining which elements to include or exclude in the subsets. It makes this decision by examining each bit of the binary representation, where a 1 indicates inclusion and a 0 indicates exclusion of the corresponding element.

To implement the algorithm:

1. Calculate the total number of subsets subsets_count, which is $2^n$.

2. Iterate through numbers from 0 to subsets_count - 1 using a for loop.

   1. Inside the loop, create an empty set called st to store the current subset.

   2. Iterate through each index j of the input list nums using another for loop.

      1. Write and use the function get_bit to determine whether the jth bit of the current number i is set to 1 or 0.

      2. If the jth bit of i is 1, add the corresponding element from nums to the current subset st.

   3. After iterating through all indexes of nums, append the current subset st to the list sets.

Runtime complexity: Exponential, $𝑂(2^𝑛∗𝑛)$

Memory complexity: Exponential, $𝑂(2^𝑛∗𝑛)$

View the print balanced brace combinations solution in C++, Java, JavaScript, and Ruby.

The algorithm has the following main points:

1. Adding parentheses:

   1. Determine whether to add a left parenthesis “{” or a right parenthesis “}” based on certain conditions:

      1. If the count of left parentheses (left_count) is less than n, a left parenthesis can be added to make a valid combination.

      2. If the count of right parentheses (right_count) is less than the count of left parentheses (left_count), a right parenthesis can be added to make a valid combination.

2. Constructing the result: As the algorithm explores different combinations of parentheses, when left_count and right_count both reach n, indicating that n pairs of parentheses have been added and the combination is complete, it appends the current combination present in the output list to the result list.

3. Backtracking:

   1. After exploring a possible path by adding a parenthesis and making recursive calls, the algorithm backtracks to explore other possible combinations.

   2. Backtracking involves removing the last added parenthesis from the output list using the pop operation.

   3. This reverts the output list to its state before the current recursive call, allowing the algorithm to explore other possible combinations without missing any.

To implement the algorithm:

1. Initialize an empty list output to store the current combination and an empty list result to store all valid combinations.

2. Define a print_all_braces_rec function with parameters n (the total number of pairs), left_count, right_count, output, and result.

3. Inside print_all_braces_rec:

   1. Check if both left_count and right_count are greater than or equal to n. If TRUE, append a copy of output to result.

   2. If left_count is less than n, add a left parenthesis { to output, and recursively call print_all_braces_rec with n, left_count + 1, right_count, output, and result.

   3. After the recursive call, remove (pop) the last element from output to backtrack.

   4. If right_count is less than left_count, add a right parenthesis } to output, and recursively call print_all_braces_rec with n, left_count, right_count + 1, output, and result.

   5. After the recursive call, remove (pop) the last element from output to backtrack.

4. Return the result list containing all valid combinations of well-formed parentheses pairs for the given n.

Runtime complexity: Exponential, $O(2^n)$

Memory complexity: Linear, $O(n)$

View the clone a directed graph solution in C++, Java, JavaScript, and Ruby.

This algorithm clones a directed graph by traversing it recursively. It creates a new node for each encountered node, replicates its data, and traverses its neighbors. If a neighbor has already been cloned, it uses the existing clone; otherwise, it recursively clones the neighbor. This process continues until all nodes and their relationships are replicated, resulting in a deep copy of the original graph.

To implement the algorithm:

1. Initialize an empty dictionary called nodes_completed to keep track of cloned nodes.

2. Write clone_rec function, which takes root node of the original graph and the nodes_completed dictionary as parameters. Inside the function:

   1. If the root node is None, return None.

   2. Otherwise, create a new node p_new with the same data as the root and add it to the nodes_completed dictionary to mark it as visited.

   3. Iterate through each neighbor p of the root node:

      1. If the neighbor p has not been cloned yet (i.e., not present in nodes_completed), recursively call clone_rec with p and nodes_completed, and add the clone to the neighbors list of p_new.

      2. If the neighbor p has already been cloned, retrieve the clone x from nodes_completed and add it to the neighbors list of p_new.

3. Call clone_rec and pass root and nodes_completed as parameters. When its recursion completes, return the cloned graph rooted at p_new.

Runtime complexity: Linear, $O(n)$

Memory complexity: Linear, $O(n)$

View the find low/high index solution in C++, Java, JavaScript, and Ruby.

We can modify the binary search algorithm to find the first occurrence of the key by narrowing down the search range even if the value at the mid is equal to the key. The algorithm is designed to always move to the left whenever it encounters an element that’s equal to or greater than the target. So, when the search range is narrowed down to a single element, and that element matches the target, it means that this is the leftmost occurrence of the target element in the array. Similarly, to find the last occurrence of a key, we adjust the search range toward the right whenever the middle element is less than or equal to the key. This iterative process continues until the search range narrows down to a single element. At this point, either the last occurrence of the key is found, or it confirms the absence of the key in the array.

To implement the algorithm:

1. Initialize low to 0, high to the length of the array minus one, and mid to high / 2.

2. Enter a while loop that continues while low is less than or equal to high.

   1. Inside the loop, set mid_elem to arr[mid]

   2. Compare mid_elem with the key:

      1. If mid_elem is less than the key, update low to mid + 1.

      2. Otherwise, update high to mid - 1.

   3. Update mid to low + (high - low) / 2.

3. After the loop, check if low is within the bounds of the array and if the element at index low equals the key. If so, return low. Otherwise, return -1.

Repeat the same steps to find the last occurrence, with the only difference being in the comparison step. If mid_elem is less than or equal to the key, update low to mid + 1; and if it’s greater than the key, update high to mid - 1.

Runtime complexity: Logarithmic, $O(logn)$

Memory complexity: Constant, $O(1)$

View the search rotated array solution in C++, Java, JavaScript, and Ruby.

To tackle rotation in a binary search for a rotated array, we adjust the search range based on the middle element’s comparisons as follows:

1. If the element at the middle index matches the target, return the index of the middle element, as the target has been found.

2. If the element at the middle index is greater than or equal to the element at the start index, it implies that the left subarray (from the start to the middle) is sorted:

   1. Now, check if the target falls within the range of elements from the leftmost element to the middle element. If it does, adjust the search range to focus on the left subarray.

   2. Otherwise, adjust the search range to focus on the right subarray.

3. If the element at the middle index is less than the element at the end index, it indicates that the right subarray (from the middle to the end) is sorted:

   1. Check if the target falls within the range of elements from the middle element to the rightmost element. If it does, adjust the search range to focus on the right subarray.

   2. Otherwise, adjust the search range to focus on the left subarray.

To implement the algorithm:

1. Initialize low to 0 and high to the length of the array minus one.

2. Enter a while loop that continues while low is less than or equal to high.

   1. Inside the loop, calculate mid using the formula low + (high - low) // 2.

   2. Check if the element at the middle index matches the target. If it does, return the index of the middle element.

   3. If arr[low] is less than or equal to arr[mid], it implies that the left subarray (from low to mid) is sorted:

      1. If the target falls within this range, update the high to mid - 1. Otherwise, update the low to mid + 1.

   4. Otherwise, it’s obvious that arr[low] is greater than arr[mid], which it indicates that the right subarray (from mid to high) is sorted:

      1. If the target falls within this range, update the low to mid + 1. Otherwise, update the high to mid - 1.

   5. If the target is not found after the loop, return -1 to indicate its absence in the array.

Runtime complexity: Logarithmic, $O(logn)$

Memory complexity: Constant, $O(1)$

Amazon Software Engineer Interview#

Amazon is one of the top tech companies worldwide, and the company focuses on hiring only the best talent. Securing a software engineer position at Amazon is not a piece of cake, but with the right guidance, content, and practice questions, you can ace the Amazon software engineer interview.

Amazon software engineer interviews consist of four rounds. A major part of these four interview rounds involves technical interview questions. That is why having a solid grasp of computing fundamentals is crucial. Questions related to arrays, linked lists, strings, dynamic programming, and system design are common. We have mentioned some of the commonly asked questions above, so have a look and practice them thoroughly. For more interview prep questions, you can try Educative-99, created to help software engineers secure a job at top tech companies.

Besides technical questions, Amazon software engineer interviews also include behavioral questions. Amazon ensures that candidates are the right fit for the company culture, which is why you’ll be asked several behavioral questions as well. The cornerstone of Amazon’s culture is its 14 Leadership Principles. These principles, which include notions like “Customer Obsession,” “Ownership,” and “Bias for Action,” guide every decision the company makes, from high-level strategies to everyday interactions.

This dual approach to assessing candidates ensures that Amazon software engineers can solve complex technical challenges, collaborate effectively, handle difficult situations, and adapt to the company’s fast-paced environment. Hence, candidates must prepare themselves for both technical and behavioral challenges.