# 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!