Drill — Solutions Hidden by Default

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.

🎯 11 problems 🐍 Python ⏱ ~25 min each on first pass 🔁 Practice tracker saves locally
0 / 11 practiced

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.

  1. Restate: "Just to make sure I understand — you want me to..."
  2. Constraints: input size, sorted?, duplicates?, empty input?
  3. Example: trace a small case on paper or shared doc
  4. Brute force: mention it even if you'll discard it
  5. Pattern: consult the menu — hash map? two pointers? sliding window? DFS?
  6. State complexity: "brute force is O(n²); I think we can do O(n) with..."
  7. Code with narration: talk while you type
  8. Test: walk your code against the example
  9. Tradeoffs: time, space, edge cases, what you'd add for production

Pattern recognition menu

When you see a problem, scan this:

Problem says...Likely pattern
"Find pair / triplet summing to..."Hash map (or two pointers if sorted)
"Subarray / substring with property..."Sliding window / prefix sum
"Sorted array..."Two pointers, binary search
"Frequency / count / duplicates..."Hash map
"Tree / graph traversal..."DFS or BFS
"Shortest path / level by level..."BFS
"All paths / combinations..."DFS / backtracking
"Top K / Kth largest..."Heap or quickselect
"Anagram / palindrome..."Char counts (hash) or two pointers
"Overlapping intervals..."Sort by start, sweep

1Longest Common Prefix

StringMulti-pointer · LeetCode 14 · Easy

Prompt: Given an array of strings, return the longest common prefix. If none, return "".

examples
["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.

vertical_scan.py
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.

horizontal_scan.py
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 prefix

Same 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.

sort_endpoints.py
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.

examples
"anagram", "nagaram" → True
"rat", "car"         → False

Clarify: case sensitive? Unicode? Assume lowercase ASCII unless told otherwise. Different lengths → immediately False.

Approach 1 — Counter (cleanest)
counter.py
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
sort_compare.py
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:

manual_count.py
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 True

Time 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.

examples
nums = [1, 1, 1], k = 2  →  2  (two [1,1] subarrays)
nums = [1, 2, 3], k = 3  →  2  ([1,2] and [3])
Common trap

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)
brute.py
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 count

Time 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)
optimal.py
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 count

Time: O(n). Space: O(n).

Why {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
two_sum.py
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.

example
["eat","tea","tan","ate","nat","bat"]
→ [["eat","tea","ate"], ["tan","nat"], ["bat"]]
Solution — defaultdict with sorted-string keys
group_anagrams.py
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
num_islands.py
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 count

Time: 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
kadane.py
def max_subarray(nums):
    best = current = nums[0]
    for n in nums[1:]:
        current = max(n, current + n)
        best = max(best, current)
    return best

Time: 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
valid_palindrome.py
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 True

Time: 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
longest_unique.py
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 best

Time: 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
validate_bst.py
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.

example
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
Solution — sort by start, sweep
merge_intervals.py
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 merged

Time: 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:

  1. Toggle Drill mode at the top to hide solutions.
  2. Set a timer — 25 min for first pass, 10 min for re-solves.
  3. Code from scratch. Talk out loud (yes, even alone — builds the muscle).
  4. State complexity at the end.
  5. Reveal the solution. Note differences.
  6. 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.

✓ Check yourself

Answer from memory before opening each one.

  1. Group Anagrams runs on a million words averaging eight letters. Compare a sorted-string key with a tuple of letter counts. Which do you use?

    Show answer

    Sorting each word costs m log m, so the total is n m log m; a count tuple costs m per word, so n m. For short words the difference is small and the sorted key is simpler, so use it. Reach for the count key only when words are long. See Group Anagrams.

  2. Walk the prefix-sum solution for [3, -3, 3] with k = 3. What count does it end on, and which subarrays are they?

    Show answer

    It ends on three: the first element, the whole array, and the last element. The running sums are 3, 0, 3. The first step finds the seeded zero, and the third step finds two earlier prefixes of zero, the seed and the one after the second element, so it adds two. See Subarray Sum Equals K.

  3. Remove the {0: 1} seed from the Subarray Sum solution and run [3] with k = 3. What happens, and what does it show?

    Show answer

    It returns zero instead of one: the prefix sum is 3, the needed earlier prefix is 0, and without the seed that zero is not in the map. The seed stands for the empty prefix, which is how subarrays that begin at index zero get counted. See Subarray Sum Equals K.

  4. In Number of Islands the interviewer says not to modify the input grid. What changes, and what do you watch for with deep recursion?

    Show answer

    Keep a visited set of coordinates instead of overwriting cells, which costs extra space proportional to the land cells. A long snake-shaped island can push recursion past Python's limit, so an explicit stack is the safer form. Mention both trade-offs. See Number of Islands.

  5. A tree has root 10, a left child 5, and a right child 15 whose left child is 6. Why does comparing each node only with its parent say it is valid, and what is the correct check?

    Show answer

    The 6 is below the right child but smaller than the root, which a BST forbids. Each node must stay within bounds inherited from all its ancestors, so pass a low and a high bound down the recursion; for the 6, the low bound is 10. See Validate BST.

  6. In the longest-substring solution, why must you test that the last seen index is at least the left edge? Give an input that breaks without it.

    Show answer

    A repeat that sits left of the window no longer matters, and without the test the left edge can jump backwards and count a window that contains a repeat. On "abba", the final "a" was last seen at index 0, outside the window starting at 2, and without the check the answer is 3 instead of 2. See Longest Substring Without Repeating Characters.

Takeaway

  • State the brute force first, then the pattern that beats it, then the complexity.
  • Subarray Sum Equals K needs prefix sums and a hash map, because negative numbers break a sliding window.
  • Seed the prefix-sum map with zero once, or subarrays that start at index zero are never counted.
  • Anagram and grouping problems reduce to character counts or sorted keys; choose the key by word length.
  • Grid and tree problems are DFS, and a BST check needs bounds from every ancestor, not just the parent.
  • In a sliding window with a last-seen map, ignore entries that sit left of the window.
  • Sort then sweep solves interval problems in n log n.

Coding rounds test fluency; the next chapter returns to production, with the data pipelines that feed and follow the model. → Data Pipelines for AI

Further reading

  • collections: Container datatypes — Python Software Foundation, accessed 2026. Counter and defaultdict, used in several solutions here.
  • Sorting Techniques — Python Software Foundation, accessed 2026. Key functions and stability, which the interval and anagram solutions rely on.
  • 560. Subarray Sum Equals K — LeetCode, accessed 2026. The problem statement and constraints for the prefix-sum exercise.
  • 98. Validate Binary Search Tree — LeetCode, accessed 2026. The problem statement, with the cases that defeat the parent-only check.