Problem Solving: Intermediate

Spotify's playlist deduplication system uses sliding window and frequency counting patterns to scan billions of playlist entries for duplicate songs in linear time, cutting what would have been hours of processing into minutes across 4 billion user-created playlists. The sliding window technique avoids re-scanning already-processed data on every step, achieving O(n) time where a naive approach would take O(n²). Two-pointer and frequency counting are the most common patterns in technical interviews at companies like Stripe, Airbnb, and Shopify because they appear in real production systems every day. The patterns you learn in this lesson will show up repeatedly in both interviews and on the job.

Common Code Patterns

Daily Life
Interviews

Apply transform, reduce, and two-pass

Experienced programmers don't solve each problem from scratch. They recognize patterns and apply proven approaches. Here are essential patterns you'll use constantly.

The Transform Pattern

Convert each element into a new form. Use when you need to change every item in a collection.
1names = ["alice", "bob", "charlie"]
2upper_names = []
3for name in names:
4 upper_names.append(name.upper())
5print(upper_names)
>>>Output
['ALICE', 'BOB', 'CHARLIE']

Python provides a concise way to do this with [x for x in ...] list comprehensions:

1names = ["alice", "bob", "charlie"]
2upper_names = [name.upper() for name in names]
3print(upper_names)
>>>Output
['ALICE', 'BOB', 'CHARLIE']

The Reduce Pattern

Combine all elements into a single value. Use for totals, products, finding min/max, or building composite results.
1numbers = [3, 1, 4, 1, 5, 9, 2, 6]
2
3# Find minimum
4minimum = numbers[0]
5for num in numbers:
6 if num < minimum:
7 minimum = num
8
9# Find product
10product = 1
11for num in numbers:
12 product = product * num
13
14print(f"Min: {minimum}, Product: {product}")
>>>Output
Min: 1, Product: 6480

The Two-Pass Pattern

Sometimes you need information from the entire collection before processing. Make one pass to gather data, another to use it.
1scores = [85, 90, 78, 92, 88]
2
3# Pass 1: Calculate average
4total = sum(scores)
5average = total / len(scores)
6
7# Pass 2: Find above-average scores
8above_average = []
9for score in scores:
10 if score > average:
11 above_average.append(score)
12
13print(f"Average: {average}")
14print(f"Above average: {above_average}")
>>>Output
Average: 86.6
Above average: [90, 92, 88]
TIP
Don't try to be clever by doing everything in one pass. Two simple passes are often clearer and just as fast as one complex pass.
Fill in the Blank

> A class has test scores [85, 90, 78, 92, 88] and the teacher wants to see how each student compares to the average. Pick an expression to transform each score relative to the mean.

scores = [85, 90, 78, 92, 88]
average = sum(scores) / len(scores)
result = [ for s in scores]
print(result)
The transform, reduce, and two-pass patterns are building blocks that combine naturally. Real-world solutions often chain them: reduce the data to compute an aggregate, then transform every element relative to that aggregate.
List comprehensions express the transform pattern concisely. When the expression inside the comprehension grows complex, consider extracting it into a named function for readability.
TIP
When you see a loop that builds a new list from an existing one, that is the transform pattern. When a loop reduces a list to a single number, that is the reduce pattern. Naming the pattern helps you choose the right tool.

Edge Case Handling

Daily Life
Interviews

Guard every function against bad input

Edge cases are inputs at the boundaries of what's valid. They're where bugs hide and where robust code proves its worth. Professional developers think about edge cases BEFORE writing code.
Empty inputs
Empty inputs
Empty lists, empty strings, None, and zero values
Single element
Single element
A list with one item or a one-character string
Boundary values
Boundary values
First, last, maximum, and minimum values in a range
Duplicates
Duplicates
Identical values like [1, 1, 1] or "aaa" in the input
Negative values
Negative values
Negative numbers and negative indices that flip logic
Type edge cases
Type edge cases
Very large numbers, special characters, mixed types

Defensive Programming

Handle edge cases explicitly at the start of your functions. This makes your intentions clear and prevents crashes.
1def average(numbers):
2 # Edge case: empty list
3 if not numbers:
4 return 0
5
6 # Edge case: single element
7 if len(numbers) == 1:
8 return numbers[0]
9
10 # Normal case
11 return sum(numbers) / len(numbers)
12
13print(average([]))
14print(average([42]))
15print(average([10, 20, 30]))
>>>Output
0
42
20.0

Common Pitfalls

These edge cases cause the most bugs:
✓Do
  • Check for empty input first
  • Validate indices before access
  • Use >= instead of > for bounds
  • Handle None explicitly
✗Don't
  • Divide without checking for zero
  • Access list[-1] on empty lists
  • Confuse < with <= in ranges
  • Treat empty string as valid data
1def safe_divide(a, b):
2 if b == 0:
3 return None
4 return a / b
5
6def safe_first(items):
7 if not items:
8 return None
9 return items[0]
10
11print(safe_divide(10, 0))
12print(safe_first([]))
>>>Output
None
None
Debug Challenge

> This safe_get function uses > instead of >= to guard against out-of-range indices. When the index equals the list length, the check passes but the access fails.

IndexError: list index out of range when index equals len(items)

Off-by-one errors at boundaries are among the most common bugs in all of programming. Zero-based indexing means a list of n items has valid indices from 0 to n-1, so the guard condition must use >= len rather than > len.

Defensive programming at function boundaries -- validating inputs before using them -- prevents a whole class of crashes. Guard clauses that return early for invalid inputs keep the main logic clean and readable.
TIP
When guarding against index errors, always work through the boundary case explicitly. For a list of 3 items: what happens at index 0? Index 2? Index 3? This mental check reveals whether you need > or >=.

Time Complexity Basics

Daily Life
Interviews

Predict runtime with Big O notation

Time complexity describes how runtime grows as input size increases. We use Big O notation to classify algorithms by their worst-case scaling behavior.

O(1) - Constant Time

Operations that take O(1) time run in the same time regardless of input size. Direct access, simple arithmetic, and dictionary lookups are all constant-time.

1# O(1) - constant time
2first = items[0]
3last = items[-1]
4length = len(items)
5value = my_dict["key"]

O(n) - Linear Time

O(n) time grows proportionally with input size. Scanning through a list once with a simple loop is a common O(n) operation.

1# O(n) - visits each element once
2total = 0
3for num in numbers:
4 total += num
5
6# Also O(n)
7found = target in items

O(n²) - Quadratic Time

O(n²) time grows with the square of input size. Nested loops over the same data are a warning sign of quadratic behavior.

1# O(n²) - every pair
2for i in range(len(items)):
3 for j in range(len(items)):
4 pass

Recognizing these three complexity classes (O(1), O(n), and O(n²)) helps you estimate how your code will perform before you even run it.

O(1)O(n)O(n²)
O(1)
Constant time
Same speed at any scale
O(n)
Linear time
2x data means 2x slower
O(n²)
Quadratic time
2x data means 4x slower
The difference between these classes becomes dramatic as input size grows.
•n = 1,000
  • O(1): 1 operation
  • O(n): 1,000 operations
  • O(n²): 1,000,000 operations
•n = 1,000,000
  • O(1): 1 operation
  • O(n): 1,000,000 operations
  • O(n²): 1 trillion operations!
These numbers have real consequences when you run code on large datasets.
Fill in the Blank

> You need to find pairs in [3, 1, 4, 1, 5] that sum to 6. Pick the inner logic for the loop and see whether each approach uses nested iteration or a smarter lookup.

items = [3, 1, 4, 1, 5]
target = 6
for i in range(len(items)):
    
        print(f"Found pair")
print("Search complete")

Recognizing O(n²) before you run your code comes from spotting nested loops over the same data. When you see two loops both ranging over the input, ask whether there is a data structure that can eliminate the inner loop.

A set converts the O(n) inner "in" check to O(1), turning the overall algorithm from O(n²) to O(n). This is one of the most common interview optimizations and one of the most impactful in production code.

TIP
If your algorithm checks each element against every other element, its complexity is O(n²). If it checks each element against a hash structure, it is O(n). Adding a set is often the simplest path from one to the other.

Space Complexity Basics

Daily Life
Interviews

Spot and fix wasted memory usage

Space complexity measures how much memory your algorithm uses relative to input size. Sometimes you can trade space for time, using more memory to run faster.

O(1) Space

Uses a fixed amount of memory regardless of input size. Only a few variables, no new collections.
1def find_max(numbers):
2 maximum = numbers[0]
3 for num in numbers:
4 if num > maximum:
5 maximum = num
6 return maximum
7
8print(find_max([3, 1, 4, 1, 5, 9, 2, 6]))
>>>Output
9

O(n) Space

Memory grows with input size. Creating new lists, building results.
1def get_evens(numbers):
2 # Creates new list - O(n) space
3 evens = []
4 for num in numbers:
5 if num % 2 == 0:
6 evens.append(num)
7 return evens
8
9print(get_evens([1, 2, 3, 4, 5, 6, 7, 8]))
>>>Output
[2, 4, 6, 8]
TIP
When memory is tight, consider in-place algorithms that modify the original data instead of creating copies. But be careful: modifying input can cause bugs if that data is used elsewhere.
Debug Challenge

> This function builds an entire list of positive numbers just to check if any exist. It wastes O(n) memory when a simple early return would suffice.

Code works but wastes memory by building a list just to check existence

Allocating memory proportional to input size when only a boolean answer is needed is a common beginner mistake. Early return reduces both time complexity (stops at the first positive) and space complexity (no extra list).

Space and time complexity trade-offs are real design decisions. Sometimes using O(n) extra space (like a hash map) halves the time complexity. Other times, as shown here, using O(1) space also improves time by enabling early termination.

TIP
Before allocating a new collection, ask: do I actually need to store everything, or do I just need to know something about the data? Existence checks, count checks, and "any/all" checks rarely need to materialize a full list.

Choosing Data Structures

Daily Life
Interviews

Pick list, set, or dict on sight

The right data structure can make a problem trivial. The wrong one can make it impossibly slow. Here's how to choose.

List vs Set vs Dictionary

Each data structure excels in different scenarios. Choosing correctly often determines whether your solution is fast or slow.
Use a List when order matters
Use a List when order matters
Index access, duplicates OK, sequential iteration
Use a Set for fast membership
Use a Set for fast membership
Unique values, O(1) "in" checks, union and intersection
Use a Dict for key-value lookup
Use a Dict for key-value lookup
Counting, grouping, fast access and insert by key
When you are unsure which structure fits, think about what your code does most often. The dominant operation should drive your choice.
Quick Data Structure Decision Guide
  • Frequent "is X in collection?" checks: use a set for O(1) membership
  • Need to count occurrences or group by key: use a dict
  • Order matters and you access by position: use a list
  • Need both fast lookup and ordering: build a dict and keep a sorted list of keys

Performance Comparison

The difference between O(1) and O(n) lookup is dramatic:

1# Checking membership in a list: O(n)
2numbers_list = list(range(100000))
3found = 99999 in numbers_list
4
5# Checking membership in a set: O(1)
6numbers_set = set(range(100000))
7found = 99999 in numbers_set
8
9print("Both find it, but set is ~100,000x faster!")
>>>Output
Both find it, but set is ~100,000x faster!

When you see if x in collection inside a loop, ask yourself: should this be a set?

01
Identify operations
What does your code do most: search, insert, or iterate?
02
Match to structure
Lists for order, sets for membership, dicts for lookup
03
Profile if unsure
Measure actual performance before optimizing blindly
Fill in the Blank

> A function checks whether a list [1, 2, 3, 2] contains any duplicates. Pick the data structure and method that give O(1) membership testing for the fastest solution.

def has_duplicates(items):
    
    for item in items:
        if item in seen:
            return True
        seen.(item)
    return False

print(has_duplicates([1, 2, 3, 2]))

Choosing the right data structure at the start is one of the highest-leverage decisions in software development. A set here reduces an O(n²) algorithm to O(n) with a single line change.

The decision framework is straightforward: if your algorithm's dominant operation is checking membership, use a set. If it's counting or grouping, use a dict. If it's ordered access by position, use a list.

TIP
When you see "if item in some_list" inside a loop, that is often a performance red flag. Converting the list to a set before the loop frequently eliminates the bottleneck.
Systematic problem-solving techniques help you tackle increasingly complex challenges with confidence. Put these approaches to the test with hands-on challenges in the Python Builder.
❯❯❯PUTTING IT ALL TOGETHER

> You are a data engineer at a startup profiling a slow Python transformation script that times out on production datasets. You must select better algorithms and data structures to bring runtime within the performance budget.

Common code patterns like sliding window and two-pointer replace nested loops, reducing time complexity from O(n²) to O(n) for deduplication passes.
Edge case handling ensures the optimized script produces correct results on empty partitions and single-row inputs before scaling to full production data.
Time complexity intuition reveals that the bottleneck is a linear scan inside a loop, making it O(n²) and the primary target for algorithmic replacement.
Choosing data structures based on most frequent operation means switching from a list to a set for membership testing cuts lookup time from O(n) to O(1).
KEY TAKEAWAYS
Master common patterns: transform, filter, reduce, two-pass
Always handle edge cases: empty, single, boundary, None
O(1) is constant, O(n) is linear, O(n²) is quadratic
Nested loops over the same data often means O(n²)
Use set for fast membership testing, dict for fast lookup
Choose data structures based on your most frequent operation

Write code that scales

Category
Python
Difficulty
intermediate
Duration
21 minutes
Challenges
0 hands-on challenges

Topics covered: Common Code Patterns, Edge Case Handling, Time Complexity Basics, Space Complexity Basics, Choosing Data Structures

Lesson Sections

  1. Common Code Patterns

    Experienced programmers don't solve each problem from scratch. They recognize patterns and apply proven approaches. Here are essential patterns you'll use constantly. The Transform Pattern Convert each element into a new form. Use when you need to change every item in a collection. The Reduce Pattern Combine all elements into a single value. Use for totals, products, finding min/max, or building composite results. The Two-Pass Pattern Sometimes you need information from the entire collection bef

  2. Edge Case Handling

    Edge cases are inputs at the boundaries of what's valid. They're where bugs hide and where robust code proves its worth. Professional developers think about edge cases BEFORE writing code. Defensive Programming Handle edge cases explicitly at the start of your functions. This makes your intentions clear and prevents crashes. Common Pitfalls These edge cases cause the most bugs: Defensive programming at function boundaries -- validating inputs before using them -- prevents a whole class of crashe

  3. Time Complexity Basics

    Time complexity describes how runtime grows as input size increases. We use Big O notation to classify algorithms by their worst-case scaling behavior. O(1) - Constant Time O(n) - Linear Time O(n²) - Quadratic Time The difference between these classes becomes dramatic as input size grows. These numbers have real consequences when you run code on large datasets.

  4. Space Complexity Basics

    Space complexity measures how much memory your algorithm uses relative to input size. Sometimes you can trade space for time, using more memory to run faster. O(1) Space Uses a fixed amount of memory regardless of input size. Only a few variables, no new collections. O(n) Space Memory grows with input size. Creating new lists, building results. Allocating memory proportional to input size when only a boolean answer is needed is a common beginner mistake. Early return reduces both time complexity

  5. Choosing Data Structures

    The right data structure can make a problem trivial. The wrong one can make it impossibly slow. Here's how to choose. List vs Set vs Dictionary Each data structure excels in different scenarios. Choosing correctly often determines whether your solution is fast or slow. When you are unsure which structure fits, think about what your code does most often. The dominant operation should drive your choice. Performance Comparison Systematic problem-solving techniques help you tackle increasingly compl