DSA course menu
DSA Coding Challenges With Solutions (Python)
Practice full coding interview problems with hints and step-by-step Python solutions: trapping rain water, merge intervals, LRU cache, word search, minimum window substring, rotting oranges, coin change and the longest palindromic substring.
On this page
These are complete problems of the kind asked in coding rounds. For each one: read it, try it yourself for 20–30 minutes using the problem-solving method, then use the hint, and only then read the solution.
1. Trapping rain water#
Practice exercise
Bars of width 1 have the given heights. How much rain water is trapped between them? For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] the answer is 6.
Show hint
Water above a bar is min(highest bar to its left, highest bar to its right) - its height. Two pointers from both ends can track those maximums: always move the side with the smaller maximum, because that side's water level is already decided.
Show solution
def trap(heights):
left, right = 0, len(heights) - 1
left_max = right_max = water = 0
while left < right:
if heights[left] < heights[right]:
left_max = max(left_max, heights[left])
water += left_max - heights[left]
left += 1
else:
right_max = max(right_max, heights[right])
water += right_max - heights[right]
right -= 1
return water
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
print(trap([4, 2, 0, 3, 2, 5]))6
9O(n) time, O(1) space.
2. Insert an interval#
Practice exercise
Given sorted, non-overlapping intervals and a new interval, insert it and merge any overlaps.
Show hint
Three phases: copy intervals that end before the new one starts; merge every interval that overlaps it (take the min start and max end); copy the rest.
Show solution
def insert_interval(intervals, new):
result, i = [], 0
start, end = new
while i < len(intervals) and intervals[i][1] < start:
result.append(intervals[i]); i += 1
while i < len(intervals) and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
result.append([start, end])
result.extend(intervals[i:])
return result
print(insert_interval([[1, 3], [6, 9]], [2, 5]))
print(insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]O(n).
3. Word search in a grid#
Practice exercise
Can the word be spelled by moving between horizontally or vertically adjacent cells, using each cell at most once?
Show hint
Backtracking from every cell that matches the first letter. Mark a cell as used before exploring its neighbours and unmark it afterwards.
Show solution
def exists(board, word):
rows, cols = len(board), len(board[0])
grid = [list(r) for r in board]
def search(r, c, i):
if i == len(word):
return True
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != word[i]:
return False
saved, grid[r][c] = grid[r][c], "#" # mark as used
found = any(search(r + dr, c + dc, i + 1) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
grid[r][c] = saved # un-mark
return found
return any(search(r, c, 0) for r in range(rows) for c in range(cols))
board = ["ABCE", "SFCS", "ADEE"]
print(exists(board, "ABCCED"), exists(board, "SEE"), exists(board, "ABCB"))True True False"ABCB" would need to reuse the B, which is not allowed.
4. Minimum window substring#
Practice exercise
Find the shortest substring of s that contains every character of t (with repeats). Return "" if there is none.
Show hint
Sliding window with counts. Expand right until all characters of t are covered; then shrink from the left while it stays covered, recording the shortest window. Track how many distinct characters are fully satisfied so the "covered?" check is O(1).
Show solution
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(need) # distinct characters not yet satisfied
have = Counter()
best = (float("inf"), 0, 0)
left = 0
for right, ch in enumerate(s):
have[ch] += 1
if ch in need and have[ch] == need[ch]:
missing -= 1
while missing == 0:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right + 1)
out = s[left]
have[out] -= 1
if out in need and have[out] < need[out]:
missing += 1
left += 1
return s[best[1]:best[2]] if best[0] != float("inf") else ""
print(repr(min_window("ADOBECODEBANC", "ABC")))
print(repr(min_window("a", "aa")))'BANC'
''O(len(s) + len(t)).
5. Rotting oranges#
Practice exercise
Each minute, rotten oranges (2) rot their fresh (1) neighbours up, down, left and right. How many minutes until no fresh orange remains? Return -1 if some never rot.
Show hint
Multi-source BFS: start with every rotten orange in the queue at minute 0.
Show solution
from collections import deque
def oranges(grid):
grid = [row[:] for row in grid]
rows, cols = len(grid), len(grid[0])
queue = deque((r, c, 0) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
fresh = sum(row.count(1) for row in grid)
minutes = 0
while queue:
r, c, t = queue.popleft()
minutes = max(minutes, t)
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, t + 1))
return -1 if fresh else minutes
print(oranges([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
print(oranges([[0, 2]]))4
0O(rows × cols).
6. Longest palindromic substring#
Practice exercise
Return the longest contiguous palindrome inside a string.
Show hint
Every palindrome has a centre: a character (odd length) or a gap between two characters (even length). Expand outwards from each of the 2n − 1 centres while the ends match.
Show solution
def longest_palindrome(s):
best = ""
for centre in range(2 * len(s) - 1):
left = centre // 2
right = left + centre % 2
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
if right - left - 1 > len(best):
best = s[left + 1:right]
return best
print(longest_palindrome("babad"), longest_palindrome("cbbd"), longest_palindrome("forgeeksskeegfor"))bab bb geeksskeegO(n²) time, O(1) space. "babad" also contains "aba"; either is accepted.
7. Coin change (fewest coins)#
Practice exercise
Fewest coins to make an amount, or -1.
Show hint
dp[a] = 1 + min(dp[a - c]) over coins c ≤ a, with dp[0] = 0. Greedy does not work for arbitrary coin sets.
Show solution
def coin_change(coins, amount):
dp = [0] + [float("inf")] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
print(coin_change([1, 2, 5], 11), coin_change([2], 3), coin_change([186, 419, 83, 408], 6249))3 -1 20O(amount × coins).
8. Design an LRU cache#
Practice exercise
Implement get(key) and put(key, value) in O(1) with a fixed capacity, evicting the least recently used key.
Show hint
A hash map from keys to nodes, plus a doubly linked list ordered by use. In Python, collections.OrderedDict provides both: move_to_end marks use, popitem(last=False) evicts the oldest.
Show solution
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3) # evicts key 2
print(cache.get(2), cache.get(3))1
-1 3In an interview, be ready to build the linked list by hand too: see Doubly Linked Lists.
Key takeaway#
More practice: the DSA practice sets and DSA interview questions.
Finished this lesson?