Home/Blog/Interview Prep/Cracking the top Amazon coding interview questions
Home/Blog/Interview Prep/Cracking the top Amazon coding interview questions

Cracking the top Amazon coding interview questions

Amanda Fawcett
May 27, 2024
37 min read

Landing a job at Amazon is a dream for many developers around the globe. Amazon is one of the largest companies in the world, with a workforce of over half a million strong.

For you to join them, you’ll need to complete their unique interview that combines technical and leadership knowledge.

Today, we’ll walk you through everything you need to crack the Amazon technical interview, including questions and answers for coding problems and a step-by-step tech interview prep guide.

Amazon Leetcode Questions#

Amazon is a dream company for many developers. To get yourself a job at Amazon, the most important part is to practice your interview skills and apply for the correct position. Make sure you thoroughly look at the job description to ensure that it matches your skill set. The next step is to practice some Amazon Leetcode Questions. Solving Leetcode problems is an exceptional way to practice your coding skills.

Educative has curated a collection of Amazon-specific LeetCode problems to facilitate focused practice. There’s no need to feel overwhelmed by the vast array of over 2000+ LeetCode problems. With this select set, you can practice and develop the logic necessary to tackle all the coding problems typically encountered in Amazon interviews. We’veve also added 40+ commonly asked Amazon coding interview questions for you to practice and improve your skills. For detailed lists of questions curated to help you ace the Amazon coding interviews, Educative-99 and Educative-77 are the perfect places to start.


45 common Amazon technical 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.

%0 node_1592256077325 3 node_1592255996586 7 node_1592255998192 1 node_1592256032162 2 node_1 8 node_2 4 node_3 5
n = 8 missing number = 6
def find_missing(nums):
# Replace this placeholder return statement with your code
return -1

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)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)/2n(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)𝑂(1)

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:

%0 node_1592256164418 5 node_1592256069696 7 node_1592256107658 1 node_1592256151353 2 node_1 8 node_2 4 node_3 3
%0 node_1 Target Sum node_2 10 node_3 7+3=10, 2+8=10
%0 node_1 Target Sum node_2 19 node_3 No 2 values sum up to 19
sum of two integers
def check_two_sum(arr, t):
# Replace this placeholder return statement with your code
return False

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 (numtarget - 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)O(n)

Memory complexity: Linear, O(n)O(n)

3. Merge two sorted linked lists#

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.

%0 node_1 head1 node_2 4 node_1->node_2 node_3 8 node_2->node_3 node_1592253395443 15 node_3->node_1592253395443 node_1592253478417 19 node_1592253395443->node_1592253478417 node_1592253525413 NULL node_1592253478417->node_1592253525413
%0 node_1 head2 node_2 7 node_1->node_2 node_3 9 node_2->node_3 node_1592253395443 10 node_3->node_1592253395443 node_1592253478417 16 node_1592253395443->node_1592253478417 node_1592253525413 NULL node_1592253478417->node_1592253525413
%0 node_1 head1 node_2 4 node_1->node_2 node_3 7 node_2->node_3 node_1592253395443 8 node_3->node_1592253395443 node_1592253478417 9 node_1592253395443->node_1592253478417 node_1592253525413 10 node_1592253478417->node_1592253525413 node_1592253587407 15 node_1592253525413->node_1592253587407 node_1592253604112 16 node_1592253587407->node_1592253604112 node_1592253591340 19 node_1592253604112->node_1592253591340 node_1592253558766 NULL node_1592253591340->node_1592253558766
Merge two sorted linked lists
# class LinkedListNode:
# def __init__(self, data, next=None):
# self.data = data
# self.next = next
def merge_lists(head1, head2):
# Replace this placeholder return statement with your code
return None

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 mm and nn are lengths of both linked lists.

Memory complexity: Constant, 𝑂(1)𝑂(1)

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 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.

# Template for the linked list node class with arbitrary pointer
# class LinkedListNode:
# # __init__ will be used to make a LinkedListNode type object
# def __init__(self, data, next=None, arbitrary=None):
# self.data = data
# self.next = next
# self.arbitrary = arbitrary
def deep_copy_arbitrary_pointer(head):
# Replace this placeholder return statement with your code
return head

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)O(n)

Memory complexity: Linear, O(n)O(n)

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.

%0 node_1 100 node_2 50 node_1->node_2 node_3 200 node_1->node_3 node_1592254056130 25 node_2->node_1592254056130 node_1592254006797 75 node_2->node_1592254006797 node_1592253992644 350 node_3->node_1592253992644
Level order traversal for this tree should look like: 100; 50, 200; 25, 75, 350
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, data):
# self.data = data
# self.left = None
# self.right = None
def level_order_traversal(root):
# Replace this placeholder return statement with your code
return ""

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)O(n)

Memory complexity: Linear, O(n)O(n)

6. Determine if a binary tree is a binary search tree#

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.

%0 node_1 100 node_2 50 node_1->node_2 node_3 200 node_1->node_3 node_1592254056130 25 node_2->node_1592254056130 node_1592254006797 75 node_2->node_1592254006797 node_1592254403237 125 node_3->node_1592254403237 node_1592253992644 350 node_3->node_1592253992644

Below is an example of a binary tree that is not a BST.

%0 node_1 100 node_2 50 node_1->node_2 node_3 200 node_1->node_3 node_1592254056130 25 node_2->node_1592254056130 node_1592254006797 75 node_2->node_1592254006797 node_1592254403237 90 node_3->node_1592254403237 node_1592253992644 350 node_3->node_1592253992644
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, data):
# self.data = data
# self.left = None
# self.right = None
def is_bst(root):
# Replace this placeholder return statement with your code
return False

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)O(n)

Memory complexity: Linear, O(n)O(n)

7. String segmentation#

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.

%0 node_1592256504770 apple node_1 apple node_2 pear node_3 pie

Input string of “applepie” can be segmented into dictionary words.

%0 node_1 apple node_2 pie

Input string “applepeer” cannot be segmented into dictionary words.

%0 node_1 apple node_2 peer
def can_segment_string(s, dictionary):
# Replace this placeholder return statement with your code
return False

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(n3)O(n^3)

Memory complexity: Linear, O(n)O(n)

8. Reverse words in a sentence#

Reverse the order of words in a given sentence (a string of words).

%0 node_1 "Hello World" node_2 "World Hello" node_1->node_2
def reverse_words(sentence):
# Replace this placeholder return statement with your code
return ""

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)O(n)

Memory complexity: Constant, O(1)O(1)

9. How many ways can you make change with coins and a total amount#

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

def solve_coin_change(denominations, amount):
# Replace this placeholder return statement with your code
return -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, 𝑂(𝑛)𝑂(𝑛)

10. Find Kth permutation#

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

%0 node_1 1 node_2 2 node_3 3

All permutations of the above elements are (with ordering):

Here we need to find the Kth permutation.

def find_kth_permutation(v, k):
# Replace this placeholder return statement with your code
return ""

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#ofblocksblock\_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 (kskippedpermutations)th(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)𝑂(𝑛^2)

Memory complexity: Linear, O(n)O(n)

11. Find all subsets of a given set of integers#

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:

%0 node_1 2 node_2 3 node_3 4

All possile subsets for the given set of integers:

%0 node_1592257959345 node_2 2 node_3 3 node_1592258011315 2, 3 node_1592257951507 4 node_1592257981275 2, 4 node_1592258053495 3, 4 node_1592257967558 2, 3, 4
def get_all_subsets(nums):
# Replace this placeholder return statement with your code
return [[]]

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 2n2^n subsets, wherenn represents the size of the original set. The algorithm decodes the binary representation of each number, ranging from 00 to 2n12^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 2n2^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𝑛𝑛)𝑂(2^𝑛∗𝑛)

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

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.

def print_all_braces(n):
# Replace this placeholder return statement with your code
return []

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(2n)O(2^n)

Memory complexity: Linear, O(n)O(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)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.

# Definition for a graph node
# class Node:
# def __init__(self, d):
# self.data = d
# self.neighbors = []
def clone(root):
# Replace this placeholder return statement with your code
return root

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)O(n)

Memory complexity: Linear, O(n)O(n)

14. Find low/high index#

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
def find_low_high_index(arr, key):
# Replace this placeholder return statement with your code
return []

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)O(logn)

Memory complexity: Constant, O(1)O(1)

15. Search rotated array#

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.

def binary_search_rotated(arr, key):
# Replace this placeholder return statement with your code
return -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)O(logn)

Memory complexity: Constant, O(1)O(1)

More common Amazon technical coding interview questions#

  1. K largest elements from an array
  2. Convert a Binary tree to DLL
  3. Given a binary tree T, find the maximum path sum. The path may start and end at any node in the tree.
  4. Rotate a matrix by 90 degrees
  5. Assembly line scheduling with dynamic programming
  6. Implement a stack with push(), min(), and pop() in O(1)O(1) time
  7. How do you rotate an array by K?
  8. Design Snake Game using Object Oriented Programming analysis and design technique.
  9. Print all permutations of a given string using recursion
  10. Implement a queue using a linked list
  11. Find the longest increasing subsequence of an array
  12. Lowest common ancestor in a Binary Search Tree and Binary Tree
  1. Rotate a given list to the right by k places, which is non-negative.
  2. Write a function that counts the total of set bits in a 32-bit integer.
  3. How do you detect a loop in a singly linked list?
  4. Reverse an array in groups
  5. Given a binary tree, check if it’s a mirror of itself
  6. Josephus problem for recursion
  7. Zero Sum Subarrays
  8. Huffman Decoding for greedy algorithms
  9. Egg Dropping Puzzle for dynamic programming
  10. N-Queen Problem
  11. Check if strings are rotations of each other
  12. 0-1 Knapsack Problem
  13. Unbounded knapsack problem
  14. Longest palindromic subsequence
  15. Print nth number in the Fibonacci series
  16. Longest common substring
  17. Longest common subsequence


Overview of the Amazon technical 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.

  • Customer Obsession: Leaders start with the customer and work backwards. They work vigorously to earn and keep customer trust.
  • Ownership: Leaders are owners. They think long term and don’t sacrifice long-term value for short-term results. They act on behalf of the entire company. They never say “that’s not my job."
  • Invent and Simplify: Leaders expect and require innovation and invention from their teams and always find ways to simplify. They are externally aware, look for new ideas from everywhere, and are not limited by “not invented here."
  • Are Right, A Lot: Leaders are right a lot. They have strong judgment and good instincts. They seek diverse perspectives and work to disconfirm their beliefs.
  • Learn and Be Curious: Leaders are never done learning and always seek to improve themselves.
  • Hire and Develop the Best: Leaders raise the performance bar with every hire and promotion. They recognize exceptional talent, and willingly move them throughout the organization.
  • Insist on the Highest Standards: Leaders have relentlessly high standards — many people may think these standards are unreasonably high. Leaders are continually raising the bar.
  • Think Big: Thinking small is a self-fulfilling prophecy. Leaders create and communicate a bold direction that inspires results.
  • Bias for Action: Speed matters in business. Many decisions and actions are reversible and do not need extensive study. We value calculated risk taking.
  • Frugality: Accomplish more with less. Constraints breed resourcefulness, self-sufficiency, and invention.
  • Earn Trust: Leaders listen attentively, speak candidly, and treat others respectfully. They are vocally self-critical, even when doing so is awkward or embarrassing.
  • Dive Deep: Leaders operate at all levels, stay connected to the details, audit frequently, and are skeptical when metrics differ. No task is beneath them.
  • Have Backbone; Disagree and Commit: Leaders are obligated to respectfully challenge decisions when they disagree, even when doing so is uncomfortable or exhausting.
  • Deliver Results: Leaders focus on the key inputs for their business and deliver them with the right quality and in a timely fashion. Despite setbacks, they rise to the occasion and never settle.
  • How to prepare for an Amazon coding interview#

    Now that you have a sense of what to expect from an interview and know what kinds of questions to expect, let’s learn some preparation strategies based on Amazon’s unique interview process.

    Updating your resume#

    Make sure you’ve updated your resume and LinkedIn profile. Always use deliverables and metrics when you can as they are concrete examples of what you’ve accomplished. Typically recruiters will browse LinkedIn for candidates.

    If an Amazon recruiter believes that you are a good match they will reach out to you (via email or LinkedIn) to set up a time to chat. Even if you don’t land the job this time, chatting with them is a great chance to network

    Prepare for coding assessment#

    It’s up to you to come to a coding interview fully prepared for technical assessment. I recommend at least three months of self-study to be successful. This includes choosing a programming language, reviewing the basics, and studying algorithms, data structures, system design, object-oriented programming, OS, and concurrency concepts.

    You’ll also want to prepare for behavioral interviews.

    It’s best to create a roadmap for your coding interview to keep yourself on track.

    Prescreen with a recruiter#

    Expect a light 15-30 minute call where the recruiter will gauge your interest level and determine if you’re a good fit. The recruiter may touch on a few technical aspects. They just want to get an idea of your skills. Typical questions might include your past work experiences, your knowledge of the company/position, salary, and other logistical questions.

    It’s important to have around 7-10 of your own questions ready to ask the interviewer. Asking questions at an early stage shows investment and interest in the role.

    Online Coding Assessment#

    Once you complete the call with the recruiter, they’ll administer an online coding test, a debugging test, and an aptitude test. The debugging section will have around 6-7 questions, which you have 30 minutes to solve. The aptitude section will have around 14 multiple-choice questions, dealing with concepts like basic permutation combination and probabilities.

    The coding test consists of two questions. You’ll have about 1.5 hours to complete it. Expect the test to be conducted through Codility, HackerRank, or another site. Expect some easy to medium questions that are typically algorithm related. Examples include: ​

    • Reverse the second half of a linked list ​
    • Find all anagrams in a string ​
    • Merge overlapping intervals

    Tips to crack Amazon online coding assessment:#

    Here are a few easily implemented tips to make the Amazon coding assessment more manageable for yourself:

    • Use your own preferred editor

      • It is best to take the assessment in a familiar environment.
    • Read each prompt multiple times through

      • Sometimes, they may try and trick you with the wording. Make sure that you’re meeting all of the stated requirements before diving in.
    • Practice with less time than you’re given in the actual assessment

      • Time-sensitive tests can be stressful for many people. Help to relieve some of this stress by learning to work faster and more efficiently than you need to be.

    Phone Interviews#

    Once you’ve made it past the prescreen and online assessment, the recruiter will schedule your video/phone interviews, likely with a hiring manager or a manager from the team you’re looking to join. At this stage in the process, there will be one to three more interviews.

    This is where they’ll ask you questions directly related to your resume, as well as data structures, algorithms, and other various coding questions that apply to the position. You can expect to write code, review code, and demonstrate your technical knowledge.

    On-Site Interviews: The Loop#

    If you have successfully made it through the series of phone interviews, you’ll be invited for an on-site visit. This full day of on-site interviews is referred to as the “The Loop”. Throughout the day, you’ll meet with 4-6 people. Expect half of these interviews to be technical and the other half to assess soft skills. Be prepared to work through questions on a whiteboard and discuss your thought process.

    Concepts that Amazon loves to test on are data structures algorithms. It’s important to know the runtimes, theoretical limitations, and basic implementation strategies of different classes of algorithms.

    • Data structures you should know: Arrays, Stacks, Queues, Linked lists, Trees, Graphs, Hash tables

    • Algorithms you should know: Breadth First Search, Depth First Search, Binary Search, Quicksort, Mergesort, Dynamic programming, Divide and Conquer

    The Offer / No Offer#

    Generally, you’ll hear back from a recruiter within a week after your interviews. If you didn’t get an offer, Amazon will give you a call. You’ll likely have to wait another six months to re-apply. Judging that your on-site interviews went well, they’ll reach out to you, at which point they’ll make you an offer, send you documents to sign, and discuss any further questions you have.

    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.

    Wrapping up and resources#

    Cracking the Amazon coding interview comes down to the time you spend preparing, such as practicing coding questions, studying behavioral interview questions, and understanding Amazon’s company culture. There is no golden ticket, but more preparation will surely make you a more confident and desirable candidate.

    To help you prepare for interviews, Educative has created several unique language-specific courses:

  • Grokking Coding Interview Patterns in Python
  • Grokking Coding Interview Patterns in JavaScript
  • Grokking Coding Interview Patterns in Java
  • Grokking Coding Interview Patterns in Go
  • Grokking Coding Interview Patterns in C++
  • Available in multiple languages, these courses teach you the underlying patterns for any coding interview question.

    This is coding interview prep reimagined, with your needs in mind.

    Happy learning

    Continue reading about coding interview prep and interview tips#

    Frequently Asked Questions

    How do I clear my Amazon Coding interview test?

    Understand the fundamentals of data structures and algorithms, as Amazon interviews often involve complex problem-solving. Practice coding regularly. Check out the previous Amazon coding interview questions and practice well with them.

    Is Amazon coding interview hard?

    What are the different rounds of the Amazon interview?


      

    Free Resources