Coding Problems Worked Out
Three commonly-named problems for AI engineering loops — Longest Common Prefix, Valid Anagram, Subarray Sum Equals K — plus eight common companions. Click to reveal solutions only after you've tried.
How to approach each problem out loud
Before solving anything, walk through this template. Practiced consistently, it makes you look senior even on problems you don't know.
- Restate: "Just to make sure I understand — you want me to..."
- Constraints: input size, sorted?, duplicates?, empty input?
- Example: trace a small case on paper or shared doc
- Brute force: mention it even if you'll discard it
- Pattern: consult the menu — hash map? two pointers? sliding window? DFS?
- State complexity: "brute force is O(n²); I think we can do O(n) with..."
- Code with narration: talk while you type
- Test: walk your code against the example
- Tradeoffs: time, space, edge cases, what you'd add for production
1Longest Common Prefix
StringMulti-pointer · LeetCode 14 · Easy
Prompt: Given an array of strings, return the longest common prefix. If none, return "".
["flower", "flow", "flight"] → "fl"
["dog", "racecar", "car"] → ""
["interspecies", "interstellar", "interstate"] → "inters"Edge cases to mention: empty input, one string, two strings where one is a prefix of another (["ab", "abc"] → "ab"), all empty strings.
Approach 1 — Vertical scan (cleanest, O(S))
Walk down the first string character by character, checking that every other string has the same character at that position.
def longest_common_prefix(strs):
if not strs:
return ""
for i in range(len(strs[0])):
c = strs[0][i]
for s in strs[1:]:
if i >= len(s) or s[i] != c:
return strs[0][:i]
return strs[0]Time: O(S) where S = sum of all characters across all strings — worst case you compare every char. Space: O(1).
Approach 2 — Horizontal scan
Compare the first two, get their prefix; compare that prefix to the third; etc.
def longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefixSame Big-O. Slightly worse worst case due to repeated startswith. Vertical scan is the cleaner default.
Approach 3 — Sort + compare endpoints (clever, slower)
Sort the array; the first and last strings are the most "different." The common prefix of the array is the common prefix of those two.
def longest_common_prefix(strs):
if not strs:
return ""
strs.sort()
first, last = strs[0], strs[-1]
i = 0
while i < len(first) and i < len(last) and first[i] == last[i]:
i += 1
return first[:i]Time: O(n log n × m) due to sort. Elegant; mention as an alternative if asked for variations.
What to say at the end
"Vertical scan in O(S) is the cleanest. Sort-and-compare-endpoints is elegant but slower; only worth it if amortized over many lookups."
2Valid Anagram
Hash TableString · LeetCode 242 · Easy
Prompt: Given two strings s and t, return True if t is an anagram of s.
"anagram", "nagaram" → True
"rat", "car" → FalseClarify: case sensitive? Unicode? Assume lowercase ASCII unless told otherwise. Different lengths → immediately False.
Approach 1 — Counter (cleanest)
from collections import Counter
def is_anagram(s, t):
if len(s) != len(t):
return False
return Counter(s) == Counter(t)Time: O(n). Space: O(k) where k = alphabet size.
Approach 2 — Sort and compare
def is_anagram(s, t):
return sorted(s) == sorted(t)Time: O(n log n). One-liner. Slower in Big-O, but Python's Timsort is fast in practice.
Approach 3 — Manual count (no Counter)
If they want you to show you can do it without library help:
def is_anagram(s, t):
if len(s) != len(t):
return False
counts = {}
for c in s:
counts[c] = counts.get(c, 0) + 1
for c in t:
if c not in counts:
return False
counts[c] -= 1
if counts[c] < 0:
return False
return TrueTime O(n), Space O(k).
Follow-up: what about Unicode? Streaming?
Unicode: Counter and dict-based approaches still work. The fixed-size int-array optimization (int[26]) doesn't apply.
Can't fit in memory: streaming Counter (one pass each), or external sort.
3Subarray Sum Equals K
ArrayHash TablePrefix Sum · LeetCode 560 · Medium
Prompt: Given an integer array nums and integer k, return the number of contiguous subarrays whose sum equals k. Numbers may be negative.
nums = [1, 1, 1], k = 2 → 2 (two [1,1] subarrays)
nums = [1, 2, 3], k = 3 → 2 ([1,2] and [3])Sliding window doesn't work here — nums can contain negatives, so the running sum isn't monotonic. The unlock is prefix sum + hash map.
Approach 1 — Brute force (state it, then beat it)
def subarray_sum_brute(nums, k):
count = 0
for i in range(len(nums)):
s = 0
for j in range(i, len(nums)):
s += nums[j]
if s == k:
count += 1
return countTime O(n²). Works for small inputs.
The insight (say this out loud before coding)
Define prefix[i] = sum of nums[0..i-1]. Then the sum of nums[i..j] equals prefix[j+1] - prefix[i].
We want subarrays where this equals k:
prefix[j+1] - prefix[i] = k
⇒ prefix[i] = prefix[j+1] - k
So as we walk through computing prefix sums, at each position j, we ask: "how many prior prefix sums equal (current_prefix - k)?" That count is the number of subarrays ending at j with sum k. Sum it.
Approach 2 — Optimal (prefix sum + hash map)
def subarray_sum(nums, k):
count = 0
prefix_sum = 0
sums_seen = {0: 1} # the "empty prefix" — see note below
for n in nums:
prefix_sum += n
if prefix_sum - k in sums_seen:
count += sums_seen[prefix_sum - k]
sums_seen[prefix_sum] = sums_seen.get(prefix_sum, 0) + 1
return countTime: O(n). Space: O(n).
{0: 1} at the start
We initialize the map with {0: 1} to handle subarrays that start at index 0. Without it, when prefix_sum == k at some point, we'd miss counting the subarray nums[0..i]. Always say this aloud — interviewers love when you explain the empty-prefix trick.
Walk-through: [1, 1, 1], k = 2
Start: count=0, prefix=0, seen={0:1}
See 1: prefix=1. prefix-k=-1 not in seen. seen={0:1, 1:1}
See 1: prefix=2. prefix-k=0 in seen (count 1) → count=1. seen={0:1, 1:1, 2:1}
See 1: prefix=3. prefix-k=1 in seen (count 1) → count=2. seen={0:1, 1:1, 2:1, 3:1}
Return: 2 ✓
4Two Sum
Hash TableArray · LeetCode 1 · Easy · The universal warmup
Prompt: Given nums and target, return indices of two numbers that sum to target. Assume exactly one solution.
Solution — hash map, one pass
def two_sum(nums, target):
seen = {} # value → index
for i, n in enumerate(nums):
complement = target - n
if complement in seen:
return [seen[complement], i]
seen[n] = i
return []Time: O(n). Space: O(n). The pattern — "look for the complement in a hash map as you iterate, store the current" — appears in dozens of problem variations.
5Group Anagrams
Hash TableStringSort · LeetCode 49 · Medium
Prompt: Group strings that are anagrams of each other.
["eat","tea","tan","ate","nat","bat"]
→ [["eat","tea","ate"], ["tan","nat"], ["bat"]]Solution — defaultdict with sorted-string keys
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for word in words:
key = ''.join(sorted(word))
groups[key].append(word)
return list(groups.values())Time: O(n × m log m) where m = average word length. Space: O(n × m).
Faster key: a tuple of 26 char counts gives O(n × m) but is rarely worth the complexity in an interview.
6Number of Islands
DFSGrid · LeetCode 200 · Medium · DFS classic
Prompt: Given a grid of '1' (land) and '0' (water), count connected components of land. Diagonals don't connect.
Solution — DFS, mark visited by mutating
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 or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited (mutates — clarify!)
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 countTime: O(rows × cols). Space: O(rows × cols) recursion in worst case.
If interviewer says "don't mutate input": use a visited set instead. Mention it; mutation is cleanest if allowed.
7Maximum Subarray
ArrayKadane · LeetCode 53 · Medium
Prompt: Find the contiguous subarray with the largest sum.
Solution — Kadane's algorithm
def max_subarray(nums):
best = current = nums[0]
for n in nums[1:]:
current = max(n, current + n)
best = max(best, current)
return bestTime: O(n). Space: O(1).
The insight: at each position, decide — extend the previous subarray or start fresh. Whichever is bigger. current = max(n, current + n) captures both choices.
8Valid Palindrome
StringTwo Pointers · LeetCode 125 · Easy
Prompt: Determine if a string is a palindrome considering only alphanumeric characters and ignoring case.
Solution — two pointers from both ends
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return TrueTime: O(n). Space: O(1).
9Longest Substring Without Repeating Characters
Sliding WindowHashString · LeetCode 3 · Medium
Prompt: Find the length of the longest substring with all distinct characters.
Solution — sliding window with last-seen map
def longest_unique_substring(s):
last_seen = {}
left = 0
best = 0
for right, c in enumerate(s):
if c in last_seen and last_seen[c] >= left:
left = last_seen[c] + 1
last_seen[c] = right
best = max(best, right - left + 1)
return bestTime: O(n). Space: O(k) bounded by alphabet.
Key detail: last_seen[c] >= left. A character "reset" only matters if it's still inside the current window.
10Validate Binary Search Tree
DFSTree · LeetCode 98 · Medium
Prompt: Determine if a binary tree is a valid BST.
The naïve trap (don't do this)
Comparing each node only to node.left and node.right is wrong. A node's value must be bounded by all ancestors, not just its parent.
Solution — DFS with bounds inherited from ancestors
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val)
and is_valid_bst(root.right, root.val, high))Time: O(n). Space: O(h) recursion (h = tree height).
Alternative: in-order traversal yields sorted sequence in a valid BST; check that it's strictly increasing.
11Merge Intervals
SortArray · LeetCode 56 · Medium
Prompt: Given intervals, merge all overlapping ones.
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]Solution — sort by start, sweep
def merge(intervals):
if not intervals: return []
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 mergedTime: O(n log n) from the sort. Space: O(n).
The pattern — sort by start, then sweep linearly — generalizes to "calendar" / "meeting room" / "schedule conflict" problems.
Drill protocol
For each problem:
- Toggle Drill mode at the top to hide solutions.
- Set a timer — 25 min for first pass, 10 min for re-solves.
- Code from scratch. Talk out loud (yes, even alone — builds the muscle).
- State complexity at the end.
- Reveal the solution. Note differences.
- Mark as practiced. Re-solve from memory the next day.
You're not memorizing — you're building pattern recognition. When you see "find subarrays with sum X" your brain should fire prefix sum + hash map before you reach for a brute force.