50 Python DSA Interview Questions & Answers — Solved by Pattern
The pattern overview gives you the 10 templates. This is the other half: all 50 problems, each stated as an interview question with a complete, runnable Python solution and the complexity to say out loud. Work the questions cold, then check the answers.
Companion: Top 50 Python DSA Problems by Pattern (With Solutions) — the 10 pattern templates this Q&A is built on. Learn the pattern there, drill the questions here.
Pattern 1 — Two Pointers
1. Two Sum II — input array is sorted
Problem: given a 1-indexed sorted array, find two numbers adding to target. Key idea: converge from both ends; move the side that's too big/small.
def two_sum_ii(a, target):
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target:
return [l + 1, r + 1]
if s < target:
l += 1
else:
r -= 1
O(n) time, O(1) space.
2. Container With Most Water
Problem: given heights, find two lines holding the most water. Key idea: area = min(h) × width; always move the shorter wall.
def max_area(h):
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, min(h[l], h[r]) * (r - l))
if h[l] < h[r]:
l += 1
else:
r -= 1
return best
O(n) time, O(1) space.
3. 3Sum
Problem: find all unique triplets summing to zero. Key idea: sort, fix one element, two-pointer the rest; skip duplicates at every level.
def three_sum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
res.append([nums[i], nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l - 1]:
l += 1
elif s < 0:
l += 1
else:
r -= 1
return res
O(n²) time, O(1) extra space.
4. Valid Palindrome
Problem: is the string a palindrome, ignoring case and non-alphanumerics? Key idea: converge, skipping junk characters from both sides.
def is_palindrome(s):
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l, r = l + 1, r - 1
return True
O(n) time, O(1) space.
5. Trapping Rain Water
Problem: compute water trapped between elevation bars. Key idea: water at i = min(maxL, maxR) − height; the two-pointer version tracks both maxima in one pass.
def trap(h):
l, r, lmax, rmax, water = 0, len(h) - 1, 0, 0, 0
while l < r:
if h[l] < h[r]:
lmax = max(lmax, h[l])
water += lmax - h[l]
l += 1
else:
rmax = max(rmax, h[r])
water += rmax - h[r]
r -= 1
return water
O(n) time, O(1) space.
Pattern 2 — Sliding Window
6. Longest Substring Without Repeating Characters
Problem: length of the longest substring with all unique characters. Key idea: expand right; on a duplicate, jump the left edge past its last occurrence.
def length_of_longest_substring(s):
seen, l, best = {}, 0, 0
for r, ch in enumerate(s):
if ch in seen and seen[ch] >= l:
l = seen[ch] + 1
seen[ch] = r
best = max(best, r - l + 1)
return best
O(n) time, O(min(n, alphabet)) space.
7. Minimum Window Substring
Problem: smallest substring of s containing all characters of t. Key idea: expand until the window covers t, then shrink from the left while it still does.
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing, l = len(t), 0
start, best = 0, float('inf')
for r, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if r - l + 1 < best:
best, start = r - l + 1, l
need[s[l]] += 1
if need[s[l]] > 0:
missing += 1
l += 1
return s[start:start + best] if best != float('inf') else ""
O(n) time, O(k) space (k = distinct chars in t).
8. Longest Repeating Character Replacement
Problem: longest substring achievable by replacing at most k characters. Key idea: window is valid while (length − most-frequent-char-count) ≤ k.
from collections import Counter
def character_replacement(s, k):
count = Counter()
l, best = 0, 0
for r, ch in enumerate(s):
count[ch] += 1
while (r - l + 1) - max(count.values()) > k:
count[s[l]] -= 1
l += 1
best = max(best, r - l + 1)
return best
O(n) time, O(1) space.
9. Permutation in String
Problem: does s2 contain a permutation of s1? Key idea: fixed-size window of len(s1); compare frequency maps as it slides.
from collections import Counter
def check_inclusion(s1, s2):
n, m = len(s1), len(s2)
if n > m:
return False
need, window = Counter(s1), Counter(s2[:n])
if need == window:
return True
for i in range(n, m):
window[s2[i]] += 1
window[s2[i - n]] -= 1
if window[s2[i - n]] == 0:
del window[s2[i - n]]
if need == window:
return True
return False
O(m) time, O(1) space.
10. Maximum Sum Subarray of Size K
Problem: maximum sum of any contiguous subarray of length k. Key idea: slide the fixed window, updating the running sum.
def max_sum_k(a, k):
window = sum(a[:k])
best = window
for i in range(k, len(a)):
window += a[i] - a[i - k]
best = max(best, window)
return best
O(n) time, O(1) space.
Pattern 3 — Hash Map
11. Two Sum
Problem: return indices of two numbers adding to target. Key idea: one pass — check for the complement before storing the current value.
def two_sum(a, target):
seen = {}
for i, x in enumerate(a):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
O(n) time, O(n) space.
12. Group Anagrams
Problem: group words that are anagrams. Key idea: anagrams share a canonical key — the sorted word.
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups[tuple(sorted(w))].append(w)
return list(groups.values())
O(n · k log k) time, O(n · k) space.
13. Top K Frequent Elements
Problem: the k most frequent elements. Key idea: count, then take the top k.
from collections import Counter
def top_k_frequent(nums, k):
return [x for x, _ in Counter(nums).most_common(k)]
O(n log k) time, O(n) space.
14. Longest Consecutive Sequence
Problem: longest consecutive run, in O(n). Key idea: only start counting at sequence starts (x−1 not in set).
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 not in s:
y = x
while y in s:
y += 1
best = max(best, y - x)
return best
O(n) time, O(n) space.
15. Subarray Sum Equals K
Problem: count subarrays summing to k. Key idea: prefix sums in a map — prefix[i] − prefix[j] = k.
from collections import defaultdict
def subarray_sum(nums, k):
prefix = defaultdict(int)
prefix[0] = 1
total = count = 0
for x in nums:
total += x
count += prefix[total - k]
prefix[total] += 1
return count
O(n) time, O(n) space.
Pattern 4 — Stack
16. Valid Parentheses
Problem: is the bracket string well-formed? Key idea: push opens, match closes; stack empty at the end.
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)
return not stack
O(n) time, O(n) space.
17. Min Stack
Problem: stack with O(1) push, pop, top, get-min. Key idea: store (value, running-min) pairs.
class MinStack:
def __init__(self):
self.stack = []
def push(self, x):
m = x if not self.stack else min(x, self.stack[-1][1])
self.stack.append((x, m))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def get_min(self):
return self.stack[-1][1]
O(1) per operation, O(n) space.
18. Daily Temperatures
Problem: for each day, days until a warmer temperature. Key idea: monotonic decreasing stack.
def daily_temperatures(t):
res = [0] * len(t)
stack = []
for i, x in enumerate(t):
while stack and t[stack[-1]] < x:
j = stack.pop()
res[j] = i - j
stack.append(i)
return res
O(n) time, O(n) space.
19. Largest Rectangle in Histogram
Problem: largest rectangle area in a histogram. Key idea: monotonic stack of indices; a shorter bar ends every taller bar on the stack.
def largest_rectangle(h):
h = h + [0]
stack, best = [], 0
for i, x in enumerate(h):
while stack and h[stack[-1]] > x:
height = h[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return best
O(n) time, O(n) space.
20. Evaluate Reverse Polish Notation
Problem: evaluate an RPN expression. Key idea: push operands; on operator pop two, apply, push back. Division truncates toward zero.
def eval_rpn(tokens):
stack = []
for t in tokens:
if t not in "+-*/":
stack.append(int(t))
continue
b, a = stack.pop(), stack.pop()
if t == '+':
stack.append(a + b)
elif t == '-':
stack.append(a - b)
elif t == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
return stack[0]
O(n) time, O(n) space.
Pattern 5 — Binary Search
21. Binary Search
Problem: find target in a sorted array. Key idea: the half-open interval form — no off-by-one.
def binary_search(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo if lo < len(a) and a[lo] == target else -1
O(log n) time, O(1) space.
22. Search in Rotated Sorted Array
Problem: find target in a rotated sorted array. Key idea: one half is always sorted — check which, then decide if the target lives there.
def search_rotated(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[lo] <= a[mid]:
if a[lo] <= target < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if a[mid] < target <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
O(log n) time, O(1) space.
23. Find Minimum in Rotated Sorted Array
Problem: the minimum of a rotated sorted array. Key idea: compare mid to the right end.
def find_min(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1
else:
hi = mid
return a[lo]
O(log n) time, O(1) space.
24. Search a 2D Matrix
Problem: search a row-sorted matrix where each row starts after the previous ends. Key idea: flatten mentally — mid maps to m[mid // cols][mid % cols].
def search_matrix(m, target):
if not m:
return False
rows, cols = len(m), len(m[0])
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
x = m[mid // cols][mid % cols]
if x == target:
return True
if x < target:
lo = mid + 1
else:
hi = mid - 1
return False
O(log(m·n)) time, O(1) space.
25. Koko Eating Bananas
Problem: minimum eating speed k to finish all piles in h hours. Key idea: binary search on the answer — "can finish at speed k" is monotonic.
import math
def min_eating_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
k = (lo + hi) // 2
hours = sum(math.ceil(p / k) for p in piles)
if hours <= h:
hi = k
else:
lo = k + 1
return lo
O(n log max) time, O(1) space.
Pattern 6 — Trees: BFS & DFS
All tree solutions below use this node definition:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
26. Maximum Depth of Binary Tree
Problem: depth of the deepest node. Key idea: 1 + max(depth of children).
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
O(n) time, O(h) space.
27. Invert Binary Tree
Problem: mirror the tree. Key idea: swap children recursively.
def invert_tree(root):
if root:
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return root
O(n) time, O(h) space.
28. Diameter of Binary Tree
Problem: longest path between any two nodes (in edges). Key idea: post-order returns depth; candidate diameter at each node is left-depth + right-depth.
def diameter(root):
best = 0
def depth(node):
nonlocal best
if not node:
return 0
l, r = depth(node.left), depth(node.right)
best = max(best, l + r)
return 1 + max(l, r)
depth(root)
return best
O(n) time, O(h) space.
29. Lowest Common Ancestor of a Binary Tree
Problem: deepest node that is an ancestor of both p and q. Key idea: a node is the answer when p is found in one subtree and q in the other.
def lowest_common_ancestor(root, p, q):
if not root or root in (p, q):
return root
l = lowest_common_ancestor(root.left, p, q)
r = lowest_common_ancestor(root.right, p, q)
return root if l and r else (l or r)
O(n) time, O(h) space.
30. Binary Tree Level Order Traversal
Problem: values level by level. Key idea: BFS with the level-size loop.
from collections import deque
def level_order(root):
if not root:
return []
q, res = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
O(n) time, O(n) space.
Pattern 7 — Heaps
31. Kth Largest Element in an Array
Problem: kth largest, without full sort. Key idea: min-heap of size k — the root is always the kth largest so far.
import heapq
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
O(n log k) time, O(k) space.
32. Merge K Sorted Lists
Problem: merge k sorted linked lists. Key idea: heap of list heads — pop the smallest, push its next.
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def merge_k_lists(lists):
heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
heapq.heapify(heap)
dummy = cur = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
cur.next, cur = node, node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
O(N log k) time, O(k) space.
33. Top K Frequent Elements — heap version
Problem: the k most frequent, via an explicit heap. Key idea: heapq.nlargest with the count as key.
import heapq
from collections import Counter
def top_k_frequent_heap(nums, k):
counts = Counter(nums)
return heapq.nlargest(k, counts, key=counts.get)
O(n log k) time, O(n) space.
34. Find Median from Data Stream
Problem: support add_num and find_median on a stream. Key idea: max-heap for the low half, min-heap for the high half; rebalance so sizes differ by at most one.
import heapq
class MedianFinder:
def __init__(self):
self.lo = []
self.hi = []
def add_num(self, x):
heapq.heappush(self.lo, -x)
heapq.heappush(self.hi, -heapq.heappop(self.lo))
if len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def find_median(self):
if len(self.lo) > len(self.hi):
return -self.lo[0]
return (-self.lo[0] + self.hi[0]) / 2
O(log n) add, O(1) median, O(n) space.
35. Task Scheduler
Problem: minimum intervals to run tasks with cooldown n. Key idea: driven by the most frequent task: (fmax−1)·(n+1) + ties, or len(tasks) if bigger.
from collections import Counter
def least_interval(tasks, n):
counts = Counter(tasks).values()
fmax = max(counts)
return max(len(tasks), (fmax - 1) * (n + 1) + sum(c == fmax for c in counts))
O(n) time, O(1) space.
Pattern 8 — Graphs
36. Number of Islands
Problem: count islands of '1's in a grid. Key idea: flood fill — every unvisited land cell starts a new island; sink it with DFS.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
return
grid[r][c] = '0'
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
dfs(r + dr, c + dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
O(m·n) time, O(m·n) space worst case.
37. Clone Graph
Problem: deep-copy a connected undirected graph. Key idea: DFS + old→new map; create the copy before recursing so cycles terminate.
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors or []
def clone_graph(node):
old_to_new = {}
def dfs(n):
if n in old_to_new:
return old_to_new[n]
copy = Node(n.val)
old_to_new[n] = copy
copy.neighbors = [dfs(nb) for nb in n.neighbors]
return copy
return dfs(node) if node else None
O(V + E) time and space.
38. Course Schedule
Problem: can you finish all courses given prerequisites? Key idea: cycle detection via topological sort (Kahn's).
from collections import defaultdict, deque
def can_finish(n, prereqs):
graph = defaultdict(list)
indeg = [0] * n
for a, b in prereqs:
graph[b].append(a)
indeg[a] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
done = 0
while q:
u = q.popleft()
done += 1
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return done == n
O(V + E) time and space.
39. Pacific Atlantic Water Flow
Problem: cells from which water can flow to both oceans. Key idea: reverse thinking — flow uphill from each ocean's edge; intersect the reachable sets.
def pacific_atlantic(h):
if not h:
return []
rows, cols = len(h), len(h[0])
pac = [[False] * cols for _ in range(rows)]
atl = [[False] * cols for _ in range(rows)]
def dfs(r, c, seen):
seen[r][c] = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and not seen[nr][nc] and h[nr][nc] >= h[r][c]):
dfs(nr, nc, seen)
for r in range(rows):
dfs(r, 0, pac)
dfs(r, cols - 1, atl)
for c in range(cols):
dfs(0, c, pac)
dfs(rows - 1, c, atl)
return [[r, c] for r in range(rows) for c in range(cols)
if pac[r][c] and atl[r][c]]
O(m·n) time and space.
40. Word Ladder
Problem: shortest transformation sequence from begin to end, one letter at a time. Key idea: BFS on the word graph; wildcard buckets make neighbor lookup O(1).
from collections import defaultdict, deque
def ladder_length(begin, end, words):
words = set(words)
if end not in words:
return 0
buckets = defaultdict(list)
for w in words | {begin}:
for i in range(len(w)):
buckets[w[:i] + '*' + w[i + 1:]].append(w)
q = deque([(begin, 1)])
seen = {begin}
while q:
w, d = q.popleft()
if w == end:
return d
for i in range(len(w)):
for nb in buckets[w[:i] + '*' + w[i + 1:]]:
if nb not in seen:
seen.add(nb)
q.append((nb, d + 1))
return 0
O(N · L²) time, O(N · L) space.
Pattern 9 — Dynamic Programming
41. Climbing Stairs
Problem: ways to climb n stairs taking 1 or 2 steps. Key idea: dp[i] = dp[i−1] + dp[i−2]; optimize to O(1) space.
def climb_stairs(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
O(n) time, O(1) space.
42. House Robber
Problem: max loot without robbing adjacent houses. Key idea: dp[i] = max(dp[i−1], dp[i−2] + nums[i]) — take or skip.
def rob(nums):
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
O(n) time, O(1) space.
43. Coin Change
Problem: fewest coins to make amount (unlimited coins). Key idea: unbounded knapsack; iterate coins outer, amounts inner.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for c in coins:
for a in range(c, amount + 1):
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
O(amount · coins) time, O(amount) space.
44. Longest Increasing Subsequence
Problem: length of the longest strictly increasing subsequence. Key idea: patience sorting — smallest possible tail for each length; bisect to place each element.
import bisect
def length_of_lis(nums):
tails = []
for x in nums:
i = bisect.bisect_left(tails, x)
tails[i:i + 1] = [x]
return len(tails)
O(n log n) time, O(n) space.
45. 0/1 Knapsack
Problem: max value with capacity W, each item taken at most once. Key idea: iterate capacity backwards so each item is used once.
def knapsack(weights, values, W):
dp = [0] * (W + 1)
for w, v in zip(weights, values):
for cap in range(W, w - 1, -1):
dp[cap] = max(dp[cap], dp[cap - w] + v)
return dp[W]
O(n·W) time, O(W) space.
Pattern 10 — Intervals
46. Merge Intervals
Problem: merge overlapping intervals. Key idea: sort by start; each interval extends the last merged one or starts a new one.
def merge(intervals):
intervals.sort()
merged = [intervals[0]]
for s, e in intervals[1:]:
if s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])
return merged
O(n log n) time, O(n) space.
47. Insert Interval
Problem: insert a new interval into sorted non-overlapping intervals. Key idea: one pass, three phases — before, overlap (widen), after.
def insert(intervals, new):
res, i = [], 0
while i < len(intervals) and intervals[i][1] < new[0]:
res.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
i += 1
res.append(new)
return res + intervals[i:]
O(n) time, O(n) space.
48. Non-overlapping Intervals
Problem: minimum removals to make intervals non-overlapping. Key idea: greedy by end time — keep the earliest-ending interval.
def erase_overlap(intervals):
intervals.sort(key=lambda x: x[1])
removed, end = 0, float('-inf')
for s, e in intervals:
if s < end:
removed += 1
else:
end = e
return removed
O(n log n) time, O(1) extra space.
49. Meeting Rooms II
Problem: minimum conference rooms needed. Key idea: min-heap of end times — if the earliest-ending meeting is done, reuse its room.
import heapq
def min_rooms(intervals):
intervals.sort()
heap = []
for s, e in intervals:
if heap and heap[0] <= s:
heapq.heappop(heap)
heapq.heappush(heap, e)
return len(heap)
O(n log n) time, O(n) space.
50. Minimum Number of Arrows to Burst Balloons
Problem: fewest arrows to burst all balloons (intervals). Key idea: sort by end; shoot at the earliest end.
def min_arrows(points):
points.sort(key=lambda p: p[1])
arrows, end = 0, float('-inf')
for s, e in points:
if s > end:
arrows += 1
end = e
return arrows
O(n log n) time, O(1) extra space.
How to drill these
- Cover the answer, read only the Problem line, and write the solution cold — then diff against the code above.
- Say the Key idea and the complexity out loud before you code; interviewers score the analysis.
- Stuck? Name the pattern, then re-read the matching template in the companion post.
In this series
- Top 40 Python Interview Questions and Answers (2026 Edition) — start here.
- Python Coding Interview Patterns: Lists, Strings & Hash Maps — the essential patterns.
- Python Internals for Interviews: Decorators, Generators, GIL & OOP — how Python really works.
- Tricky Python Questions Interviewers Love — gotchas and edge cases.
- Top 50 Python DSA Problems by Pattern (With Solutions) — 50 problems, solved by pattern.
- 50 Python DSA Interview Questions & Answers — Solved by Pattern (this post) — the companion drill set.
Full Python roadmap: Python Learning Roadmap 2026 — all 50 tutorials across 8 tracks.
Comments
Post a Comment