Mixed Practice Problems

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 1 Time to complete: ~40 minutes

How to Work Through These
Two Sum
Valid Parentheses
Longest Substring Without Repeating Characters
Binary Tree Level Order Traversal
Number of Islands
Word Break
Kth Largest Element in an Array
Subsets
Summary & Next Steps

1. How to Work Through These

For each problem: read only the problem statement first, name the pattern yourself using Chapter 1's table, then reveal the labeled solution below and check your reasoning against it. Getting the pattern right matters more than getting the exact code right on the first try.

2. Two Sum

Problem: Given an array of integers and a target, return the indices of the two numbers that add up to the target. Pattern: Hash map (Module 8) — "find a pair summing to a target" without a sorted-array guarantee.

def two_sum(nums, target):
    seen = {}                              # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
    # O(n) time, O(n) space — one pass, O(1) average hash lookups

3. Valid Parentheses

Problem: Given a string of ()[]{}, determine if the brackets are balanced and correctly nested. Pattern: Stack (Module 5) — LIFO matching is the textbook stack use case.

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
 
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack
    # O(n) time, O(n) space

4. Longest Substring Without Repeating Characters

Problem: Given a string, find the length of the longest substring without repeating characters. Pattern: Sliding window (Module 2) + hash set (Module 8) — "longest substring satisfying a condition."

def length_of_longest_substring(s):
    seen = set()
    left = 0
    longest = 0
 
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        longest = max(longest, right - left + 1)
 
    return longest
    # O(n) time — each character enters and leaves the window at most once
    # O(min(n, alphabet size)) space for the set

5. Binary Tree Level Order Traversal

Problem: Return the values of a binary tree's nodes, grouped level by level. Pattern: BFS (Module 9) applied to a tree (Module 7) — level-by-level structure is BFS's signature.

from collections import deque
 
def level_order(root):
    if not root:
        return []
 
    result = []
    queue = deque([root])
 
    while queue:
        level_size = len(queue)
        level_values = []
        for _ in range(level_size):
            node = queue.popleft()
            level_values.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_values)
 
    return result
    # O(n) time — every node visited once; O(n) space for the queue/result

6. Number of Islands

Problem: Given a 2D grid of '1' (land) and '0' (water), count the number of islands (connected groups of land, horizontally/vertically adjacent). Pattern: DFS/graph traversal (Module 9) — a grid is just a graph where each cell is a node connected to its neighbors.

def num_islands(grid):
    if not grid:
        return 0
 
    rows, cols = len(grid), len(grid[0])
    visited = set()
 
    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == '0' or (r, c) in visited):
            return
        visited.add((r, c))
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
 
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                islands += 1
                dfs(r, c)
 
    return islands
    # O(rows × cols) time and space — every cell visited at most once

7. Word Break

Problem: Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of dictionary words. Pattern: Dynamic programming (Module 10) + hash set (Module 8) — "can this be built from smaller valid pieces" is a DP signal, and checking dictionary membership fast needs a set.

def word_break(s, word_dict):
    words = set(word_dict)                  # O(1) average membership check
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                            # empty prefix is trivially "breakable"
 
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
 
    return dp[n]
    # O(n² ) time (n positions × n possible split points, each substring check
    # amortized O(1) via the set) — O(n) space for the dp array

8. Kth Largest Element in an Array

Problem: Find the kth largest element in an unsorted array. Pattern: Heap (Module 7) — "kth largest/smallest" is the canonical heap signal.

import heapq
 
def find_kth_largest(nums, k):
    min_heap = nums[:k]
    heapq.heapify(min_heap)                  # O(k) to build
 
    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)  # pop smallest, push num
 
    return min_heap[0]
    # O(n log k) time — the heap never grows past size k
    # O(k) space

9. Subsets

Problem: Given an array of unique integers, return all possible subsets (the power set). Pattern: Backtracking (Module 4) — "generate all combinations" is the defining backtracking signal.

def subsets(nums):
    result = []
 
    def backtrack(start, current):
        result.append(current[:])            # record a copy of the current subset
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)         # choose
            current.pop()                     # un-choose (backtrack)
 
    backtrack(0, [])
    return result
    # O(2ⁿ) time and space — there are exactly 2ⁿ subsets to generate

10. Summary & Next Steps

Key Takeaways

Every problem above maps to exactly one primary row from Chapter 1's cheat sheet — that mapping, not the code itself, is the transferable skill.
Several problems (Longest Substring, Word Break) combine two techniques from two different modules — recognizing both signals is common in real interview problems.
If any of these took more than a few minutes to place correctly, revisit that pattern's module before moving to Chapter 3.

Concept Check

Which two problems in this set combine a hash-based lookup with another technique, and why does hashing help in each?
Why is Number of Islands framed as a graph problem even though the input is a 2D grid, not an explicit adjacency list?
What makes Subsets naturally exponential, and why is that considered acceptable here (unlike the exponential blowups flagged as problems in Module 1 and Module 10)?

Next Chapter

→ Chapter 3: Mock Interview-Style Questions

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index