Python Coding Interview Questions and Patterns

Coding rounds look like an endless supply of puzzles, but most problems are one of a few patterns wearing a different story. Recognising the pattern is most of the work: once you see that a question is really a sliding window or a monotonic stack, the code follows. These Python coding interview patterns are each solved on real data rather than toy arrays, and each fast solution is checked against a slow, obviously correct one, which is also what you should do in an interview when time allows.

The data is two years of rentals from Capital Bikeshare in Washington, D.C.: 731 daily totals and 17,379 hourly rows with a weather code from 1, clear, to 4, heavy rain or snow (UCI: Bike Sharing). Only the standard library is used.

import bisect
import csv
import heapq
from collections import Counter, defaultdict
from datetime import date, datetime, timedelta
from itertools import accumulate

with open("day.csv") as f:                                   # UCI Bike Sharing, daily rentals 2011-2012
    days = [(r["dteday"], int(r["cnt"])) for r in csv.DictReader(f)]
with open("hour.csv") as f:
    hours = [(r["dteday"], int(r["hr"]), int(r["weathersit"]), int(r["cnt"])) for r in csv.DictReader(f)]
counts = [c for _, c in days]
print(f"{len(days)} days, {len(hours)} hours")

print("\n1 Hash map: rentals by hour of day, one pass")
by_hour = defaultdict(int)
for _, hr, _, c in hours:
    by_hour[hr] += c
print("   busiest hours:", Counter(by_hour).most_common(3))

print("\n2 Sliding window: busiest 7 days in a row")
window = best = sum(counts[:7])
best_end = 6
for i in range(7, len(counts)):
    window += counts[i] - counts[i - 7]                       # add the new day, drop the oldest: O(n)
    if window > best:
        best, best_end = window, i
brute = max(sum(counts[i:i + 7]) for i in range(len(counts) - 6))   # O(n * k), to check
print(f"   {days[best_end - 6][0]} to {days[best_end][0]}: {best:,} rentals | matches brute force: {best == brute}")

print("\n3 Two pointers: pairs of days that together exceed 15,000 rentals")
s = sorted(counts)
lo, hi, pairs = 0, len(s) - 1, 0
while lo < hi:
    if s[lo] + s[hi] > 15000:
        pairs += hi - lo                                      # every value from lo to hi-1 pairs with s[hi]
        hi -= 1
    else:
        lo += 1
brute = sum(1 for i in range(len(counts)) for j in range(i + 1, len(counts)) if counts[i] + counts[j] > 15000)
print(f"   {pairs:,} pairs | matches brute force: {pairs == brute}")

print("\n4 Heap: the 3 busiest hours without sorting all of them")
top = heapq.nlargest(3, hours, key=lambda h: h[3])
print("  ", [(d, hr, c) for d, hr, _, c in top], "| same as sorting:", top == sorted(hours, key=lambda h: -h[3])[:3])

print("\n5 Monotonic stack: days until a busier day")
wait, stack = [0] * len(counts), []
for i, c in enumerate(counts):
    while stack and counts[stack[-1]] < c:
        j = stack.pop()
        wait[j] = i - j
    stack.append(i)
longest = max(range(len(counts)), key=lambda i: wait[i])
print(f"   longest wait: {wait[longest]} days after {days[longest][0]} ({counts[longest]:,} rentals)")
print(f"   days never beaten afterwards: {len(stack)}")

print("\n6 Binary search: the day cumulative rentals passed 1 million")
running = list(accumulate(counts))
i = bisect.bisect_left(running, 1_000_000)
print(f"   {days[i][0]} (running total {running[i]:,})")

print("\n7 Merging intervals: longest spell of bad weather (code 3 or 4)")
first = date.fromisoformat(hours[0][0])
to_hour = lambda d, hr: (date.fromisoformat(d) - first).days * 24 + hr
bad = sorted((to_hour(d, hr), to_hour(d, hr) + 1) for d, hr, w, _ in hours if w >= 3)   # [start, end) per bad hour
merged = [list(bad[0])]
for start, end in bad[1:]:
    if start <= merged[-1][1]:                                # overlaps or touches the previous interval
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])
start, end = max(merged, key=lambda iv: iv[1] - iv[0])
when = lambda h: f"{datetime(first.year, first.month, first.day) + timedelta(hours=h):%Y-%m-%d %H:00}"
print(f"   {len(bad)} bad hours merged into {len(merged)} spells; longest {end - start} hours, {when(start)} to {when(end)}")

731 days, 17379 hours

1 Hash map: rentals by hour of day, one pass
   busiest hours: [(17, 336860), (18, 309772), (8, 261001)]

2 Sliding window: busiest 7 days in a row
   2012-09-09 to 2012-09-15: 55,916 rentals | matches brute force: True

3 Two pointers: pairs of days that together exceed 15,000 rentals
   2,641 pairs | matches brute force: True

4 Heap: the 3 busiest hours without sorting all of them
   [('2012-09-12', 18, 977), ('2012-09-20', 17, 976), ('2012-09-11', 17, 970)] | same as sorting: True

5 Monotonic stack: days until a busier day
   longest wait: 254 days after 2011-07-04 (6,043 rentals)
   days never beaten afterwards: 15

6 Binary search: the day cumulative rentals passed 1 million
   2011-10-17 (running total 1,002,452)

7 Merging intervals: longest spell of bad weather (code 3 or 4)
   1422 bad hours merged into 502 spells; longest 23 hours, 2011-10-28 20:00 to 2011-10-29 19:00

1. Hash map: count or group in one pass

Recognise it when the question says "how many", "group by", "first duplicate" or "pair that sums to". A dictionary lookup costs O(1) on average, against O(n) for searching a list (Python Wiki: time complexity), so one pass over the data replaces a nested loop. Summing 17,379 hours by hour of day showed the commuter pattern: 17:00 and 18:00 busiest, then 08:00. defaultdict(int) avoids checking whether a key exists, and Counter.most_common sorts the result.

2. Sliding window: best run of k consecutive items

Recognise it when the question asks for the best, longest or shortest contiguous stretch. Instead of re-adding seven days for every start position, add the day entering the window and subtract the day leaving it: O(n) instead of O(n·k). The busiest week was 9 to 15 September 2012, with 55,916 rentals, and the brute-force answer agreed.

3. Two pointers on sorted data

Recognise it when you need pairs meeting a condition on sorted values. Sort once, start one pointer at each end, and move the pointer that can only make things better. When the smallest and largest values already exceed the target, every value between them does too, so the count jumps by hi - lo in one step. That is how 2,641 qualifying pairs of days were counted without checking all of the roughly 267,000 pairs, and the brute-force count matched. Sorting makes the whole thing O(n log n).

4. Heap: top k without sorting everything

Recognise it when you need the k largest or smallest items and k is much smaller than n. heapq.nlargest(3, ...) keeps a small heap while scanning, roughly O(n log k). The Python documentation adds the practical rule: these functions suit small k; for large k, sorted() is faster, and for k of 1, max() (Python: heapq). The three busiest hours were all weekday evenings in September 2012, and sorting everything gave the same three.

5. Monotonic stack: next greater element

Recognise it when each item needs "the next item that is bigger" (or smaller): the classic "days until a warmer temperature". Keep a stack of indices whose answer is not known yet; each new value pops every smaller value off the stack and settles its answer. Every index is pushed and popped once, so it is O(n). Applied to daily rentals, 4 July 2011, with 6,043 rentals, waited 254 days for a busier day. Fifteen days were never beaten later in the data, and they are what remains on the stack at the end.

6. Binary search on a sorted or cumulative list

Recognise it when the data is sorted, or can be made monotonic, and you need the first position meeting a condition. A running total only ever rises, so bisect_left finds the day it first reached one million by repeated halving instead of a scan (Python: bisect): 17 October 2011, with 1,002,452 rentals so far. O(log n) per question matters when you have to answer many such questions against the same list.

7. Merging intervals

Recognise it when the input is ranges that can overlap or touch: bookings, outages, sessions. Sort by start, then extend the last merged interval while the next one starts before it ends. Each bad-weather hour became a one-hour interval; 1,422 such hours merged into 502 spells, the longest lasting 23 hours, from 20:00 on 28 October 2011 to 19:00 on 29 October.

A trap to mention: the first draft of this example grouped consecutive rows instead of consecutive hours. The hourly file has gaps, so two adjacent rows are not always adjacent hours. Converting each row to an absolute hour number before merging fixed it. Interviewers like candidates who question whether "next row" really means "next time step".

How to use these patterns in the room

1. Restate the problem and say which pattern it resembles.
2. Write the brute-force version first if it is short; it is your correctness check.
3. State the complexity of both versions.
4. Test the edges: empty input, one element, ties, values exactly at the threshold.
5. Run both on the same input, as each pattern above does, before calling it done.

For data-manipulation tasks rather than algorithms, see Python interview questions for data roles. The full topic list is in Python interview questions: top 50 with answers, the containers behind these patterns in Python data structures, and array-based questions in NumPy interview questions.

Python fundamentals and data structures are taught in the Python Programming course.

Sources

• TimeComplexity (Python Wiki) — Python Software Foundation
• heapq: Heap queue algorithm (Python documentation) — Python Software Foundation
• bisect: Array bisection algorithm (Python documentation) — Python Software Foundation
• Bike Sharing dataset (UCI Machine Learning Repository) — UCI Machine Learning Repository