Cracking the top Amazon coding interview questions

45 common Amazon coding interview questions

1. Find the missing number in the array

You are given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one number x. You have to find x. The input array is not sorted. Look at the below array and give it a try before checking the solution.

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Constant, $O(1)$

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. But we can do better. Here is a linear, $O(n)$, solution that uses the arithmetic series sum formula.​​ Here are the steps to find the missing number:

• Find the sum sum_of_elements of all the numbers in the array. This would require a linear scan, $O(n)$.
• Then find the sum expected_sum of first n numbers using the arithmetic series sum formula
• The difference between these i.e. expected_sum - sum_of_elements, is the missing number in the array.

2. Determine if the sum of two integers is equal to the given value

Given an array of integers and a value, determine if there are any two integers in the array whose sum is equal to the given value. Return true if the sum exists and return false if it does not. Consider this array and the target sums:

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Linear, $O(n)$

You can use the following algorithm to find a pair that add up to the target (say val).

• Scan the whole array once and store visited elements in a hash set.
• During scan, for every element e in the array, we check if val - e is present in the hash set i.e. val - e is already visited.
• If val - e is found in the hash set, it means there is a pair (e, val - e) in array whose sum is equal to the given val.
• If we have exhausted all elements in the array and didn’t find any such pair, the function will return false

Given two sorted linked lists, merge them so that the resulting linked list is also sorted. Consider two sorted linked lists and the merged list below them as an example.

Runtime Complexity: Linear, $O(m + n)$ where m and n are lengths of both linked lists

Memory Complexity: Constant, $O(1)$

Maintain a head and a tail pointer on the merged linked list. Then choose the head of the merged linked list by comparing the first node of both linked lists. For all subsequent nodes in both lists, you choose the smaller current node and link it to the tail of the merged list, and moving the current pointer of that list one step forward.

Continue this while there are some remaining elements in both the lists. If there are still some elements in only one of the lists, you link this remaining list to the tail of the merged list. Initially, the merged linked list is NULL.

Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list. In this example, it is 4 from head1. Since it’s the first and only node in the merged list, it will also be the tail. Then move head1 one step forward.

4. Copy linked list with arbitrary pointer

You are given a linked list where the node has two pointers. The first is the regular next pointer. The second pointer is called arbitrary_pointer and it can point to any node in the linked list. Your job is to write code to make a deep copy of the given linked list. Here, deep copy means that any operations on the original list should not affect the copied list.

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Linear, $O(n)$

This approach uses a map to track arbitrary nodes pointed by the original list. You will create a deep copy of the original linked list (say list_orig) in two passes.

• In the first pass, create a copy of the original linked list. While creating this copy, use the same values for data and arbitrary_pointer in the new list. Also, keep updating the map with entries where the key is the address to the old node and the value is the address of the new node.
• Once the copy has been created, do another pass on the copied linked list and update arbitrary pointers to the new address using the map created in the first pass.

5. Level Order Traversal of Binary Tree

Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Linear, $O(n)$

Here, you are using two queues: current_queue and next_queue. You push the nodes in both queues alternately based on the current level number.

You’ll dequeue nodes from the current_queue, print the node’s data, and enqueue the node’s children to the next_queue. Once the current_queue becomes empty, you have processed all nodes for the current level_number. To indicate the new level, print a line break (\n), swap the two queues, and continue with the above-mentioned logic.

After printing the leaf nodes from the current_queue, swap current_queue and next_queue. Since the current_queue would be empty, you can terminate the loop.

Given a Binary Tree, figure out whether it’s a Binary Search Tree. In a binary search tree, each node’s key value is smaller than the key value of all nodes in the right subtree, and is greater than the key values of all nodes in the left subtree. Below is an example of a binary tree that is a valid BST.

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Linear, $O(n)$

There are several ways of solving this problem. A basic algorithm would be to check on each node where the maximum value of its left sub-tree is less than the node’s data and the minimum value of its right sub-tree is greater than the node’s data. This is highly inefficient as for each node, both of its left and right sub-trees are explored.

Another approach would be to do a regular in-order traversal and in each recursive call, pass maximum and minimum bounds to check whether the current node’s value is within the given bounds.

You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following two examples elaborate on the problem further.

Given a dictionary of words.

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

Memory Complexity: Polynomial, $O(n^2)$

You can solve this problem by segmenting the large string at each possible position to see if the string can be completely segmented to words in the dictionary. If you write the algorithm in steps it will be as follows:

n = length of input string
for i = 0 to n - 1
  first_word = substring (input string from index [0, i] )
  second_word = substring (input string from index [i + 1, n - 1] )
  if dictionary has first_word
    if second_word is in dictionary OR second_word is of zero length, then return true
    recursively call this method with second_word as input and return true if it can be segmented

The algorithm will compute two strings from scratch in each iteration of the loop. Worst case scenario, there would be a recursive call of the second_word each time. This shoots the time complexity up to $2^n$.

You can see that you may be computing the same substring multiple times, even if it doesn’t exist in the dictionary. This redundancy can be fixed by memoization, where you remember which substrings have already been solved.

To achieve memoization, you can store the second string in a new set each time. This will reduce both time and memory complexities.

Reverse the order of words in a given sentence (an array of characters).

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Constant, $O(1)$

The steps to solve this problem are simpler than they seem:

• Reverse the string.
• Traverse the string and reverse each word in place.

Suppose we have coin denominations of [1, 2, 5] and the total amount is 7. We can make changes in the following 6 ways:

Runtime Complexity: Quadratic, $O(m*n)$

Memory Complexity: Linear, $O(n)$

To solve this problem, we’ll keep an array of size amount + 1. One additional space is reserved because we also want to store the solution for the 0 amount.

There is only one way you can make a change of 0, i.e., select no coin so we’ll initialize solution[0] = 1. We’ll solve the problem for each amount, denomination to amount, using coins up to a denomination, den.

The results of different denominations should be stored in the array solution. The solution for amount x using a denomination den will then be:

solution[x] = solution[x] + solution[x - den]

We’ll repeat this process for all the denominations, and at the last element of the solution array, we will have the solution.

10. Find Kth permutation

Given a set of ‘n’ elements, find their Kth permutation. Consider the following set of elements:

Here we need to find the Kth permutation.

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Linear, $O(n)$

Here is the algorithm that we will follow:

If input vector is empty return result vector
 
block_size = (n-1)! ['n' is the size of vector]

Figure out which block k will lie in and select the first element of that block
(this can be done by doing (k-1)/block_size)
 
Append selected element to result vector and remove it from original input vector
 
Deduce from k the blocks that are skipped i.e k = k - selected*block_size and goto step 1

We are given a set of integers and we have to find all the possible subsets of this set of integers. The following example elaborates on this further.

Given set of integers:

Runtime Complexity: Exponential, $O(2^n*n)$

Memory Complexity: Exponential, $O(2^n*n)$

There are several ways to solve this problem. We will discuss the one that is neat and easier to understand. We know that for a set of n elements there are $2^n$ subsets. For example, a set with 3 elements will have 8 subsets. Here is the algorithm we will use:

n = size of given integer set
subsets_count = 2^n
for i = 0 to subsets_count
    form a subset using the value of 'i' as following:
        bits in number 'i' represent index of elements to choose from original set,
        if a specific bit is 1 choose that number from original set and add it to current subset,
        e.g. if i = 6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
    add current subset to list of all subsets

12. Print balanced brace combinations

Print all braces combinations for a given value n so that they are balanced. For this solution, we will be using recursion.

Runtime Complexity: Exponential, $2^n$

Memory Complexity: Linear, $O(n)$

The solution is to maintain counts of left_braces and right_braces. The basic algorithm is as follows:​

left_braces count: 0
right_braces count: 0
 
if left_braces count is less than n:
  add left_braces and recurse further
if right_braces count is less than left_braces count:
  add right_braces and recurse further
stop recursing when left_braces and right_braces counts are both equal to n

13. Clone a Directed Graph

Given the root node of a directed graph, clone this graph by creating its deep copy so that the cloned graph has the same vertices and edges as the original graph.

Let’s look at the below graphs as an example. If the input graph is $G = (V, E)$ where V is set of vertices and E is set of edges, then the output graph (cloned graph) G’ = (V’, E’) such that V = V’ and E = E’. We are assuming that all vertices are reachable from the root vertex, i.e. we have a connected graph.

Runtime Complexity: Linear, $O(n)$

Memory Complexity: Logarithmic, $O(logn)$

We use depth-first traversal and create a copy of each node while traversing the graph. To avoid getting stuck in cycles, we’ll use a hashtable to store each completed node and will not revisit nodes that exist in the hashtable. The hashtable key will be a node in the original graph, and its value will be the corresponding node in the cloned graph.

Given a sorted array of integers, return the low and high index of the given key. You must return -1 if the indexes are not found. The array length can be in the millions with many duplicates.

In the following example, according to the key, the low and high indices would be:

• key: 1, low = 0 and high = 0
• key: 2, low = 1 and high = 1
• key: 5, low = 2 and high = 9
• key: 20, low = 10 and high = 10

For the testing of your code, the input array will be:

1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6

Runtime Complexity: Logarithmic, $O(logn)$

Memory Complexity: Constant, $O(1)$

Linearly scanning the sorted array for low and high indices are highly inefficient since our array size can be in millions. Instead, we will use a slightly modified binary search to find the low and high indices of a given key. We need to do binary search twice: once for finding the low index, once for finding the high index.

Let’s look at the algorithm for finding the low index. At every step, consider the array between low and high indices and calculate the mid index.

• If the element at mid index is less than the key, low becomes mid + 1 (to move towards the start of range).
• If the element at mid is greater or equal to the key, the high becomes mid - 1. Index at low remains the same.
• When low is greater than high, low would be pointing to the first occurrence of the key.
• If the element at low does not match the key, return -1.

Similarly, we can find the high index by slightly modifying the above condition:

• Switch the low index to mid + 1 when element at mid index is less than or equal to the key.
• Switch the high index to mid - 1 when the element at mid is greater than the key.

Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number. Return -1 if the number does not exist. Assume that the array does not contain duplicates.

Runtime Complexity: Logarithmic, $O(logn)$

Memory Complexity: Logarithmic, $O(logn)$

The solution is essentially a binary search but with some modifications. If we look at the array in the example closely, we notice that at least one half of the array is always sorted. We can use this property to our advantage. If the number n lies within the sorted half of the array, then our problem is a basic binary search. Otherwise, discard the sorted half and keep examining the unsorted half. Since we are partitioning the array in half at each step, this gives us $O(log n)$ runtime complexity.

Overview of Amazon coding interview

To land a software engineering job at Amazon, you need to know what lies ahead. The more prepared you are, the more confident you will be. So, let’s break it down.

• Interview Timeline: The whole interview process takes 6 to 8 weeks to complete.

• Types of Interviews: Amazon coding interviews consist of 5 to 7 interviews. This includes 1 assessment for fit and aptitude, 1-2 online tests, and 4-6 on-site interviews, also known as The Loop.

• The Loop: The onsite interviews include 1 to 3 interviews with hiring managers and 1 bar raiser interview to evaluate Amazon’s 14 leadership principles.

• Coding Questions: Amazon programming questions focus on algorithms, data structures, puzzles, and more.

• Hiring Levels: Amazon usually hires at entry-level 4 (out of 12 total), and the average salary for that level ranges from $106,000 to $114,000 yearly.

• Hiring Teams: Amazon hires based on teams. The most common hiring teams are Alexa and AWS.

• Programming Languages: Amazon prefers the following programming languages for coding questions: Java, C++, Python, Ruby, and Perl.

Amazon’s 14 leadership principles

Though coding interviews at Amazon are similar to other big tech companies, there are a few differences in their process, in particular, the Bar Raiser. Amazon brings in an objective third-party interviewer called a Bar Raiser, who evaluates candidates on Amazon’s 14 Leadership Principles. The Bar Raiser has complete veto power over whether or not you will be hired.

It is unlikely that you will know which of your interviewers is the Bar Raiser. The key is to take every part of the interview seriously and always assume you’re being evaluated for cultural fit as well as technical competency.

Below are the 14 values that you will be evaluated on.