Question Banks
DSA Coding Problems
25 must-know problems with complete solutions, complexities, and follow-ups
P1: Two Sum Hash Map O(n)
Problem: Given array of integers and target, return indices of two numbers that add to target.
Approach: Single-pass hash map. For each number, check if complement exists.
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []Complexity: O(n) time, O(n) space.
Follow-up: What if the array is sorted? → Two pointers O(n) time O(1) space.
P2: Merge Intervals Sort + Merge
Problem: Given array of intervals, merge all overlapping intervals.
Approach: Sort by start. Iterate and merge if current overlaps with last merged.
def merge(intervals):
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 mergedComplexity: O(n log n) time, O(n) space.
P3: LRU Cache DLL + Hash Map
Problem: Implement LRU cache with O(1) get and put.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False)P4: Merge K Sorted Lists Min-Heap
Problem: Given k sorted linked lists, merge into one sorted list.
Approach: Min-heap of size k tracking smallest across all lists. Pop min, push its next.
Complexity: O(N log k) time, O(k) space.
Follow-up: What if lists are on different machines? (distributed merge)
P5: Longest Increasing Subsequence O(n log n)
Problem: Find length of longest strictly increasing subsequence.
Approach: Patience sorting with binary search. Maintain tails array.
import bisect
def length_of_lis(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)Complexity: O(n log n) time, O(n) space.
P6: Binary Search in Rotated Sorted Array
Problem: Search target in a sorted array that has been rotated at some pivot. Return index or -1.
Approach: Modified binary search. One half is always sorted determine which half target falls in.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Complexity: O(log n) time, O(1) space.
Follow-up: What if duplicates exist? → Worst case O(n) when all elements equal except one.
P7: Sliding Window Maximum (Deque)
Problem: Given array and window size k, return max of each sliding window.
Approach: Monotonic decreasing deque storing indices. Front always has current window max.
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, front = max
result = []
for i, num in enumerate(nums):
# Remove elements outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return resultComplexity: O(n) time, O(k) space.
Follow-up: How to handle this in a stream where you can't index? → Use a max-heap with lazy deletion.
P8: Word Break (Dynamic Programming)
Problem: Given a string and dictionary of words, determine if string can be segmented into dictionary words.
Approach: DP where dp[i] = True if s[0:i] can be segmented.
def word_break(s, word_dict):
word_set = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]Complexity: O(n² · m) time where m is avg word length for hashing, O(n) space.
Follow-up: Return all possible segmentations? → Backtracking with memoization.
P9: Clone Graph (BFS)
Problem: Given a node in a connected undirected graph, return a deep copy.
Approach: BFS with a hash map mapping original → clone.
from collections import deque
def clone_graph(node):
if not node:
return None
cloned = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in cloned:
cloned[neighbor] = Node(neighbor.val)
queue.append(neighbor)
cloned[curr].neighbors.append(cloned[neighbor])
return cloned[node]Complexity: O(V + E) time, O(V) space.
Follow-up: What about a directed graph with cycles? → Same approach works since we track visited via cloned map.
P10: Course Schedule (Topological Sort)
Problem: Given n courses and prerequisites, determine if all courses can be finished (detect cycle in DAG).
Approach: Kahn's algorithm BFS with in-degree tracking.
from collections import deque, defaultdict
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
completed = 0
while queue:
node = queue.popleft()
completed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return completed == num_coursesComplexity: O(V + E) time, O(V + E) space.
Follow-up: Return the actual ordering? → Collect nodes as you pop from queue.
P11: Find Median from Data Stream (Two Heaps)
Problem: Design a data structure that supports addNum and findMedian in O(log n) and O(1).
Approach: Max-heap for lower half, min-heap for upper half. Keep balanced.
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (negate values)
self.hi = [] # min-heap
def add_num(self, num):
heapq.heappush(self.lo, -num)
# Ensure max of lo <= min of hi
heapq.heappush(self.hi, -heapq.heappop(self.lo))
# Balance sizes: lo can have at most 1 more
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.0Complexity: addNum O(log n), findMedian O(1).
Follow-up: What if 99% of numbers are between 0-100? → Bucket counting for O(1) operations.
P12: Serialize/Deserialize Binary Tree
Problem: Design an algorithm to serialize and deserialize a binary tree.
Approach: Preorder traversal with null markers.
class Codec:
def serialize(self, root):
result = []
def dfs(node):
if not node:
result.append("N")
return
result.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(result)
def deserialize(self, data):
values = iter(data.split(","))
def dfs():
val = next(values)
if val == "N":
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
return dfs()Complexity: O(n) time and space for both operations.
Follow-up: How to serialize a BST more efficiently? → Only preorder needed (no null markers), rebuild using value bounds.
P13: Minimum Window Substring (Sliding Window)
Problem: Given strings s and t, find the minimum window in s containing all characters of t.
Approach: Expand window right, contract left when all chars satisfied.
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
left = 0
start, end = 0, float('inf')
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
while missing == 0:
if right - left < end - start:
start, end = left, right
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if end == float('inf') else s[start:end + 1]Complexity: O(|s| + |t|) time, O(|t|) space.
Follow-up: What if you need ALL minimum windows (not just one)? → Collect all windows with length == best.
P14: Trapping Rain Water (Two Pointers)
Problem: Given elevation map, compute how much water it can trap.
Approach: Two pointers tracking left_max and right_max.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0
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 waterComplexity: O(n) time, O(1) space.
Follow-up: 2D version (trapping rain water on a matrix)? → BFS with min-heap from borders inward.
P15: Valid Parentheses Generator (Backtracking)
Problem: Generate all valid combinations of n pairs of parentheses.
Approach: Backtracking with open/close counts.
def generate_parenthesis(n):
result = []
def backtrack(curr, open_count, close_count):
if len(curr) == 2 * n:
result.append(curr)
return
if open_count < n:
backtrack(curr + "(", open_count + 1, close_count)
if close_count < open_count:
backtrack(curr + ")", open_count, close_count + 1)
backtrack("", 0, 0)
return resultComplexity: O(4^n / √n) time (Catalan number), O(n) recursion depth.
P16: Number of Islands (DFS/BFS)
Problem: Given a 2D grid of '1' (land) and '0' (water), count number of islands.
Approach: DFS from each unvisited '1', mark all connected cells as visited.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if 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':
count += 1
dfs(r, c)
return countComplexity: O(m × n) time, O(m × n) space worst case (recursion stack).
Follow-up: What if grid is too large for recursion? → Iterative BFS with explicit queue or Union-Find.
P17: Kth Largest Element (Quickselect)
Problem: Find kth largest element in unsorted array without sorting.
Approach: Quickselect partition around pivot, recurse on relevant half.
import random
def find_kth_largest(nums, k):
target = len(nums) - k # kth largest = (n-k)th smallest
def quickselect(left, right):
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
pivot = nums[right]
store = left
for i in range(left, right):
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[right] = nums[right], nums[store]
if store == target:
return nums[store]
elif store < target:
return quickselect(store + 1, right)
else:
return quickselect(left, store - 1)
return quickselect(0, len(nums) - 1)Complexity: O(n) average, O(n²) worst case. O(1) extra space.
Follow-up: Guaranteed O(n)? → Median-of-medians pivot selection (impractical but theoretical).
P18: Dijkstra's Shortest Path
Problem: Find shortest path from source to all vertices in weighted graph (non-negative weights).
Approach: Priority queue (min-heap) processing nearest unvisited vertex first.
import heapq
from collections import defaultdict
def dijkstra(graph, source, n):
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distComplexity: O((V + E) log V) with binary heap, O(V) space.
Follow-up: Negative weights? → Bellman-Ford O(VE). Negative cycles? → Bellman-Ford detects them.
P19: Union-Find with Path Compression
Problem: Implement efficient disjoint set with union by rank and path compression.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return TrueComplexity: Nearly O(1) per operation O(α(n)) amortized (inverse Ackermann).
Use cases: Kruskal's MST, connected components, cycle detection in undirected graphs.
P20: Maximum Subarray (Kadane's Algorithm)
Problem: Find contiguous subarray with maximum sum.
Approach: Track current max ending at each position. Reset if negative.
def max_subarray(nums):
max_sum = curr_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sumComplexity: O(n) time, O(1) space.
Follow-up: Return the actual subarray? → Track start/end indices when max_sum updates. Circular array? → max(kadane, total_sum - min_subarray).
P21: Word Search II (Trie + DFS)
Problem: Given a board of characters and a list of words, find all words that exist on the board.
Approach: Build Trie from word list, then DFS from each cell matching Trie paths.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def find_words(board, words):
root = TrieNode()
for word in words:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = word
rows, cols = len(board), len(board[0])
result = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node.children:
return
child = node.children[ch]
if child.word:
result.append(child.word)
child.word = None # avoid duplicates
board[r][c] = '#' # mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, child)
board[r][c] = ch # restore
# Prune: remove leaf nodes
if not child.children:
del node.children[ch]
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return resultComplexity: O(m × n × 4^L) where L = max word length. Trie pruning makes it practical.
P22: Alien Dictionary (Topological Sort)
Problem: Given sorted list of words in alien language, derive character ordering.
Approach: Build graph from adjacent word comparisons, then topological sort.
from collections import defaultdict, deque
def alien_order(words):
# Build adjacency and in-degree
graph = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
# Check invalid case: prefix ordering
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return ""
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in graph[w1[j]]:
graph[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
# BFS topological sort
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in graph[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(in_degree):
return "" # cycle detected
return "".join(result)Complexity: O(C) where C = total characters across all words.
P23: Best Time to Buy and Sell Stock (State Machine DP)
Problem: With at most k transactions, find max profit. Generalized stock problem.
Approach: State machine with states: holding, not holding, for each transaction.
def max_profit(k, prices):
if not prices:
return 0
n = len(prices)
if k >= n // 2:
# Unlimited transactions
return sum(max(0, prices[i+1] - prices[i]) for i in range(n-1))
# dp[t][0] = max profit with t transactions, not holding
# dp[t][1] = max profit with t transactions, holding
dp = [[0, float('-inf')] for _ in range(k + 1)]
for price in prices:
for t in range(k, 0, -1):
dp[t][0] = max(dp[t][0], dp[t][1] + price) # sell
dp[t][1] = max(dp[t][1], dp[t-1][0] - price) # buy
return dp[k][0]Complexity: O(nk) time, O(k) space.
Follow-up: With cooldown? → Add a "cooldown" state: can't buy on day after selling.
P24: Edit Distance (2D DP)
Problem: Find minimum operations (insert, delete, replace) to convert word1 to word2.
Approach: Classic 2D DP. dp[i][j] = edit distance of word1[0:i] and word2[0:j].
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1] # replace
)
return dp[m][n]Complexity: O(mn) time, O(mn) space. Can optimize to O(min(m,n)) space with rolling array.
Follow-up: What if operations have different costs? → Modify the min() weights accordingly.
P25: Design Twitter (OOP + Heap)
Problem: Design a simplified Twitter with postTweet, getNewsFeed, follow, unfollow.
Approach: User → set of followees. Each user has tweet list. News feed = merge k sorted lists (heaps).
import heapq
from collections import defaultdict
class Twitter:
def __init__(self):
self.time = 0
self.tweets = defaultdict(list) # userId -> [(time, tweetId)]
self.following = defaultdict(set) # userId -> set of followees
def post_tweet(self, user_id, tweet_id):
self.tweets[user_id].append((self.time, tweet_id))
self.time += 1
def get_news_feed(self, user_id):
# Merge latest 10 from user + followees
users = self.following[user_id] | {user_id}
heap = []
for uid in users:
if self.tweets[uid]:
idx = len(self.tweets[uid]) - 1
t, tid = self.tweets[uid][idx]
heap.append((-t, tid, uid, idx))
heapq.heapify(heap)
feed = []
while heap and len(feed) < 10:
neg_t, tid, uid, idx = heapq.heappop(heap)
feed.append(tid)
if idx > 0:
t2, tid2 = self.tweets[uid][idx - 1]
heapq.heappush(heap, (-t2, tid2, uid, idx - 1))
return feed
def follow(self, follower_id, followee_id):
self.following[follower_id].add(followee_id)
def unfollow(self, follower_id, followee_id):
self.following[follower_id].discard(followee_id)Complexity: postTweet O(1), getNewsFeed O(F·log F) where F = followees, follow/unfollow O(1).
Follow-up: How would you scale this? → Fan-out-on-write for normal users, fan-out-on-read for celebrities (hybrid approach).