Amazon Top 18 Coding Interview Questions with Solutions

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 25 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:

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

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)

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

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)

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

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:

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

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)

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

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:

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

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)

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

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)

Linked Lists

Linked lists are linear data structures that are very commonly tested in interviews. Here are some key linked list questions:

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

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)

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

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:

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

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)

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

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.

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

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)

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

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)

14. Longest Palindromic Substring

Problem: Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad"
Output: "bab" 
Explanation: "aba" is also a valid answer.

Algorithm:

• Use dynamic programming.
• Initialize table of length n+1.
• Check every substring with left/right pointers.
• Store longest palindrome seen so far.

Solution:

def longestPalindrome(s):
  n = len(s)
  table = [[False]*n for _ in range(n)]
  ans = ""
  
  for i in range(n):
    table[i][i] = True
    ans = s[i]

  for i in range(n-1):
    if s[i] == s[i+1]:
      table[i][i+1] = True
      ans = s[i:i+2]

  for k in range(3, n+1):
    for i in range(n-k+1): 
      j = i + k - 1
      if table[i+1][j-1] and s[i] == s[j]:
        table[i][j] = True
        ans = s[i:j+1]

  return ans

Time Complexity: O(N^2)

Space Complexity: O(N^2)

15. Product of Array Except Self

Problem: Given an array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Do not use division operator.

Example:

Input: nums = [1,2,3,4]
Output: [24,12,8,6] 

Algorithm:

• Initialize answer array with all 1s.
• Traverse forward to calculate left running product.
• Traverse backward to calculate right running product.
• Answer is product of left and right products.

Solution:

def productExceptSelf(nums):
  n = len(nums)
  output = [1] * n

  leftProduct = 1
  for i in range(n):
    output[i] = leftProduct
    leftProduct *= nums[i]
  
  rightProduct = 1
  for i in range(n-1, -1, -1):
    output[i] *= rightProduct
    rightProduct *= nums[i]

  return output

Time Complexity: O(N)

Space Complexity: O(1)

16. Valid Parentheses

Problem: Given a string s containing just parentheses '()', '{}', '[]', determine if it is valid.

Example:

Input: s = "()[]{}"
Output: true

Algorithm:

• Declare a stack.
• Push opening brackets onto stack.
• Pop stack if closing bracket matches top.
• Check empty stack in the end.

Solution:

def isValid(s):
  stack = []
  closeToOpen = {")":"(", "}":"{", "]":"["}

  for ch in s:
    if ch in closeToOpen:
      if stack and stack[-1] == closeToOpen[ch]:
        stack.pop()
      else:
        return False
    else:
      stack.append(ch)

  return True if not stack else False

Time Complexity: O(N) Space Complexity: O(N)

17. Merge K Sorted Lists

Problem: Given an array of linked lists lists, merge all the lists into one sorted list.

Example:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Algorithm:

• Use a min-heap to store node values.
• Extract min value, append to result.
• Add next node value for that list to heap.
• Repeat till heap empty.

Solution:

from heapq import heappush, heappop

def mergeKLists(lists):
  dummy = ListNode()
  tail = dummy

  minHeap = []
  
  for linkedList in lists:
    if linkedList:
      heappush(minHeap, (linkedList.val, linkedList))

  while minHeap:
    val, node = heappop(minHeap)
    tail.next = node
    tail = tail.next
    
    if node.next:
      heappush(minHeap, (node.next.val, node.next))

  return dummy.next 

Time Complexity: O(NlogK) where N is total nodes, K is lists Space Complexity: O(K)

18. Word Break

Problem: Given a string s and a dictionary of words dict, return true if s can be segmented into a space separated sequence of one or more dictionary words.

Example:

s = "applepenapple"
dict = ["apple", "pen"]
Output: true
Explanations: "apple pen apple" is a valid segmentation.

Solution:

def wordBreak(s, words):
  dp = [False] * (len(s) + 1)
  dp[0] = True

  for i in range(len(s)):
    for w in words:
      if dp[i] and s[i:i+len(w)] == w:
        dp[i+len(w)] = True
  
  return dp[-1]

Wrap Up

In summary, Amazon coding interviews test a wide range of data structures and algorithms. Mastering these top interview questions will prepare you to tackle any Amazon interview with confidence. Focus on writing clean, optimal code and having strong communication skills. With diligent practice, you will be able to successfully solve these problems under pressure. All the best!