Skip to content

Interview PrepCoding · Core

Python Coding Classics ​

These are the small exercises that test whether you know Python's standard library. The full algorithm patterns are in the Part 4 NeetCode pages of the book; here the focus is the idiomatic Python answer.

65. Find two numbers in a list that add up to a target. ​

The short answer

Walk the list once with a dict from value to index. For each number, check whether target - number has already been seen; if so, you have the pair. Each lookup is about constant time, so the whole solution is O(n) time and O(n) extra space, instead of O(n²) for checking every pair.

python
def two_sum(nums: list[int], target: int) -> list[int] | None:
    seen: dict[int, int] = {}
    for i, n in enumerate(nums):              # (1)
        if target - n in seen:                # (2)
            return [seen[target - n], i]
        seen[n] = i                           # (3)
    return None

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2]
  1. enumerate gives index and value together.
  2. Look for the partner first, so a number is never paired with itself.
  3. Then remember this number's index.

66. Check whether a string is a palindrome, ignoring case and punctuation. ​

The short answer

Keep only letters and digits, lower-cased, then compare the result with its reverse, using the slice [::-1]. That is O(n) time and O(n) space. A two-pointer version, moving inward from both ends and skipping non-alphanumeric characters, uses O(1) extra space if the interviewer asks.

python
def is_palindrome(s: str) -> bool:
    clean = [c.lower() for c in s if c.isalnum()]
    return clean == clean[::-1]

print(is_palindrome("A man, a plan, a canal: Panama"))   # True
print(is_palindrome("race a car"))                       # False

67. Count word frequencies and find the most common. ​

The short answer

Use collections.Counter: it counts any iterable in one call, and most_common(k) returns the top k pairs. It is a dict subclass, so missing keys count as zero, and counters can be added and subtracted. Writing the counting loop by hand with a dict and get(word, 0) + 1 is the same O(n) algorithm, but Counter shows you know the standard library.

python
from collections import Counter

words = "the cart the order the cart".split()
print(Counter(words).most_common(2))      # [('the', 3), ('cart', 2)]

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    return [n for n, _ in Counter(nums).most_common(k)]

print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))   # [1, 2]

Complexity: counting is O(n). most_common(k) uses a heap, O(n log k), when k is given.

68. Group words that are anagrams of each other. ​

The short answer

Anagrams have the same letters, so they share a key: the sorted letters, "aet" for "eat", "tea" and "ate". Put each word into a defaultdict(list) under its key; the dict's values are the groups. Sorting each word of length m costs O(m log m), so the total is O(n · m log m). A 26-count tuple of letter frequencies as the key gives O(n · m).

python
from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: defaultdict[str, list[str]] = defaultdict(list)    # (1)
    for w in words:
        groups["".join(sorted(w))].append(w)                   # (2)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
  1. A missing key gets an empty list automatically, so there is no "if key not in groups" step.
  2. The sorted letters, joined back into a string, are hashable and identical for every anagram.

69. Flatten an arbitrarily nested list. ​

The short answer

Recurse: for each item, if it is a list or tuple, flatten it and extend the result; otherwise append it. A generator with yield from does the same lazily (yield from). Mention the limits: very deep nesting can hit Python's recursion limit, about 1,000, in which case use an explicit stack; and strings are iterable, so do not treat them as nested lists.

python
def flatten(items: list) -> list:
    out = []
    for x in items:
        if isinstance(x, (list, tuple)):     # (1)
            out.extend(flatten(x))
        else:
            out.append(x)
    return out

print(flatten([1, [2, (3, [4])], 5]))       # [1, 2, 3, 4, 5]
  1. Check for the container types you mean, not "any iterable", or a string like "abc" would be split into letters.

70. Implement an LRU cache. ​

The short answer

Use collections.OrderedDict, which remembers insertion order and can move a key to the end in O(1). On get, move the key to the end, meaning most recently used. On put, insert or update and move to the end; if over capacity, remove the first item, the least recently used, with popitem(last=False). Both operations are O(1). For caching a function's results, functools.lru_cache already does this.

python
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data: OrderedDict[str, int] = OrderedDict()

    def get(self, key: str) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)                # (1)
        return self.data[key]

    def put(self, key: str, value: int) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)         # (2)

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2)
cache.get("a")                                    # "a" is now most recent
cache.put("c", 3)                                 # evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c"))   # -1 1 3
  1. Mark as recently used.
  2. Evict from the front, the oldest. The JavaScript version uses a Map the same way (the JS LRU cache).

71. Merge sorted lists, and find the largest k items. ​

The short answer

Use heapq. heapq.merge(*sorted_lists) lazily merges already-sorted inputs in O(n log k) for k lists, without loading everything. heapq.nlargest(k, items) and nsmallest find the top k in O(n log k), better than sorting everything, O(n log n), when k is small. heapq implements a min-heap on a plain list; for a max-heap, push negated values.

python
import heapq

print(list(heapq.merge([1, 4, 9], [2, 3, 10])))   # [1, 2, 3, 4, 9, 10]
print(heapq.nlargest(2, [5, 1, 9, 3]))             # [9, 5]

tasks: list[tuple[int, str]] = []
heapq.heappush(tasks, (2, "send email"))
heapq.heappush(tasks, (1, "charge card"))
print(heapq.heappop(tasks))                        # (1, 'charge card'), lowest priority number first

72. Check whether brackets in a string are balanced. ​

The short answer

Use a stack, a plain list. Push every opening bracket. For a closing bracket, the stack must be non-empty and its top must be the matching opener; pop it. At the end the stack must be empty. That is O(n) time and O(n) space, and it shows you know when a list works as a stack with append and pop.

python
def valid_brackets(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:   # (1)
                return False
    return not stack                                     # (2)

print(valid_brackets("{[()]}"), valid_brackets("([)]"), valid_brackets("(("))   # True False False
  1. A closer with nothing open, or the wrong opener on top, fails immediately.
  2. Leftover openers mean something was never closed.

73. Compute a moving average over a stream of values. ​

The short answer

Keep a collections.deque of the last window values and a running total. For each new value, append it and add it to the total; if the deque is longer than the window, pop the oldest from the left and subtract it. Each step is O(1), instead of re-summing the window each time. deque is the right structure because removing from the left of a list is O(n) but from a deque is O(1).

python
from collections import deque

def moving_average(values: list[float], window: int) -> list[float]:
    recent: deque[float] = deque()
    total, out = 0.0, []
    for v in values:
        recent.append(v); total += v
        if len(recent) > window:
            total -= recent.popleft()            # (1)
        if len(recent) == window:
            out.append(total / window)
    return out

print(moving_average([10, 20, 30, 40, 50], 3))   # [20.0, 30.0, 40.0]
  1. O(1) removal from the left, the reason to use a deque.

74. Write a decorator that rate-limits calls to a function. ​

The short answer

A decorator factory takes the allowed rate, works out the minimum interval between calls, and keeps the time of the last call in the closure. Before each call, if not enough time has passed, it sleeps for the remainder. Use time.monotonic(), which never jumps backwards when the system clock changes. For async code, use asyncio.sleep and an asyncio.Lock; for many processes, a shared limiter in Redis (distributed rate limiting).

python
import functools, time

def rate_limited(calls_per_second: float):
    interval = 1 / calls_per_second
    def decorator(fn):
        last_call = 0.0
        @functools.wraps(fn)
        def wrapper(*args, **kwargs):
            nonlocal last_call                          # (1)
            wait = last_call + interval - time.monotonic()
            if wait > 0:
                time.sleep(wait)                        # (2)
            last_call = time.monotonic()
            return fn(*args, **kwargs)
        return wrapper
    return decorator

@rate_limited(10)
def call_partner_api():
    ...

start = time.perf_counter()
for _ in range(5):
    call_partner_api()
print(round(time.perf_counter() - start, 1))   # 0.4: the first call is immediate, then 4 × 0.1 s
  1. nonlocal lets the wrapper update the time of the last call kept in the closure.
  2. Sleep only for what is left of the interval. This version is not thread-safe; add a threading.Lock around the check and update for use from several threads.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Interview Prep
Python
Foundations
Functions
Iteration
Objects
Internals
Errors and packaging
Concurrency
Modern Python
Coding
Other topics
Nothing picked yet