Data structures & algorithms

list.append: amortized O(1), due to the list’s over-allocation growth strategy. list.insert(0, x): genuinely O(n) — every single existing element has to shift over by one position to make room at the front. x in list (membership test): O(n), a genuine linear scan through the whole list. x in dict/x in set: average O(1), thanks to hashing. dict insertion: average O(1), amortized (with an occasional O(n) resize, mirroring the same growth strategy as lists). Slicing (lst[a:b]): O(k), where k is the resulting slice’s length — this genuinely creates a brand-new list, not a lightweight view into the original. The insert(0, ...)/linear-scan in behaviors on plain lists are the two most common real-world performance bugs stemming from people not fully internalizing this — for instance, using a plain list as though it were a genuine FIFO queue via pop(0)/insert(0, x), instead of reaching for collections.deque.

deque provides genuine O(1) append and pop performance from both ends of the sequence (implemented internally as a doubly-linked structure of fixed-size blocks), whereas list.pop(0)/list.insert(0, x) are both O(n) operations. The genuine deciding factor for choosing deque: needing efficient operations specifically at the left/front end of a sequence — a true FIFO queue, a sliding window over a data stream, or a bounded “keep only the last N items” buffer (conveniently supported directly via deque(maxlen=N)) — a plain list handles all of these cases poorly once the data genuinely scales up in size.

There’s a genuine, real behavioral difference here, not merely fewer lines of code: accessing defaultdict(list)[missing_key] actually creates and inserts a fresh, empty list at that key, as a direct side effect of the mere access itself — this is genuinely different from dict.get(key, []), which simply returns a default value without ever inserting anything into the dict at all. This distinction matters genuinely if downstream code later checks if key in the_dict, since a defaultdict access can silently, unintentionally create new keys in ways a purely .get()-based approach never would. Counter similarly adds genuine, specific convenience beyond a plain defaultdict(int) — most notably .most_common(n) and built-in arithmetic operations directly between two separate Counter objects.

bisect.bisect_left/bisect_right/insort all operate on an already-sorted list, letting you efficiently find the correct insertion point for a new value, or directly insert while correctly preserving the existing sort order — the actual search itself runs in O(log n) time (though the physical insertion, if you choose to perform it, remains O(n), due to the underlying list-shifting cost). Using the standard library’s own implementation genuinely avoids the classic, subtle off-by-one bugs that come up surprisingly often in a hand-rolled binary search — correctly handling duplicate values, and correctly distinguishing a “leftmost” vs. “rightmost” valid insertion point — mistakes that are genuinely, deceptively easy to introduce when implementing this from scratch yourself.

A heap provides genuine O(log n) insertion and O(log n) “extract the minimum element” operations, all without needing to maintain a fully, completely sorted ordering across the entire structure at every single moment — this stands in real contrast to bisect.insort’s O(n) cost for inserting into a fully sorted list, since maintaining complete sort order at all times is inherently more expensive than a heap’s much weaker (but sufficient for many purposes) partial-ordering invariant. Real, practical scenarios: implementing a genuine priority queue (e.g., a task scheduler processing items strictly by priority, or the frontier data structure driving Dijkstra’s shortest-path algorithm), or efficiently finding just the k smallest or largest items out of a large stream of data, without needing to fully sort the entire thing first (heapq.nsmallest/heapq.nlargest, directly relevant to top-k selection problems).

Python uses Timsort — a hybrid algorithm combining merge sort and insertion sort, specifically optimized around a real-world observation that most practical data already contains meaningfully long partially-sorted runs, which Timsort exploits for genuinely better real-world performance than a naive general-purpose sort. It’s genuinely stable: elements that compare as exactly equal to one another retain their original, pre-sort relative order in the output. A real scenario where stability genuinely matters for correctness, not merely aesthetics: sorting a list of records by one field, having already previously sorted the same list by a different field — a common, deliberate multi-key sorting pattern (sort by the secondary key first, then perform a stable sort by the primary key afterward), where the earlier secondary-key ordering is correctly preserved within each group sharing the same primary-key value only because the sort is genuinely stable — this pattern breaks silently and genuinely confusingly if the underlying sort algorithm isn’t actually stable.

No — CPython performs genuinely no tail-call optimization whatsoever, regardless of whether a given recursive call happens to be positioned in tail position or not; every single recursive call, without exception, consumes a genuine, real stack frame. Python’s default recursion limit (typically around 1000 frames) exists specifically to catch runaway or genuinely infinite recursion cleanly, well before it would otherwise crash the entire process with a low-level C stack overflow — a Python-level RecursionError is a vastly more graceful, and far more debuggable, failure mode than an outright process crash/segfault would be. The genuine practical consequence: writing deeply recursive code over large inputs (processing a deeply nested data structure, or an algorithm that’s naturally expressed recursively) needs to be deliberately restructured as an iterative loop using an explicit, manually-managed stack in Python — you simply cannot rely on the recursive form scaling arbitrarily deep the way you might reasonably expect in a language like Scheme or Haskell that genuinely does perform tail-call optimization.

import sys

def depth(node):                       # recursive: one frame per level
    return 0 if node is None else 1 + depth(node.get("child"))

def depth_iter(node):                  # iterative: no frames, any depth
    d = 0
    while node is not None:
        d, node = d + 1, node.get("child")
    return d

nested = None
for _ in range(5000):
    nested = {"child": nested}

sys.getrecursionlimit()   # -> 1000
depth_iter(nested)        # -> 5000
depth(nested)             # RecursionError: maximum recursion depth exceeded

Why raising sys.setrecursionlimit is usually a smell

The limit protects against runaway recursion crashing the process via a C stack overflow, converting it into a clean, catchable RecursionError. Raising it (sys.setrecursionlimit(100_000)) instead of restructuring the algorithm is usually a smell rather than a fix: it doesn’t address what caused the deep recursion, it just moves the failure point further out — and past a certain depth the real, lower-level C stack runs out first, so instead of a catchable exception the process segfaults with no traceback. A modest bump for a known-bounded depth (a parser on input you control) is defensible; for input-driven depth (user-supplied JSON, a graph of unknown size), convert to an explicit stack.

CPython’s dict implementation uses open addressing — genuinely distinct from the separate chaining approach some other languages’ hash table implementations use — meaning that when a hash collision occurs (two different keys happening to hash to the same initial slot), the table instead probes onward to a different slot, following a specific, deterministic probing sequence, rather than building up a linked list of multiple colliding entries all stored at one single slot. The exact probing formula matters less than knowing conceptually that dicts are open-addressing-based, and why this choice affects load-factor and resize behavior — CPython dicts deliberately resize themselves well before actually becoming completely “full,” specifically to keep probe sequences reliably short and lookups genuinely fast even under real, everyday collision rates.

Implementing a singly linked list from scratch, and reversing it in place, exercises pointer/reference manipulation that’s genuinely rare in everyday Python work, which leans heavily on the built-in list instead. In-place reversal walks the list once, and at each node redirects its next pointer back toward the previous node before advancing — tracked via a prev/curr/next triple of references — giving O(n) time and O(1) extra space, with no auxiliary list needed.

The classic solution is Floyd’s cycle detection (the “slow/fast pointer,” or “tortoise and hare,” technique): two pointers walk the list at different speeds — one node at a time for the slow pointer, two at a time for the fast one. If a cycle exists, the fast pointer eventually laps the slow one and the two meet inside the loop; if the list is acyclic, the fast pointer simply reaches the end (None) first. This runs in O(1) space, unlike the naive alternative of tracking every visited node in a set (O(n) space).

The naive, brute-force nested-loop solution runs in O(n²) time. The optimized solution instead makes a single pass, using a hash set or dict to track values genuinely already seen so far, running in O(n) time at the cost of O(n) additional space — a classic, broadly-applicable “trade space for time via hashing” pattern that generalizes well beyond this one specific problem.

A classic stack-based problem: push every opening bracket encountered, and match/pop against the stack whenever a closing bracket is encountered — a mismatch, or a nonempty stack once input is exhausted, signals invalid input. A stack is the natural data structure here since brackets must close in strictly reverse (LIFO) order relative to how they opened.

For BFS (breadth-first search): a genuine queue (collections.deque — notably, using a plain list with pop(0) here is exactly the O(n)-pop anti-pattern described above for deque). For DFS (depth-first search): a genuine stack (either an explicit one, implemented as a plain list using .append()/.pop() from the right-hand end specifically, both genuinely O(1), or simply natural recursion itself, which is fundamentally just implicitly using the program’s own call stack as the stack). Each traversal order emerges naturally as a direct consequence of the underlying data structure’s own inherent ordering behavior — FIFO for a queue, LIFO for a stack — rather than being an arbitrary pairing to memorize.

A named tuple is a tuple subclass whose fields can be accessed both by position (p[0]) and by name (p.x), while still being a genuine tuple everywhere one is expected — unpacking, indexing, equality, hashing, and iteration all work exactly like a plain tuple. There are two ways to create one: collections.namedtuple("Point", ["x", "y"]), a runtime factory function that dynamically generates the class, and typing.NamedTuple, a class-based syntax (class Point(NamedTuple): x: int; y: int) that additionally carries type annotations a static checker can read. It’s reached for over a plain tuple specifically for readability at the call site — point.x self-documents in a way point[0] never does — and over a full class specifically for cost: like a plain tuple it’s immutable and carries no per-instance __dict__, so it’s meaningfully cheaper to create and store in bulk than an equivalent ordinary class instance (the same “reach for NamedTuple over a slotted class” progression shows up in “cutting memory for millions of small records” in the memory-and-performance subtopic). It’s also a genuinely convenient drop-in upgrade for existing tuple-based code, since every tuple operation a caller already relies on keeps working unchanged.

Yes, it can have methods — a named tuple is a real class, not a special-cased builtin, so ordinary methods, @property, @classmethod, and a docstring can all be added to it:

from typing import NamedTuple

class Point(NamedTuple):
    x: float
    y: float

    def distance_from_origin(self) -> float:
        return (self.x ** 2 + self.y ** 2) ** 0.5

Point(3, 4).distance_from_origin()  # 5.0

The same is possible with collections.namedtuple by subclassing the generated class and adding methods there. What you still can’t do is add a genuinely new mutable instance attribute outside the declared fields — the underlying tuple immutability doesn’t go away just because methods were added; only the declared fields exist as per-instance state, and methods themselves are ordinary shared class attributes, not duplicated per instance, exactly like on any other class.

A real, practical approach: a single pass over the data building up frequency counts using Counter (genuinely feasible in the very common real case where the counts themselves comfortably fit in memory, even though the raw underlying data volume itself doesn’t), then applying heapq.nlargest(k, counter.items(), key=...) specifically rather than fully sorting the entire counts collection — this runs in O(n log k) rather than a full O(n log n) sort, which is worth reaching for deliberately rather than sorting the full counts collection purely out of habit. For the genuinely harder, “doesn’t fit in memory even as raw counts” case, the natural next step is external/streaming approaches — chunked, incremental processing, or approximate-counting data structures like a Count-Min Sketch.