20 Most Common Coding Interview Problems (With Python Solutions)
The most frequently asked coding interview problems at Google, Meta, Amazon, and Microsoft — with Python solutions, time complexity analysis, and interview tips.
These are the 20 problems that show up most often in real interviews at Google, Meta, Amazon, Microsoft, and other top tech companies. Each one includes a Python solution, the key insight to recognize the pattern, and the time/space complexity.
If you only have two weeks to prepare, solve every problem on this list.
1. Two Sum
Frequency: Extremely high (asked by almost every company)
Pattern: Hash map for O(1) lookups
def two_sum(nums: list[int], target: int) -> list[int]: seen = {} # value -> index for i, num in enumerate(nums): complement = target - num if complement in seen:
Key insight: At each position, decide whether to extend the current subarray or start fresh.
Time: O(n) | Space: O(1)
6. Binary Search
Frequency: High (and appears as a sub-step in many problems)
Pattern: Divide and conquer
def binary_search(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 # avoids overflow if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
Time: O(log n) | Space: O(1)
7. Number of Islands
Frequency: Very high
Pattern: DFS/BFS on grid
def num_islands(grid: list[list[str]]) -> int: if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r: int, c: int) -> None: if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1": return grid[r][c] = "0" # mark visited dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) for r in range(rows): for c in range(cols): if grid[r][c] == "1": dfs(r, c) count += 1 return count
def climb_stairs(n: int) -> int: if n <= 2: return n prev, curr = 1, 2 for _ in range(3, n + 1): prev, curr = curr, prev + curr return currprint(climb_stairs(5)) # 8
Time: O(n) | Space: O(1)
9. Reverse a Linked List
Frequency: Very high in phone screens
Pattern: Pointer manipulation
def reverse_list(head: ListNode) -> ListNode: prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev
Time: O(n) | Space: O(1)
10. Validate Binary Search Tree
Frequency: High
Pattern: DFS with bounds
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightdef is_valid_bst(root: TreeNode) -> bool: def validate(node, min_val, max_val): if not node: return True if node.val <= min_val or node.val >= max_val: return False return ( validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val) ) return validate(root, float("-inf"), float("inf"))
Time: O(n) | Space: O(h) where h is tree height
11. Coin Change
Frequency: Very high (tests DP ability)
Pattern: Bottom-up dynamic programming
def coin_change(coins: list[int], amount: int) -> int: dp = [float("inf")] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float("inf") else -1print(coin_change([1, 5, 11], 15)) # 3 (5+5+5)
Time: O(amount × len(coins)) | Space: O(amount)
12. Longest Common Subsequence
Frequency: High in senior interviews
Pattern: 2D dynamic programming
def longest_common_subsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]print(longest_common_subsequence("abcde", "ace")) # 3
Time: O(m × n) | Space: O(m × n)
13. Word Search
Frequency: High
Pattern: DFS + backtracking
def exist(board: list[list[str]], word: str) -> bool: rows, cols = len(board), len(board[0]) def dfs(r, c, idx): if idx == len(word): return True if (r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]): return False temp = board[r][c] board[r][c] = "#" # mark visited found = (dfs(r + 1, c, idx + 1) or dfs(r - 1, c, idx + 1) or dfs(r, c + 1, idx + 1) or dfs(r, c - 1, idx + 1)) board[r][c] = temp # restore return found for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True return False
Time: O(m × n × 4^L) where L = word length | Space: O(L)
14. Merge Intervals
Frequency: Very high in system design contexts
Pattern: Sort + greedy
def merge(intervals: list[list[int]]) -> list[list[int]]: intervals.sort(key=lambda x: x[0]) merged = [intervals[0]] for start, end in intervals[1:]: if start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end]) return mergedprint(merge([[1,3],[2,6],[8,10],[15,18]]))# [[1, 6], [8, 10], [15, 18]]
def top_k_frequent_bucket(nums: list[int], k: int) -> list[int]: count = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for num, freq in count.items(): buckets[freq].append(num) result = [] for bucket in reversed(buckets): result.extend(bucket) if len(result) >= k: return result[:k] return result
16. Longest Substring Without Repeating Characters
Frequency: Very high
Pattern: Sliding window
def length_of_longest_substring(s: str) -> int: char_set = set() left = max_length = 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left += 1 char_set.add(s[right]) max_length = max(max_length, right - left + 1) return max_lengthprint(length_of_longest_substring("abcabcbb")) # 3 ("abc")
Time: O(n) | Space: O(min(n, m)) where m is charset size
17. Course Schedule (Cycle Detection)
Frequency: High at companies with complex systems
Pattern: Topological sort / DFS cycle detection
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool: graph = [[] for _ in range(num_courses)] for a, b in prerequisites: graph[b].append(a) # 0 = unvisited, 1 = visiting, 2 = visited state = [0] * num_courses def dfs(node: int) -> bool: if state[node] == 1: # cycle return False if state[node] == 2: # already safe return True state[node] = 1 for neighbor in graph[node]: if not dfs(neighbor): return False state[node] = 2 return True return all(dfs(i) for i in range(num_courses))
Time: O(V + E) | Space: O(V + E)
18. LRU Cache
Frequency: High (tests system design + data structure knowledge)
Pattern: Hash map + doubly linked list
from collections import OrderedDictclass LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.capacity: self.cache.popitem(last=False)
19. Trapping Rain Water
Frequency: High at FAANG
Pattern: Two pointers
def trap(height: list[int]) -> int: left, right = 0, len(height) - 1 left_max = right_max = water = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return waterprint(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
Time: O(n) | Space: O(1)
20. Serialize and Deserialize Binary Tree
Frequency: Common at Google and Meta
Pattern: BFS with queue
from collections import dequeclass Codec: def serialize(self, root: TreeNode) -> str: if not root: return "" result = [] queue = deque([root]) while queue: node = queue.popleft() if node: result.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: result.append("null") return ",".join(result) def deserialize(self, data: str) -> TreeNode: if not data: return None values = iter(data.split(",")) root = TreeNode(int(next(values))) queue = deque([root]) for val in values: node = queue.popleft() left_val = next(values, None) if val != "null": node.left = TreeNode(int(val)) queue.append(node.left) if left_val and left_val != "null": node.right = TreeNode(int(left_val)) queue.append(node.right) return root
Interview Strategy Tips
Before you code:
Restate the problem in your own words
Ask about edge cases (empty input, negatives, duplicates)
Talk through your approach before writing — interviewers want to see your thinking
Test with the examples given, then with edge cases
Common patterns to recognize:
Hash map → usually when you need O(1) lookups to reduce O(n²) to O(n)
Two pointers → sorted arrays, palindromes, pair finding
Sliding window → subarrays/substrings with a constraint
DFS/BFS → trees, graphs, grids
Dynamic programming → optimization, counting, "can we achieve X"
Binary search → sorted data, "find the minimum/maximum that satisfies X"
Ready to practice these problems interactively? uByte's interview prep section has coding problems you can solve directly in your browser with instant feedback — no local setup needed.