Category G · 7 Problems

Classic Algorithms

Binary search, BFS, dynamic programming, patience sorting. These are the canonical algorithms every Python engineer should be able to implement cleanly from memory.

Problems: 7
Difficulty: Medium – Hard
Key tools: bisect · deque · heapq · DP array
Before coding, always state: (1) the approach/algorithm name, (2) time complexity, (3) space complexity. For DP problems, define dp[i] clearly before writing any code. For BFS/DFS, explain why you chose that over the other.
P 46 Coding Problem Hard
Binary Search on Answer — Ship Packages in D Days
A ship must transport weights packages in order (no reordering) within D days. Find the minimum capacity of the ship. The ship loads packages each day until the next package would exceed capacity; then it sails.
Example
ship_in_days([1,2,3,4,5,6,7,8,9,10], D=5) → 15 # Day 1:[1,2,3,4,5], Day2:[6,7], Day3:[8], Day4:[9], Day5:[10] ship_in_days([3,2,2,4,1,4], D=3) → 6 ship_in_days([1,2,3,1,1], D=4) → 3
binary search on answerfeasibility check function lo = max(weights), hi = sum(weights)greedy load simulation
Solution
from typing import List def ship_in_days(weights: List[int], D: int) -> int: def can_ship(capacity: int) -> bool: # Greedily simulate: how many days does this capacity need? days = 1 load = 0 for w in weights: if load + w > capacity: days += 1 load = 0 load += w return days <= D # Search space: must carry heaviest package (lo), could send all at once (hi) lo, hi = max(weights), sum(weights) while lo < hi: mid = (lo + hi) // 2 if can_ship(mid): hi = mid # mid works; try smaller else: lo = mid + 1 # mid too small; need more return lo
Binary search on the answer: Instead of searching for an element in an array, we binary search for the minimum value (capacity) that satisfies a condition. The search space is [max(weights), sum(weights)] — the minimum possible capacity is the largest single package; the maximum is shipping everything in one day. The feasibility check (can_ship) is O(n). Binary search runs O(log(sum)) times. Total: O(n log(sum)).
P 47 Coding Problem Medium
BFS Shortest Path in a Maze
Given a 2D grid where 0 = open and 1 = wall, find the length of the shortest path from the top-left cell to the bottom-right cell. You can move in all 8 directions. Return -1 if no path exists.
Example
grid = [[0,0,0], [1,1,0], [1,1,0]] shortest_path(grid) → 4 # (0,0)→(0,1)→(0,2)→(1,2)→(2,2) — wait, that's 5 cells # Actually path length = number of cells visited = 4 steps
BFS with dequevisited set of (row, col) tuples 8-directional movementstep count in queue
Solution
from collections import deque from typing import List def shortest_path(grid: List[List[int]]) -> int: rows, cols = len(grid), len(grid[0]) if grid[0][0] == 1 or grid[rows-1][cols-1] == 1: return -1 queue = deque([((0, 0), 1)]) # ((row, col), steps) visited = {(0, 0)} dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] while queue: (r, c), steps = queue.popleft() if r == rows - 1 and c == cols - 1: return steps for dr, dc in dirs: nr, nc = r + dr, c + dc if (0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in visited): visited.add((nr, nc)) queue.append(((nr, nc), steps + 1)) return -1 # no path found
Why BFS? BFS guarantees the shortest path in an unweighted graph because it explores nodes level by level (by distance from start). Mark cells as visited when they are enqueued (not dequeued) to avoid adding them multiple times. Store the step count in the queue tuple — increment by 1 each time you move to a neighbour. Time: O(rows × cols). Space: O(rows × cols) for the visited set.
P 48 Coding Problem Medium
Coin Change — Minimum Coins (DP)
Given a list of coin denominations and a target amount, find the minimum number of coins needed to make that amount. You have an infinite supply of each coin. Return -1 if the amount cannot be made.
Example
coin_change([1,5,11], amount=15) → 3 # 5+5+5 coin_change([1,5,11], amount=16) → 2 # 11+5 coin_change([2], amount=3) → -1 # impossible
bottom-up DPdp[i] = min coins for amount i inner coin loopfloat("inf") sentinel
Solution
from typing import List def coin_change(coins: List[int], amount: int) -> int: # dp[i] = minimum number of coins to make exactly amount i dp = [float("inf")] * (amount + 1) dp[0] = 0 # base case: 0 coins needed to make amount 0 for coin in coins: for i in range(coin, amount + 1): # Either don't use this coin (dp[i]) or use it (dp[i-coin] + 1) dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float("inf") else -1
DP definition: dp[i] = minimum coins to make amount i. Transition: dp[i] = min(dp[i], dp[i - coin] + 1) — either skip this coin, or use it once (which reduces the remaining amount by coin). The outer loop iterates over coins; the inner loop fills the DP table. This is the "unbounded knapsack" pattern — you can use each coin unlimited times. Time: O(amount × len(coins)). Space: O(amount).
P 49 Coding Problem Hard
Longest Increasing Subsequence (LIS)
Find the length of the longest strictly increasing subsequence in a list. A subsequence does not need to be contiguous. O(n²) DP gets partial credit. The O(n log n) patience-sort approach gets full credit.
Example
lis_length([10,9,2,5,3,7,101,18]) → 4 # [2,3,7,101] or [2,5,7,101] lis_length([0,1,0,3,2,3]) → 4 # [0,1,2,3] lis_length([7,7,7,7,7]) → 1 # all same, no increasing
patience sorting intuitionbisect.bisect_left tails array (smallest tail for each LIS length)
Solution
import bisect from typing import List def lis_length(nums: List[int]) -> int: # tails[i] = smallest tail element of any LIS of length i+1 tails: list = [] for n in nums: # Find the leftmost position in tails where n can replace pos = bisect.bisect_left(tails, n) if pos == len(tails): tails.append(n) # n extends the longest subsequence else: tails[pos] = n # n replaces a larger tail — same length, better future return len(tails)
Patience sorting intuition: Think of tails as "piles" in patience sort. tails[i] stores the smallest possible tail value for an increasing subsequence of length i+1. For each number: binary search for where it fits. If it's larger than all tails, extend; otherwise, replace the first tail ≥ n. The length of tails at the end equals the LIS length (though tails itself is not the actual subsequence). Time: O(n log n). Space: O(n).
P 50 Coding Problem Hard
Word Ladder
Given a begin_word, end_word, and a word_list, find the length of the shortest transformation sequence from begin to end where each step changes exactly one letter and every intermediate word must be in the word list. Return 0 if no such sequence exists.
Example
word_ladder("hit","cog",["hot","dot","dog","lot","log","cog"]) → 5 # hit→hot→dot→dog→cog (5 words = 4 transformations) word_ladder("hit","cog",["hot","dot","dog","lot","log"]) → 0 # "cog" not in list
BFS level by levelset for O(1) word lookup enumerate alphabet for neighboursvisited set
Solution
from collections import deque from typing import List def word_ladder(begin: str, end: str, word_list: List[str]) -> int: word_set = set(word_list) if end not in word_set: return 0 queue = deque([(begin, 1)]) # (word, sequence_length) visited = {begin} while queue: word, length = queue.popleft() for i in range(len(word)): for ch in "abcdefghijklmnopqrstuvwxyz": next_word = word[:i] + ch + word[i+1:] if next_word == end: return length + 1 if next_word in word_set and next_word not in visited: visited.add(next_word) queue.append((next_word, length + 1)) return 0
Key ideas: BFS naturally finds the shortest path — each level represents one transformation. Generate neighbours by trying all 26 letters at each position — O(26 × word_length) per word. Use a set for word_list to make membership checking O(1) instead of O(n). Add words to visited when enqueued, not dequeued, to avoid redundant processing. Time: O(M² × N) where M = word length, N = word list size.
P 51 Coding Problem Easy
K Closest Points to Origin
Given a list of [x, y] points and integer k, return the k points closest to the origin (0, 0). Distance is Euclidean. Order within the k results doesn't matter. Do not compute the square root — compare squared distances to avoid floating-point issues.
Example
k_closest([[1,3],[-2,2]], k=1) → [[-2,2]] k_closest([[3,3],[5,-1],[-2,4]], k=2) → [[3,3],[-2,4]]
heapq.nsmallestlambda key: x²+y² avoid sqrtO(n log k)
Solution
import heapq from typing import List def k_closest(points: List[List[int]], k: int) -> List[List[int]]: # heapq.nsmallest with a key function — O(n log k) return heapq.nsmallest( k, points, key=lambda p: p[0]**2 + p[1]**2 )
Key ideas: heapq.nsmallest(k, iterable, key=...) is the Pythonic way to find the k smallest items. It uses a max-heap of size k internally: O(n log k) vs O(n log n) for a full sort. The key x² + y² is the squared Euclidean distance — monotonic with actual distance, so no sqrt needed. For the alternative (sort-based) approach: sorted(points, key=lambda p: p[0]**2+p[1]**2)[:k] — simpler but O(n log n).
P 52 Coding Problem Medium
Unique Paths in a Grid (DP)
A robot sits at the top-left of an m × n grid. It can only move right or down. How many unique paths are there from top-left to bottom-right? Count all distinct routes.
Example
unique_paths(3, 7) → 28 unique_paths(3, 2) → 3 unique_paths(1, 1) → 1
2D DP tabledp[r][c] = dp[r-1][c] + dp[r][c-1] base case: first row and column = 1
Solution
def unique_paths(m: int, n: int) -> int: # dp[r][c] = number of ways to reach cell (r, c) dp = [[1] * n for _ in range(m)] # First row and first column have only 1 path each (go straight right or down) for r in range(1, m): for c in range(1, n): # Paths to (r,c) = paths from above + paths from left dp[r][c] = dp[r-1][c] + dp[r][c-1] return dp[m-1][n-1]
DP definition: dp[r][c] = number of unique paths to reach cell (r, c). Base case: the first row and first column each have exactly 1 path (robot can only go right or down respectively). Transition: dp[r][c] = dp[r-1][c] + dp[r][c-1] — reach from above or from the left. The 2D list initialised to all 1s handles the base cases implicitly. Time: O(m×n). Space: O(m×n). Can be optimised to O(n) using a 1D rolling array.
← Category F: Data Structures Category H: Real-world →