Build an Interview Pattern Toolkit

Implement 5 top FAANG algorithm patterns in Python with a test runner.

Introduction

30 Second Summary

Coding interviews test pattern recognition, not just coding ability. The difference between passing and failing often comes down to recognizing which algorithm pattern fits the problem within the first 30 seconds.

In this project, you will build an Interview Pattern Toolkit in Python: five algorithm modules that each solve a classic coding interview problem using one of the most-tested patterns, tied together by a test runner that validates your solutions and times their execution.

What You'll Build

A Python-based toolkit containing 5 pattern modules (Two Pointers, Sliding Window, Hash Map, Binary Search, Monotonic Stack) with a test runner that validates and times each solution.

By the end of this project, you'll have:

  • 5 pattern modules each solving a canonical interview problem with documented strategy and complexity analysis.
  • A test runner that validates all solutions and reports pass/fail with execution time.
  • Pattern recognition guides embedded in each module with signal phrases that tell you which pattern to apply during a live interview.
  • Secret Mission: Add a 6th pattern (BFS) by implementing Number of Islands to cover graph traversal.

Are there any prerequisites?

This project assumes intermediate Python knowledge. You should be comfortable with functions, loops, lists, dictionaries, and list comprehensions.

No external packages are required. The toolkit uses only the Python standard library.

Before We Start

You're about to build a toolkit that solves five classic coding interview problems. Each solution uses one of the most-tested algorithm patterns at companies like Google, Meta, and Amazon.

First, let's confirm your Python setup and create the project folder with all six files you'll need.

In this step, get ready to:
  • Verify your Python version is 3.9 or higher.
  • Create the interview_toolkit project folder with 6 pattern files.
  • Open the project in VS Code.
Open VS Code and the integrated terminal

Everything in this project happens inside VS Code's integrated terminal. Let's open VS Code first, then launch a terminal panel inside it.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Visual Studio Code and press Enter to open it.
  • Open the integrated terminal by pressing Ctrl+` (macOS and Windows).

What is the integrated terminal?

VS Code has a built-in terminal panel at the bottom of the window. It works exactly like a standalone terminal, but keeps everything in one place so you don't have to switch between apps.

Verify your Python version

This project uses type hint syntax (list[int]) that requires Python 3.9 or higher.

  • Check your Python version by running this command:

macOS

python3 --version

Windows

python --version

You should see a version number of 3.9 or higher in the output (for example, Python 3.14.5).

Seeing a version lower than 3.9?

Download the latest Python from python.org/downloads and run the installer. After installing, close and reopen VS Code's terminal, then run the version check again.

On macOS, the system Python may be older. The python.org installer adds a newer python3 binary that takes priority.

help me troubleshoot my Python version

Create the project folder and pattern files

Your toolkit lives in a single folder with six Python files. Five are pattern modules (one per algorithm pattern) and the sixth is a test runner that validates them all.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create the project folder and move into it by running these commands:
mkdir interview_toolkit
cd interview_toolkit
  • Create all six pattern files by running this command:

macOS

touch two_pointers.py sliding_window.py hash_map.py binary_search.py monotonic_stack.py runner.py

Windows

New-Item -ItemType "File" -Path "two_pointers.py", "sliding_window.py", "hash_map.py", "binary_search.py", "monotonic_stack.py", "runner.py"
  • Confirm the files exist by running:
ls

You should see all six files listed: two_pointers.py, sliding_window.py, hash_map.py, binary_search.py, monotonic_stack.py, and runner.py.

Don't see all six files?

Make sure you're inside the interview_toolkit folder when you run ls. If you see an empty list, re-run the touch or New-Item command from above.

help me create the six pattern files in my interview_toolkit folder

  • Now open this folder in VS Code. Click File in the top menu bar.
  • Click Open Folder.
  • Navigate to your Desktop, select the interview_toolkit folder, and click Open.

You should see all six .py files listed in the Explorer sidebar on the left.

Why six separate files?

Each pattern gets its own module so you can study, run, and test them independently. The runner.py file ties everything together at the end.

This mirrors how real interview prep works: practice one pattern at a time, then combine.

Your project structure is ready. Next up, you'll implement the first two patterns: Two Pointers and Sliding Window.

Set Up the Project Structure

Before you implement any algorithm, you need a way to validate that your solutions actually work. The test runner is the backbone of your toolkit.

In this step, you will open your project in VS Code and build a test runner skeleton that times each solution, compares output against expected values, and reports pass/fail results. Every pattern module you build later plugs directly into this runner.

In this step, get ready to:
  • Open the interview_toolkit folder in VS Code.
  • Build the test runner with timing, normalization, and pass/fail reporting.
Open the project in VS Code

Your interview_toolkit folder already has six empty Python files waiting for code. Loading the folder in VS Code gives you a file tree in the sidebar so you can switch between modules quickly.

  • In VS Code, click File in the top menu bar.
  • Click Open Folder.
  • Navigate to your Desktop, select the interview_toolkit folder, then click Open.

You should see all six files listed in the Explorer sidebar on the left.

Build the test runner skeleton

The test runner has three responsibilities: import all pattern solutions, run them against test cases with timing, and report a summary. You will build it in three chunks.

  • In the Explorer sidebar, click runner.py to open it in the editor.
Add the imports and helper function
  • Paste the following code into runner.py:
import time

from two_pointers import max_area
from sliding_window import length_of_longest_substring
from hash_map import group_anagrams
from binary_search import search_rotated
from monotonic_stack import daily_temperatures


def normalize_groups(groups):
    """Sort group contents and group order for stable comparison."""
    return sorted([sorted(g) for g in groups])

What does this code do?

The import time line brings in Python's built-in timer so you can measure how fast each solution runs.

The five from ... import ... lines pre-wire each pattern module to the runner. The modules are empty right now, so you will not run this file until the patterns are implemented.

The normalize_groups helper sorts nested lists so that Group Anagrams output can be compared regardless of order.

Add the run_tests function

This is the core engine of your runner. It accepts any pattern function, feeds it test cases, times execution, and prints pass/fail for each case.

  • Below the normalize_groups function, add the following code:
def run_tests(name, func, test_cases, normalize=None):
    """Run test cases for a pattern and report results."""
    print(f"\n{'='*55}")
    print(f"  {name}")
    print(f"{'='*55}")
    all_passed = True

    for i, (args, expected) in enumerate(test_cases, 1):
        start = time.perf_counter()
        if isinstance(args, tuple):
            result = func(*args)
        else:
            result = func(args)
        elapsed = (time.perf_counter() - start) * 1000

        check_result = normalize(result) if normalize else result
        check_expected = normalize(expected) if normalize else expected
        passed = check_result == check_expected
        status = "PASS" if passed else "FAIL"
        print(f"  Test {i}: {status} ({elapsed:.4f}ms)")

        if not passed:
            print(f"         Expected: {expected}")
            print(f"         Got:      {result}")
            all_passed = False

    return all_passed

What does this code do?

The run_tests function takes four arguments: a display name, the function to test, a list of (input, expected) pairs, and an optional normalizer.

For each test case, it starts a high-resolution timer with time.perf_counter(), calls the function, then calculates elapsed milliseconds. The isinstance(args, tuple) check handles functions that take multiple arguments (like Binary Search which takes a list and a target).

If a test fails, it prints both the expected and actual values so you can debug quickly.

Add the main function and entry point

The main function is where you will plug in test cases for each pattern. For now, it prints a header and an empty results summary.

  • Below the run_tests function, add the following code:
def main():
    print("\n" + "=" * 55)
    print("  INTERVIEW PATTERN TOOLKIT - Test Runner")
    print("=" * 55)

    results = []

    # Pattern test cases will be added in later steps

    passed = sum(results)
    total = len(results)
    print(f"\n{'='*55}")
    print(f"  Results: {passed}/{total} patterns passing")
    if passed == total:
        print("  All patterns implemented correctly!")
    print(f"{'='*55}\n")


if __name__ == "__main__":
    main()

What does this code do?

The main function prints a banner, collects pass/fail results from each pattern's test suite, then prints a final summary showing how many patterns passed.

The results list is empty for now. In later steps, you will append run_tests(...) calls here as you implement each pattern.

The if __name__ == "__main__" guard ensures main() only runs when you execute runner.py directly.

  • Save runner.py by pressing Cmd+S (macOS) or Ctrl+S (Windows).

Why not run it yet?

The imports at the top reference functions like max_area and length_of_longest_substring that do not exist yet. Running runner.py right now would raise an ImportError because the pattern modules are still empty.

You will run the full suite in Step 4 after all five patterns are implemented.

Seeing a red squiggly line under the imports?

VS Code may show warnings because the pattern modules are empty. This is expected and will resolve once you add code to those files in the next steps.

help me understand why VS Code shows import warnings for empty modules

✔️ Awesome, I've got everything!

Great. Double check you have saved runner.py before moving on.

ⓧ I'd like to double check the full code

Here is the complete runner.py at this point:

import time

from two_pointers import max_area
from sliding_window import length_of_longest_substring
from hash_map import group_anagrams
from binary_search import search_rotated
from monotonic_stack import daily_temperatures


def normalize_groups(groups):
    """Sort group contents and group order for stable comparison."""
    return sorted([sorted(g) for g in groups])


def run_tests(name, func, test_cases, normalize=None):
    """Run test cases for a pattern and report results."""
    print(f"\n{'='*55}")
    print(f"  {name}")
    print(f"{'='*55}")
    all_passed = True

    for i, (args, expected) in enumerate(test_cases, 1):
        start = time.perf_counter()
        if isinstance(args, tuple):
            result = func(*args)
        else:
            result = func(args)
        elapsed = (time.perf_counter() - start) * 1000

        check_result = normalize(result) if normalize else result
        check_expected = normalize(expected) if normalize else expected
        passed = check_result == check_expected
        status = "PASS" if passed else "FAIL"
        print(f"  Test {i}: {status} ({elapsed:.4f}ms)")

        if not passed:
            print(f"         Expected: {expected}")
            print(f"         Got:      {result}")
            all_passed = False

    return all_passed


def main():
    print("\n" + "=" * 55)
    print("  INTERVIEW PATTERN TOOLKIT - Test Runner")
    print("=" * 55)

    results = []

    # Pattern test cases will be added in later steps

    passed = sum(results)
    total = len(results)
    print(f"\n{'='*55}")
    print(f"  Results: {passed}/{total} patterns passing")
    if passed == total:
        print("  All patterns implemented correctly!")
    print(f"{'='*55}\n")


if __name__ == "__main__":
    main()

Your test runner is ready and waiting for pattern implementations. Next up, you will write your first two algorithms and watch them pass real test cases.

Implement Two Pointers and Sliding Window

Your project structure is in place and the test runner is ready to validate solutions. Now it's time to write your first two algorithms.

Two Pointers and Sliding Window are the highest-yield patterns for a reason. They turn brute-force O(n²) solutions into elegant O(n) single-pass algorithms. In this step, you'll implement both from scratch and verify they produce correct results.

In this step, get ready to:
  • Implement Container With Most Water using the Two Pointers pattern.
  • Implement Longest Substring Without Repeating Characters using the Sliding Window pattern.
  • Run both modules individually to verify they produce correct output.
Implement Container With Most Water using Two Pointers

The Two Pointers pattern works by placing one pointer at each end of an array and moving them inward based on a condition. It eliminates the need to check every pair, reducing O(n²) brute force to O(n).

  • In VS Code, open two_pointers.py from the Explorer sidebar.
  • Add the pattern recognition guide at the top of the file by pasting this docstring:
"""
Pattern: Two Pointers
=====================
When to use:
- Sorted array or string
- Finding pairs/triplets that satisfy a condition
- Comparing elements from both ends
- Palindrome problems
- Container/area problems

Time: O(n) | Space: O(1)

Signal phrases: "sorted array", "pair that sums to", "container",
"palindrome", "two elements that..."
"""

What is this docstring for?

This is your pattern cheat sheet. During an interview, the signal phrases tell you when to reach for Two Pointers. If the problem mentions a sorted array, finding pairs, or comparing from both ends, this is your pattern.

O(n) time with O(1) space means you traverse the array once using only two index variables. No extra data structures needed.

  • Now add the max_area function below the docstring by pasting this code:

def max_area(height: list[int]) -> int:
    """
    Container With Most Water (LeetCode 11)

    Find two lines that together with the x-axis form a container
    that holds the most water.

    Strategy: Start with widest container (pointers at ends).
    Move the shorter line inward since it limits the height.
    """
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water


if __name__ == "__main__":
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # Expected: 49

What does this code do?

The algorithm starts with pointers at both ends of the height array. This gives the maximum width.

  • width = right - left calculates the distance between the two lines.
  • h = min(height[left], height[right]) uses the shorter line since water overflows at that height.
  • The if/else moves the shorter pointer inward. Moving the taller one can never increase the area.
  • Save two_pointers.py.

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on.

ⓧ I'd like to double check the full code

"""
Pattern: Two Pointers
=====================
When to use:
- Sorted array or string
- Finding pairs/triplets that satisfy a condition
- Comparing elements from both ends
- Palindrome problems
- Container/area problems

Time: O(n) | Space: O(1)

Signal phrases: "sorted array", "pair that sums to", "container",
"palindrome", "two elements that..."
"""


def max_area(height: list[int]) -> int:
    """
    Container With Most Water (LeetCode 11)

    Find two lines that together with the x-axis form a container
    that holds the most water.

    Strategy: Start with widest container (pointers at ends).
    Move the shorter line inward since it limits the height.
    """
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water


if __name__ == "__main__":
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # Expected: 49
Implement Longest Substring Without Repeating Characters using Sliding Window

The Sliding Window pattern maintains a dynamic window over a sequence, expanding and shrinking it to find optimal subarrays or substrings. Instead of checking every possible substring (O(n²)), you process each element at most twice.

  • Open sliding_window.py in VS Code.
  • Add the pattern recognition guide at the top of the file by pasting this docstring:
"""
Pattern: Sliding Window
=======================
When to use:
- Contiguous subarray or substring problems
- "Longest/shortest subarray with condition"
- "Maximum sum of subarray of size k"
- String matching with constraints

Time: O(n) | Space: O(k) where k = window contents

Signal phrases: "contiguous subarray", "substring", "longest",
"shortest", "window", "at most k distinct"
"""

What does this pattern guide tell you?

The signal phrases are your interview radar. When a problem says "longest substring" or "contiguous subarray with condition", your brain should immediately think Sliding Window.

The space complexity is O(k) because you store the window's contents (characters, counts, etc.) in a hash map. The window itself is just two index pointers.

  • Add the length_of_longest_substring function below the docstring by pasting this code:

def length_of_longest_substring(s: str) -> int:
    """
    Longest Substring Without Repeating Characters (LeetCode 3)

    Find the length of the longest substring without any
    repeating characters.

    Strategy: Expand window right. When a duplicate is found,
    shrink from left past the previous occurrence.
    """
    char_index = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length


if __name__ == "__main__":
    print(length_of_longest_substring("abcabcbb"))  # Expected: 3

What does this code do?

  • char_index is a dictionary tracking the last index where each character appeared.
  • The for loop expands the window rightward one character at a time.
  • When a repeated character is found inside the current window, left jumps past the previous occurrence. This shrinks the window instantly instead of sliding one position at a time.
  • max_length always holds the longest valid window seen so far.
  • Save sliding_window.py.

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on.

ⓧ I'd like to double check the full code

"""
Pattern: Sliding Window
=======================
When to use:
- Contiguous subarray or substring problems
- "Longest/shortest subarray with condition"
- "Maximum sum of subarray of size k"
- String matching with constraints

Time: O(n) | Space: O(k) where k = window contents

Signal phrases: "contiguous subarray", "substring", "longest",
"shortest", "window", "at most k distinct"
"""


def length_of_longest_substring(s: str) -> int:
    """
    Longest Substring Without Repeating Characters (LeetCode 3)

    Find the length of the longest substring without any
    repeating characters.

    Strategy: Expand window right. When a duplicate is found,
    shrink from left past the previous occurrence.
    """
    char_index = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length


if __name__ == "__main__":
    print(length_of_longest_substring("abcabcbb"))  # Expected: 3
Run both modules to verify correct output

Each module has a __main__ block that runs a quick sanity check. This lets you verify each pattern independently before wiring them into the test runner.

  • Run the Two Pointers module by executing this command in your terminal:
python3 two_pointers.py
  • You should see 49 printed in your terminal. This is the maximum water area for the input [1, 8, 6, 2, 5, 4, 8, 3, 7].
  • Run the Sliding Window module by executing this command:
python3 sliding_window.py
  • You should see 3 printed. The longest substring without repeating characters in "abcabcbb" is "abc" (length 3).

Seeing a SyntaxError or unexpected output?

  • Make sure you're running the command from inside the interview_toolkit folder. If not, use cd ~/Desktop/interview_toolkit to navigate there.
  • Check for stray characters or missing indentation. Python requires consistent indentation (4 spaces per level).
  • If you see a ModuleNotFoundError, you may be running the wrong file. Make sure you're running python3 two_pointers.py directly, not runner.py.

Help me debug my Two Pointers or Sliding Window output

Why run each module individually?

The full test runner imports all 5 pattern modules. Since the other 3 files are still empty, running runner.py now would fail with import errors. Testing each module on its own confirms your logic is correct before you wire everything together.

Two patterns down, three to go. Next up, you'll implement Hash Map and Binary Search to handle grouping problems and search-in-sorted-data problems at lightning speed.

Implement Hash Map and Binary Search

Your Two Pointers and Sliding Window patterns are locked in. Both solve problems in O(n) time by avoiding brute-force nested loops.

Now you'll tackle two patterns that show up in almost every interview loop. Hash Maps turn O(n²) lookups into O(1) by trading space for speed. Binary Search eliminates half the search space each step, giving you O(log n) performance on sorted data.

In this step, get ready to:
  • Implement Group Anagrams using the Hash Map pattern.
  • Implement Search in Rotated Sorted Array using Binary Search.
  • Run both modules individually to verify correct output.
Implement Group Anagrams with the Hash Map pattern

The classic interview question "Group Anagrams" asks you to group strings that are anagrams of each other. A brute-force approach compares every pair of strings, giving O(n²) time. The Hash Map pattern collapses this to O(n) by using a clever key.

  • In VS Code, open hash_map.py from the Explorer sidebar.
  • Paste the following code into the file:
"""
Pattern: Hash Map / Hash Set
============================
When to use:
- Need O(1) lookup to avoid nested loops
- Frequency counting
- Grouping elements by a property
- Finding duplicates or complements
- Converting O(n^2) brute force to O(n)

Time: O(n) | Space: O(n)

Signal phrases: "group by", "frequency", "duplicate", "complement",
"two sum", "anagram", "count occurrences"
"""

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    """
    Group Anagrams (LeetCode 49)

    Group strings that are anagrams of each other.

    Strategy: Use sorted characters as a hash key.
    All anagrams produce the same sorted key.
    """
    groups = defaultdict(list)

    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)

    return list(groups.values())


if __name__ == "__main__":
    result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    print(result)

What does this code do?

The module docstring at the top is your interview cheat sheet. It lists the signal phrases ("group by", "frequency", "anagram") that tell you this pattern applies.

The group_anagrams function uses a defaultdict to group strings by their sorted character tuples. Since all anagrams produce the same sorted key ("eat" and "tea" both sort to ('a', 'e', 't')), they land in the same bucket automatically.

  • Save hash_map.py.
  • You'll run this module in the verification substep coming up next.

Seeing a red underline on defaultdict?

Make sure the from collections import defaultdict line sits between the closing """ of the docstring and the function definition. If it is inside the docstring, Python treats it as text.

Help me fix my defaultdict import.

Implement Search in Rotated Sorted Array with Binary Search

Binary Search is the go-to pattern whenever a problem mentions "sorted array" or requires O(log n) performance. The twist here is that the array has been rotated, so you cannot do a simple left/right comparison. The key insight is that at any midpoint, one half of the array is always sorted.

  • Open binary_search.py in VS Code.
  • Paste the following code into the file:
"""
Pattern: Binary Search
======================
When to use:
- Sorted or rotated sorted array
- "Find position of element"
- "Minimum/maximum that satisfies condition"
- Search space can be halved each step
- Monotonic condition exists

Time: O(log n) | Space: O(1)

Signal phrases: "sorted array", "find target", "minimum speed/capacity",
"rotated", "search", "O(log n) required"
"""


def search_rotated(nums: list[int], target: int) -> int:
    """
    Search in Rotated Sorted Array (LeetCode 33)

    Find target in a sorted array that has been rotated.
    Return index or -1 if not found.

    Strategy: At each midpoint, one half is always sorted.
    Determine which half is sorted, then check if target
    falls within that sorted range.
    """
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1


if __name__ == "__main__":
    print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # Expected: 4

What does this code do?

The signal phrases in the docstring ("sorted array", "rotated", "find target") are your cues during an interview that Binary Search applies.

The search_rotated function works by checking which half of the array is sorted at each midpoint. If nums[left] <= nums[mid], the left half is sorted. You then check whether the target falls within that sorted range. If it does, narrow the search there. If not, search the other half.

Each iteration eliminates half the array, giving O(log n) time with O(1) space.

  • Save binary_search.py.
  • You'll run this module in the next substep.

Seeing a syntax error on the type hints?

The list[int] syntax requires Python 3.9 or higher. If you see an error like TypeError: 'type' object is not subscriptable, check your Python version with python3 --version.

Help me fix my type hint error.

Run both modules to verify correct output

Both pattern modules have a if __name__ == "__main__" block that runs a quick test when you execute the file directly. This lets you confirm each solution works before wiring it into the test runner.

  • Run the Hash Map module by running this command in your terminal:
python3 hash_map.py

You should see grouped anagrams printed as nested lists. The groups contain ["eat", "tea", "ate"], ["tan", "nat"], and ["bat"] (the order of groups may vary).

  • Run the Binary Search module by running this command:
python3 binary_search.py

You should see 4 printed. That is the index of 0 in the rotated array [4, 5, 6, 7, 0, 1, 2].

Seeing a ModuleNotFoundError?

Make sure your terminal is inside the interview_toolkit folder. Run ls to confirm you can see hash_map.py and binary_search.py listed.

Help me fix my ModuleNotFoundError.

Why does Group Anagrams output look different each run?

Python dictionaries maintain insertion order, but the order of groups depends on which string the loop encounters first. The important thing is that anagrams are grouped together correctly. The test runner handles this with a normalize_groups function that sorts everything before comparing.

✔️ Awesome, I've got everything!

Great. Make sure both files are saved before moving on.

ⓧ I'd like to double check the full code

Here is the complete hash_map.py:

"""
Pattern: Hash Map / Hash Set
============================
When to use:
- Need O(1) lookup to avoid nested loops
- Frequency counting
- Grouping elements by a property
- Finding duplicates or complements
- Converting O(n^2) brute force to O(n)

Time: O(n) | Space: O(n)

Signal phrases: "group by", "frequency", "duplicate", "complement",
"two sum", "anagram", "count occurrences"
"""

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    """
    Group Anagrams (LeetCode 49)

    Group strings that are anagrams of each other.

    Strategy: Use sorted characters as a hash key.
    All anagrams produce the same sorted key.
    """
    groups = defaultdict(list)

    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)

    return list(groups.values())


if __name__ == "__main__":
    result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    print(result)

Here is the complete binary_search.py:

"""
Pattern: Binary Search
======================
When to use:
- Sorted or rotated sorted array
- "Find position of element"
- "Minimum/maximum that satisfies condition"
- Search space can be halved each step
- Monotonic condition exists

Time: O(log n) | Space: O(1)

Signal phrases: "sorted array", "find target", "minimum speed/capacity",
"rotated", "search", "O(log n) required"
"""


def search_rotated(nums: list[int], target: int) -> int:
    """
    Search in Rotated Sorted Array (LeetCode 33)

    Find target in a sorted array that has been rotated.
    Return index or -1 if not found.

    Strategy: At each midpoint, one half is always sorted.
    Determine which half is sorted, then check if target
    falls within that sorted range.
    """
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1


if __name__ == "__main__":
    print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # Expected: 4

Two more patterns in the bag. You now have a Hash Map that collapses O(n²) lookups and a Binary Search that halves the problem each iteration. Next up, you'll implement the Monotonic Stack pattern and wire all five modules into the test runner.

Implement Monotonic Stack and Run All Tests

You now have four patterns implemented and passing individually. The last piece of your toolkit is the Monotonic Stack pattern, which handles a category of problems that trip up many candidates: finding the next greater or smaller element in a sequence.

After implementing this fifth pattern, you will wire all five modules into the test runner and execute the full suite. Seeing all five patterns pass in a single command is the moment your toolkit becomes a real, validated tool.

In this step, get ready to:
  • Implement Daily Temperatures using the Monotonic Stack pattern.
  • Connect all 5 pattern modules to the test runner with full test cases.
  • Run the complete test suite and verify all 5 patterns pass.
Implement Daily Temperatures with the Monotonic Stack pattern

The Monotonic Stack pattern maintains a stack where elements are always in increasing or decreasing order. When a new element breaks that order, you pop elements off and compute relationships between them. This gives you O(n) solutions to problems that would otherwise require nested loops.

  • Open monotonic_stack.py in VS Code and paste the following code:
"""
Pattern: Monotonic Stack
========================
When to use:
- "Next greater/smaller element" problems
- Need to look back at previous elements efficiently
- Finding spans or ranges in arrays
- Histogram problems
- Temperature / stock price patterns

Time: O(n) | Space: O(n)

Signal phrases: "next greater element", "next warmer day",
"largest rectangle", "stock span", "previous smaller"
"""


def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    Daily Temperatures (LeetCode 739)

    For each day, find how many days until a warmer temperature.
    Return 0 if no future day is warmer.

    Strategy: Maintain a stack of indices with decreasing temps.
    When a warmer day arrives, pop all cooler days and calculate
    the distance.
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # stores indices

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)

    return result


if __name__ == "__main__":
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
    # Expected: [1, 1, 4, 2, 1, 1, 0, 0]

What does this code do?

The module docstring at the top is your pattern recognition cheat sheet. It lists the signal phrases you will hear in an interview that tell you a Monotonic Stack is the right tool.

The daily_temperatures function solves the problem by keeping a stack of indices whose temperatures are in decreasing order. Each time a warmer day arrives, you pop indices off the stack and record how many days the gap was. Every element is pushed and popped at most once, giving O(n) total time.

  • Save monotonic_stack.py.
  • Run the module individually to verify it by running:
python monotonic_stack.py
  • You should see [1, 1, 4, 2, 1, 1, 0, 0] printed in the terminal.

Seeing a syntax error or wrong output?

  • Make sure the while condition inside the for loop uses temperatures[stack[-1]] < temp (strictly less than, not less-than-or-equal).
  • Confirm that result[prev_index] = i - prev_index is inside the while block, not outside it.

Help me debug my daily_temperatures function. I'm expecting [1, 1, 4, 2, 1, 1, 0, 0] but getting something different.

Connect all 5 pattern modules to the test runner

Your test runner already imports all five pattern functions. Now you need to fill in the main() function with the actual test cases for each pattern.

  • Open runner.py in VS Code.
  • Find this comment inside the main() function:
    # Pattern test cases will be added in later steps
  • Replace that comment with the following five run_tests calls:
    results.append(run_tests(
        "Two Pointers: Container With Most Water",
        max_area,
        [
            ([1, 8, 6, 2, 5, 4, 8, 3, 7], 49),
            ([1, 1], 1),
            ([4, 3, 2, 1, 4], 16),
        ]
    ))

    results.append(run_tests(
        "Sliding Window: Longest Substring Without Repeating",
        length_of_longest_substring,
        [
            ("abcabcbb", 3),
            ("bbbbb", 1),
            ("pwwkew", 3),
            ("", 0),
        ]
    ))

    results.append(run_tests(
        "Hash Map: Group Anagrams",
        group_anagrams,
        [
            (["eat", "tea", "tan", "ate", "nat", "bat"],
             [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]),
            ([""], [[""]]),
            (["a"], [["a"]]),
        ],
        normalize=normalize_groups
    ))

    results.append(run_tests(
        "Binary Search: Search in Rotated Sorted Array",
        search_rotated,
        [
            (([4, 5, 6, 7, 0, 1, 2], 0), 4),
            (([4, 5, 6, 7, 0, 1, 2], 3), -1),
            (([1], 0), -1),
            (([1], 1), 0),
        ]
    ))

    results.append(run_tests(
        "Monotonic Stack: Daily Temperatures",
        daily_temperatures,
        [
            ([73, 74, 75, 71, 69, 72, 76, 73], [1, 1, 4, 2, 1, 1, 0, 0]),
            ([30, 40, 50, 60], [1, 1, 1, 0]),
            ([30, 20, 10], [0, 0, 0]),
        ]
    ))

What does this code do?

Each run_tests call passes a pattern name, the function to test, and a list of (input, expected output) pairs. The runner times each call and reports PASS or FAIL.

The Group Anagrams test uses normalize=normalize_groups because dictionaries do not guarantee insertion order. The normalizer sorts each group and sorts the list of groups so the comparison is stable regardless of output ordering.

  • Save runner.py.

Seeing indentation errors?

  • All five results.append(...) calls must be indented one level inside main(). They sit at the same indentation as the results = [] line above them.
  • Make sure the old comment line is fully deleted. Leaving a stray # can cause unexpected behavior.

Help me fix indentation in my runner.py file.

✔️ Awesome, I've got everything!

Great. Double check you have saved both monotonic_stack.py and runner.py.

ⓧ I'd like to double check the full code

Here is the complete monotonic_stack.py:

"""
Pattern: Monotonic Stack
========================
When to use:
- "Next greater/smaller element" problems
- Need to look back at previous elements efficiently
- Finding spans or ranges in arrays
- Histogram problems
- Temperature / stock price patterns

Time: O(n) | Space: O(n)

Signal phrases: "next greater element", "next warmer day",
"largest rectangle", "stock span", "previous smaller"
"""


def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    Daily Temperatures (LeetCode 739)

    For each day, find how many days until a warmer temperature.
    Return 0 if no future day is warmer.

    Strategy: Maintain a stack of indices with decreasing temps.
    When a warmer day arrives, pop all cooler days and calculate
    the distance.
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # stores indices

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)

    return result


if __name__ == "__main__":
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
    # Expected: [1, 1, 4, 2, 1, 1, 0, 0]

Here is the complete runner.py:

import time

from two_pointers import max_area
from sliding_window import length_of_longest_substring
from hash_map import group_anagrams
from binary_search import search_rotated
from monotonic_stack import daily_temperatures


def normalize_groups(groups):
    """Sort group contents and group order for stable comparison."""
    return sorted([sorted(g) for g in groups])


def run_tests(name, func, test_cases, normalize=None):
    """Run test cases for a pattern and report results."""
    print(f"\n{'='*55}")
    print(f"  {name}")
    print(f"{'='*55}")
    all_passed = True

    for i, (args, expected) in enumerate(test_cases, 1):
        start = time.perf_counter()
        if isinstance(args, tuple):
            result = func(*args)
        else:
            result = func(args)
        elapsed = (time.perf_counter() - start) * 1000

        check_result = normalize(result) if normalize else result
        check_expected = normalize(expected) if normalize else expected
        passed = check_result == check_expected
        status = "PASS" if passed else "FAIL"
        print(f"  Test {i}: {status} ({elapsed:.4f}ms)")

        if not passed:
            print(f"         Expected: {expected}")
            print(f"         Got:      {result}")
            all_passed = False

    return all_passed


def main():
    print("\n" + "=" * 55)
    print("  INTERVIEW PATTERN TOOLKIT - Test Runner")
    print("=" * 55)

    results = []

    results.append(run_tests(
        "Two Pointers: Container With Most Water",
        max_area,
        [
            ([1, 8, 6, 2, 5, 4, 8, 3, 7], 49),
            ([1, 1], 1),
            ([4, 3, 2, 1, 4], 16),
        ]
    ))

    results.append(run_tests(
        "Sliding Window: Longest Substring Without Repeating",
        length_of_longest_substring,
        [
            ("abcabcbb", 3),
            ("bbbbb", 1),
            ("pwwkew", 3),
            ("", 0),
        ]
    ))

    results.append(run_tests(
        "Hash Map: Group Anagrams",
        group_anagrams,
        [
            (["eat", "tea", "tan", "ate", "nat", "bat"],
             [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]),
            ([""], [[""]]),
            (["a"], [["a"]]),
        ],
        normalize=normalize_groups
    ))

    results.append(run_tests(
        "Binary Search: Search in Rotated Sorted Array",
        search_rotated,
        [
            (([4, 5, 6, 7, 0, 1, 2], 0), 4),
            (([4, 5, 6, 7, 0, 1, 2], 3), -1),
            (([1], 0), -1),
            (([1], 1), 0),
        ]
    ))

    results.append(run_tests(
        "Monotonic Stack: Daily Temperatures",
        daily_temperatures,
        [
            ([73, 74, 75, 71, 69, 72, 76, 73], [1, 1, 4, 2, 1, 1, 0, 0]),
            ([30, 40, 50, 60], [1, 1, 1, 0]),
            ([30, 20, 10], [0, 0, 0]),
        ]
    ))

    passed = sum(results)
    total = len(results)
    print(f"\n{'='*55}")
    print(f"  Results: {passed}/{total} patterns passing")
    if passed == total:
        print("  All patterns implemented correctly!")
    print(f"{'='*55}\n")


if __name__ == "__main__":
    main()
Run the full test suite and verify all 5 patterns pass

This is the moment everything comes together. One command runs all five patterns through their test cases and reports results.

  • Run the full test suite by running this command:
python runner.py
  • You should see output for all five patterns with each test showing PASS and a timing in milliseconds.
  • At the bottom you should see Results: 5/5 patterns passing followed by All patterns implemented correctly!.

What should I see?

The runner prints a header for each pattern, then individual test results with execution times. All 15 tests (3 per pattern, except Sliding Window which has 4) should show PASS. The execution times confirm your solutions run in sub-millisecond time on small inputs.

Seeing an ImportError or ModuleNotFoundError?

  • Make sure you are running the command from inside the interview_toolkit folder where all six .py files live.
  • Check that your function names match exactly: max_area, length_of_longest_substring, group_anagrams, search_rotated, daily_temperatures.
  • Verify that each file name matches the import statement (e.g. two_pointers.py not two-pointers.py).

Help me fix an import error when running my test runner.

Why does timing matter in interview prep?

The runner reports execution time for each test so you can build intuition for what O(n) and O(log n) actually feel like on real inputs. As you extend the toolkit with larger test cases, you will see the timing differences between patterns become obvious.

Secret mission

Add BFS - Number of Islands

Your toolkit covers 5 patterns, but graph traversal questions make up another 10-15% of FAANG interviews. Extend your toolkit with a 6th pattern by implementing Number of Islands using Breadth-First Search.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs or cloud resources to worry about.

Decide whether to keep your project files for continued practice, or delete them if you're done.

Resources you used:

  • The interview_toolkit folder on your Desktop (contains all 6 pattern modules and the test runner).

Keep everything running

No action needed. Choose this if you're still actively building on your toolkit or want to add more patterns.

  • Your interview_toolkit folder stays on your Desktop, ready for you to extend with new patterns.
  • You can continue adding pattern modules (DFS, dynamic programming, tries) to the same folder.
  • Run python runner.py anytime to verify everything still passes.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your files will be waiting for you when you come back.

  • Close the VS Code window for the interview_toolkit folder.
  • Your files remain on your Desktop. Reopen the folder in VS Code when you're ready to continue.

Delete - I don't want to use this again

Remove all project files and start fresh.

  • Close the VS Code window for interview_toolkit.
  • Delete the project folder by running this command in your terminal:

macOS

rm -rf ~/Desktop/interview_toolkit

Windows

rmdir /s /q %USERPROFILE%\Desktop\interview_toolkit
  • Confirm the folder is gone by checking your Desktop.

Nice Work!

Nice Work!

Nice work! You've just built a complete Interview Pattern Toolkit covering the 5 highest-yield algorithm patterns tested in FAANG coding interviews.

You've learned how to:

  • Implement the Two Pointers, Sliding Window, Hash Map, Binary Search, and Monotonic Stack patterns to solve canonical interview problems in Python.
  • Build a test runner that validates all solutions and reports pass/fail with execution time.
  • Recognize pattern signal phrases from problem descriptions to identify which algorithm to apply within seconds.
  • Secret Mission: Added BFS (Number of Islands) to extend your toolkit into graph traversal.

Ready to quiz yourself?