Related chapters: Data Structures, Performance, Design Patterns

Implement binary search on a sorted list. Return the index or -1 if not found.

  binary_search([1, 3, 5, 7, 9, 11], 7)   # 3
binary_search([1, 3, 5, 7, 9, 11], 4)   # -1

Must be O(log n). Do not use Python’s bisect module.

Exercise 2: Bubble Sort

Implement bubble sort and count the number of swaps made.

  sort_and_count([5, 3, 1, 4, 2])
# ([1, 2, 3, 4, 5], 7)

Then implement a version that stops early if the list is already sorted.

Exercise 3: Flatten Nested List

Flatten arbitrarily nested lists:

  flatten([1, [2, 3], [4, [5, 6]], 7])
# [1, 2, 3, 4, 5, 6, 7]

Solve with recursion and with an iterative approach.

Exercise 4: Valid Parentheses

Check if a string of brackets is balanced:

  is_valid("()[]{}")     # True
is_valid("([)]")       # False
is_valid("{[]}")       # True

Use a stack.

Exercise 5: Longest Substring

Find the length of the longest substring without repeating characters:

  longest_unique("abcabcbb")  # 3 ("abc")
longest_unique("bbbbb")     # 1 ("b")
longest_unique("pwwkew")    # 3 ("wke")

Exercise 6: Merge Sorted Lists

Merge two sorted lists into one sorted list:

  merge([1, 3, 5, 7], [2, 4, 6, 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Do it in O(n) time and O(n) space. Bonus: do it in-place if given linked lists.

Challenge: Rate Limiter

Implement a RateLimiter(max_calls, period_seconds) class:

  limiter = RateLimiter(max_calls=3, period_seconds=10)

limiter.allow()  # True
limiter.allow()  # True
limiter.allow()  # True
limiter.allow()  # False — exceeded 3 calls in 10 seconds
# ... wait 10 seconds ...
limiter.allow()  # True

This pattern is used in API gateways and web applications. See Design Patterns and Security.

Solution (Exercise 4) 
  def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in s:
        if char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return not stack

Exercise 7: Quick Sort

Implement quicksort in-place. Return the sorted list.

  quicksort([5, 3, 1, 4, 2])  # [1, 2, 3, 4, 5]

Exercise 8: BFS Shortest Path

Given an unweighted graph as adjacency dict, return shortest path length from start to end.

  graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
shortest_path_length(graph, "A", "E")  # 3
Hint

Use a queue for BFS. Track visited nodes and distance from start.

Ready for projects? Start the Todo CLI or REST API.