Amazon Top 18 Coding Interview Questions with Solutions

This post highlights the 18 most frequently asked Amazon coding interview questions—spanning arrays, strings, trees, graphs, and dynamic programming—with clean, efficient solutions and detailed explanations. Each question includes algorithmic insights and code examples to help candidates solve them confidently during interviews.

Coding interviews are an integral part of the tech hiring process.

With tech giants like Amazon hiring thousands of engineers every year, coding interviews have become more competitive than ever.

In this blog, we will look at the top 18 commonly asked coding interview questions at Amazon and how to solve them efficiently.

Arrays

Arrays are one of the most commonly used data structures in programming. Here are some key array-based questions asked at Amazon interviews:

Q1. Two Sum

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Algorithm:

• Iterate through the array and store each element and its index in a hash map.
• Check if the complement (target - current element) exists in the hash map.
• If found, return the indices of the current element and the complement.

Solution Strategy:

Use a hash map to store each number's index while iterating. For each number, check if the complement (target - number) exists in the map.

Solution:

def twoSum(nums, target):
  numMap = {}
  for i, n in enumerate(nums):
    complement = target - n
    if complement in numMap:
      return [numMap[complement], i]
    numMap[n] = i

Time Complexity: O(N)

Space Complexity: O(N)

Q2. Maximum Subarray

Problem: Given an integer array nums, find the contiguous subarray with the largest sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Algorithm:

• Initialize current sum to 0 and max sum to a minimum value.
• Loop through the array and add each element to current sum.
• If current sum is negative, reset it to 0.
• Update max sum if current sum is greater.
• Return max sum.

Solution Strategy:

Use Kadane’s Algorithm. Track the current sum and maximum seen so far while scanning through the array.

Solution:

def maxSubArray(nums):
  currentSum = 0
  maxSum = float('-inf')
  
  for n in nums:
    currentSum += n
    if currentSum < 0:
      currentSum = 0
    maxSum = max(maxSum, currentSum)
        
  return maxSum

Time Complexity: O(N)

Space Complexity: O(1)

Q3. Contains Duplicate

Problem: Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example:

Input: nums = [1,2,3,1]
Output: true

Algorithm:

• Add each element to a set.
• Before adding, check if element already exists in the set.
• If found, return true.
• At the end, no duplicate found so return false.

Solution Strategy:

Use a set to track seen elements. If an element repeats, return true. Alternatively, sort and look for adjacent duplicates.

Solution:

def containsDuplicate(nums):
  numSet = set()

  for n in nums:
    if n in numSet:
      return True
    numSet.add(n)  
      
  return False

Time Complexity: O(N)

Space Complexity: O(N)

Strings

String manipulation is another key skill tested in coding interviews. Here are some must-know string questions:

Q4. Valid Anagram

Problem: Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example:

Input: s = "anagram", t = "nagaram"
Output: true

Algorithm:

• Count frequency of characters in s and store in a hash map.
• Iterate through t and decrement count for every character.
• If count becomes negative, strings are not anagrams.
• If hash map is empty at the end, t is an anagram of s.

Solution Strategy:

Sort both strings and compare them, or use a hash map to count character frequencies and compare.

Solution:

def isAnagram(s, t):
  if len(s) != len(t):
    return False

  count = {}

  for ch in s:
    count[ch] = count.get(ch, 0) + 1
    
  for ch in t:
    if ch not in count:
      return False
    count[ch] -= 1
    if count[ch] < 0:
      return False
    
  return True

Time Complexity: O(N) where N is max(len(s), len(t))

Space Complexity: O(N)

Q5. Valid Palindrome

Problem: Given a string s, return true if it is a palindrome, and false otherwise.

Example:

Input: s = "A man, a plan, a canal: Panama" 
Output: true

Algorithm:

• Convert string to lowercase and remove non-alphanumeric characters.
• Check if reversed string is equal to original string.

Solution Strategy:

Use two pointers (start and end) to compare characters while skipping non-alphanumerics and ignoring case.

Solution:

import re

def isPalindrome(s):
  s = s.lower()
  s = re.sub('[^a-zA-Z0-9]', '', s)

  return s == s[::-1] 

Time Complexity: O(N)

Space Complexity: O(N)

Trees

Trees are a very common data structure used in Amazon coding interviews. Here are some key tree problems:

Q6. Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth.

Example:

    3
   / \
  9  20
    /  \
   15   7

Max depth = 3

Algorithm:

• Recursively calculate depth of left and right subtrees.
• Max depth is 1 + max of depths of left and right subtrees.

Solution Strategy:

Use recursion or DFS to compute the maximum depth of the left and right subtree and return the greater of the two + 1.

Solution:

def maxDepth(root):
  if not root:
    return 0

  leftDepth = maxDepth(root.left)
  rightDepth = maxDepth(root.right)

  return 1 + max(leftDepth, rightDepth)

Time Complexity: O(N)

Space Complexity: O(N)

Q7. Invert Binary Tree

Problem: Given the root of a binary tree, invert the tree, and return its root.

Example:

   4
  / \ 
 2   7 
/ \ / \
1 3 6  9

Inverted:
   4
  / \
 7   2
/ \ / \ 
9 6 3  1

Algorithm:

• Recursively swap left and right subtrees.

Solution Strategy:

Use recursion or BFS/DFS to swap the left and right child of each node in the binary tree.

Solution:

def invertTree(root):
  if root is None:
    return
  
  right = invertTree(root.right) 
  left = invertTree(root.left)

  root.left = right
  root.right = left
  
  return root

Time Complexity: O(N)

Space Complexity: O(N)

Learn more about Amazon coding interview questions.

Linked Lists

Linked lists are linear data structures that are very commonly tested in interviews.

Here are some key linked list questions:

Q8. Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Algorithm:

• Initialize prev, current and next nodes.
• Loop through list. Set next to current's next.
• Point current's next to prev.
• Advance prev and current.

Solution Strategy:

Iteratively reverse the list using three pointers (prev, current, next) or use recursion to reverse from the tail.

Solution:

def reverseList(head):
  prev = None
  current = head

  while current:
    nextNode = current.next
    current.next = prev  
    prev = current
    current = nextNode

  return prev

Time Complexity: O(N)

Space Complexity: O(1)

Q9. Merge Two Sorted Lists

Problem: Merge two sorted linked lists into one sorted list.

Example:

List 1: 1->2->4
List 2: 1->3->4
Merged: 1->1->2->3->4->4

Algorithm:

• Initialize ptr1 and ptr2 to head of both lists.
• Loop through lists till one becomes Null.
• If l1 val < l2 val, append l1 node to result. Else append l2 node.
• Advance the ptr of list whose node was appended.

Solution Strategy:

Create a dummy node and merge two pointers from each list by always selecting the smaller value and updating links.

Solution:

def mergeTwoLists(l1, l2):
  dummy = ListNode()
  tail = dummy

  while l1 and l2:   
    if l1.val < l2.val:
      tail.next = l1
      l1 = l1.next
    else:
      tail.next = l2 
      l2 = l2.next
            
    tail = tail.next
  
  if l1:
    tail.next = l1
  elif l2:
    tail.next = l2
        
  return dummy.next

Time Complexity: O(M+N)

Space Complexity: O(1)

Dynamic Programming

Dynamic programming is an advanced technique and key to solving many complex problems. Here are some DP problems asked at Amazon:

Q10. Climbing Stairs

Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps.

In how many distinct ways can you climb to the top?

Example:

Input: n = 3
Output: 3
Explanations:
1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Algorithm:

• Initialize DP array of size (n+1).
• Base cases: dp[0] = 1, dp[1] = 1
• DP relation: dp[i] = dp[i-1] + dp[i-2]
• Return dp[n]

Solution Strategy:

This is a classic Fibonacci problem.

Use recursion with memoization or bottom-up DP to avoid redundant computations.

Solution:

def climbStairs(n):
  if n == 1:
    return 1
  
  dp = [0] * (n+1)
  dp[1] = 1
  dp[2] = 2
  
  for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

  return dp[n]  

Time Complexity: O(N)

Space Complexity: O(N)

Q11. Coin Change

Problem: Given coins of different denominations and amount, find number of ways to make up the amount.

Example:

Coins: [1, 2, 5]
Amount: 5
Output: 2
Explanations: 5=5, 2+2+1

Algorithm:

• Initialize DP array of size (amount+1).
• Base case: dp[0] = 1
• DP relation: dp[i] += dp[i-coin]
• Return dp[amount]

Solution Strategy:

Use bottom-up dynamic programming.

Initialize a dp array where dp[i] stores the minimum coins needed for amount i.

Solution:

def coinChange(coins, amount):

  dp = [0] * (amount+1)
  dp[0] = 1
   
  for coin in coins:
    for i in range(coin, amount+1): 
      dp[i] += dp[i-coin]

  return dp[amount]

Time Complexity: O(A*N) where A is amount, N is coins length.

Space Complexity: O(A)

Graphs

Graphs are used to represent networks and relationships between entities. Here are some key graph algorithms.

Q12. Number of Islands

Problem: Given a 2D grid consisting of 0s (water) and 1s (land). Count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Example:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Algorithm:

• Do DFS traversal of the grid treating each 1 as a node.
• In DFS, mark any adjacent 1s as visited.
• Increment island count after each DFS call.

Solution Strategy:

Use DFS or BFS to traverse the grid and mark connected land components as visited to count distinct islands.

Solution:

def numIslands(grid):
  islands = 0 
  visited = set()

  for r in range(len(grid)):
    for c in range(len(grid[0])):
      if explore(grid, r, c, visited):
        islands += 1
  
  return islands

def explore(grid, r, c, visited):
  rowInbound = 0 <= r and r < len(grid)
  colInbound = 0 <= c and c < len(grid[0]) 

  if not rowInbound or not colInbound:
    return False

  if grid[r][c] == '0' or (r, c) in visited:
    return False
    
  visited.add((r, c))

  explore(grid, r+1, c, visited)
  explore(grid, r-1, c, visited)
  explore(grid, r, c+1, visited)
  explore(grid, r, c-1, visited)

  return True

Time Complexity: O(M*N) where M, N are grid dimensions.

Space Complexity: O(M*N)

Q13. Clone a Graph

Problem: Given a reference to the node of a connected undirected graph, return a deep copy of the graph. Each node has a val and a list of neighbors.

Algorithm:

• Do a DFS traversal and deep copy nodes and their neighbors.
• Use a hash map to keep track of cloned nodes.

Solution Strategy:

Use DFS or BFS with a hash map to clone each node and its neighbors while avoiding revisiting cloned nodes.

Solution:

def cloneGraph(node):
  oldToNew = {}

  def dfs(node):
    if node in oldToNew:
      return oldToNew[node]

    copy = Node(node.val)
    oldToNew[node] = copy

    for nei in node.neighbors:
      copy.neighbors.append(dfs(nei))

    return copy

  return dfs(node) if node else None

Time Complexity: O(N+M) where N is nodes, M is edges.

Space Complexity: O(N)

Learn more about Clone a graph problem.