Python Coding Challenges to Practice for Interviews

Python coding challenges in interviews are rarely about obscure tricks. Most come down to recognising a handful of patterns: use a dictionary or set to avoid a nested loop, slide a window instead of restarting, keep a running total instead of recomputing. Knowing the pattern is half the answer. The other half is showing that your faster solution is correct and explaining why it is faster.

This article does both for three classic challenges. Each is solved twice, by brute force and with the pattern. The two versions are checked against each other on 600 random inputs, then compared by the number of steps they take on the same input.

import random
from collections import Counter, deque

random.seed(7)
steps = Counter()                      # counts the basic operations each solution performs


# 1. Two sum: brute force over pairs vs one pass with a dictionary
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            steps["two_sum brute"] += 1
            if nums[i] + nums[j] == target:
                return i, j


def two_sum_hash(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        steps["two_sum hash"] += 1
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i


# 2. Longest substring without repeats: restart from each start vs sliding window
def longest_brute(s):
    best = 0
    for i in range(len(s)):
        chars = set()
        for j in range(i, len(s)):
            steps["longest brute"] += 1
            if s[j] in chars:
                break
            chars.add(s[j])
            best = max(best, j - i + 1)
    return best


def longest_window(s):
    last, start, best = {}, 0, 0
    for i, ch in enumerate(s):
        steps["longest window"] += 1
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best


# 3. Moving average over a stream: re-sum each window vs keep a running total
def moving_avg_resum(values, k):
    out = []
    for i in range(k - 1, len(values)):
        steps["moving avg re-sum"] += k
        out.append(sum(values[i - k + 1:i + 1]) / k)
    return out


def moving_avg_running(values, k):
    window, total, out = deque(), 0, []
    for v in values:
        steps["moving avg running"] += 1
        window.append(v)
        total += v
        if len(window) > k:
            total -= window.popleft()
        if len(window) == k:
            out.append(total / k)
    return out


# Check the fast versions agree with the slow ones on random inputs, then compare work at one size
for trial in range(200):
    nums = random.sample(range(-1000, 1000), 50)
    i, j = random.sample(range(50), 2)
    a, b = two_sum_brute(nums, nums[i] + nums[j]), two_sum_hash(nums, nums[i] + nums[j])
    assert nums[a[0]] + nums[a[1]] == nums[b[0]] + nums[b[1]]
    s = "".join(random.choice("abcdefgh") for _ in range(40))
    assert longest_brute(s) == longest_window(s)
    v = [random.randint(0, 100) for _ in range(60)]
    assert all(abs(x - y) < 1e-9 for x, y in zip(moving_avg_resum(v, 7), moving_avg_running(v, 7)))
print("C1 600 randomised checks passed: fast and slow solutions agree")

steps.clear()
n = 2000
nums = random.sample(range(-10**6, 10**6), n)
two_sum_brute(nums, nums[-1] + nums[-2]); two_sum_hash(nums, nums[-1] + nums[-2])
text = "".join(random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(n))
longest_brute(text); longest_window(text)
values = [random.random() for _ in range(n)]
moving_avg_resum(values, 50); moving_avg_running(values, 50)
print(f"\nC2 basic steps at n = {n} (worst-case pair placed at the end for two sum)")
for pair in (("two_sum brute", "two_sum hash"), ("longest brute", "longest window"), ("moving avg re-sum", "moving avg running")):
    slow, fast = steps[pair[0]], steps[pair[1]]
    print(f"   {pair[0]:<20}{slow:>10,} steps | {pair[1]:<20}{fast:>7,} steps | {slow / fast:,.0f}x fewer")

C1 600 randomised checks passed: fast and slow solutions agree

C2 basic steps at n = 2000 (worst-case pair placed at the end for two sum)
   two_sum brute        1,999,000 steps | two_sum hash          2,000 steps | 1,000x fewer
   longest brute           13,886 steps | longest window        2,000 steps | 7x fewer
   moving avg re-sum       97,550 steps | moving avg running    2,000 steps | 49x fewer

Challenge 1: two sum, and the dictionary pattern

Given a list of numbers and a target, find two positions whose values add up to the target. The brute force checks every pair: for 2,000 numbers with the answer at the end, that was 1,999,000 checks. The pattern stores each number in a dictionary as you go and asks whether the complement, target minus the current number, has been seen. That took 2,000 steps, a thousand times fewer.

It works because a dictionary membership test is O(1) on average, according to Python's own complexity notes, though O(n) in the worst case (Python Wiki: time complexity). Say that in the interview: average constant time, with the worst case worth acknowledging.

Recognise it when: you are searching for a partner, a duplicate or a previously seen value inside a loop.

Challenge 2: longest substring without repeating characters, and the sliding window

Find the length of the longest run of characters with no repeats. The brute force starts again from every position. The sliding window keeps a start pointer and the last position of each character, moving the start forward only when a repeat appears, so each character is visited once.

Here is the surprising result: the brute force took only 13,886 steps against 2,000, seven times more, not the quadratic blow-up you might expect. The text used only the 26 lowercase letters, so no window can be longer than 26 characters, and each restart stops quickly. With a large alphabet, such as arbitrary Unicode or IDs, the brute force would get far worse. This is exactly the kind of point that impresses interviewers: complexity depends on the input, and you should say which inputs make a solution slow.

Recognise it when: the question asks for the longest or shortest contiguous run satisfying a condition.

Challenge 3: moving average, and the running total

Compute the average of each window of 50 values over a stream. Re-summing every window cost 97,550 additions; keeping a running total, adding the new value and subtracting the one leaving the window, cost 2,000 steps, 49 times fewer. The window itself is a deque, which Python's documentation describes as supporting appends and pops from either end in approximately O(1) time (Python docs: collections). Popping from the front of a list, by contrast, moves every other element.

Recognise it when: you recompute an aggregate over overlapping ranges.

Prove correctness the way the code does

The check at the top of the output is a habit worth bringing into interviews and real work. Write the obvious brute force first, then the fast version, and compare them on many random inputs. If they ever disagree, the fast version has a bug. In an interview you can describe this even if you cannot run it: "I'd test the optimised version against the brute force on random inputs, plus edge cases such as an empty list and duplicates."

Talking through trade-offs

Faster is not always better, and interviewers often ask what you gave up. The dictionary in two sum uses extra memory proportional to the input; on a device with tight memory and a sorted list, two pointers might be the better choice. The sliding window is harder to read than the brute force, so on tiny inputs in production code the simple version can be the right one. Saying "this uses O(n) extra space; if memory mattered I would sort and use two pointers" shows judgement rather than memorised answers.

Other patterns worth practising

• Two pointers on sorted data: pairs with a target sum, merging sorted lists.
• Sorting first: merging overlapping intervals, grouping anagrams.
• Counting with Counter: most frequent items, comparing frequencies.
• Stacks: matching brackets, next greater element.
• Breadth-first search: shortest path in a grid or graph.
• Heaps: the k largest items, merging k sorted streams.

How to practise

1. Solve the brute force first, out loud, then improve it. Interviewers want to see the path, not only the destination.
2. Name the pattern and its complexity in time and space.
3. Test edge cases: empty input, one element, duplicates, negatives, very large input.
4. Time-box each attempt to 25 minutes, then study the pattern if you are stuck, and retry the problem a few days later without notes.

For the language questions that come up in the same round, mutability, generators and decorators among them, see Python interview questions.

Python fundamentals and problem-solving practice are part of the Python Programming course.

Sources

• TimeComplexity (Python Wiki) — Python Software Foundation
• collections: Container datatypes (Python documentation) — Python Software Foundation