Data structures in Python

The Python mirror of Data structures in TypeScript. Part 1 is the batteries Python already includes — and Python includes far more than JavaScript, which changes what you should actually write in an interview. Part 2 is the from-scratch implementations you still need to be able to produce, because “just import it” is not an acceptable answer when the question is the data structure.

Everything runnable was executed on CPython 3.11.15; the test output at the end of Part 2 is real. The complexity numbers are the ones from Complexity §8.2, and the measured consequences (the accidental quadratics, the in list versus in set curve) live in Complexity §9 — this file does not re-measure them.

Table of contents

Part 1 — the built-ins

• 1. list
• 2. tuple, namedtuple, NamedTuple, dataclass
• 3. dict
• 4. set and frozenset
• 5. str, bytes, bytearray, memoryview
• 6. collections
• 7. heapq
• 8. bisect
• 9. array, struct, and numpy
• 10. itertools and functools as algorithm tools
• 11. What Python does not ship

Part 2 — from scratch

• 12. Dynamic array
• 13. Linked lists
• 14. Stacks and queues
• 15. Hash table
• 16. Binary heap
• 17. Binary search tree
• 18. AVL tree, and red-black in overview
• 19. Trie
• 20. Union-Find
• 21. Graph representations
• 22. LRU and LFU caches
• 23. Segment tree and Fenwick tree
• 24. Skip list
• 25. Bloom filter
• 26. SortedList on bisect
• 27. Persistent structures
• 28. Test run
• 29. The decision table

Gap note. Mutating a container while iterating it is one line here; the list case (which fails silently, unlike the dict) plus __missing__ for key-dependent defaults are in 20 §6.2 and 20 §5.5.

Part 1 — the built-ins

1. list

A list is a CPython dynamic array of PyObject* — 8 bytes per slot plus a 56-byte header, with the elements themselves allocated separately. That double indirection is why a list of a million small ints costs ~8 MB of pointers plus ~28 MB of int objects, and why array/bytes/NumPy exist.

Growth

Measured capacity steps as we append:

first capacity steps: [4, 8, 16, 24, 32, 40, 52, 64]
asymptotic growth factor: 1.125   (CPython: new = n + (n >> 3) + 6, rounded to a multiple of 4)
1,000,000 appends -> 86 reallocations

Growing by an eighth instead of doubling means ~9n total copying instead of 2n, in exchange for much less wasted memory and a better chance realloc can extend in place. Full derivation in Complexity §5.1.

The operations that surprise people

The aliasing trap

grid = [[0] * 3] * 3          # ONE inner list, referenced three times
grid[0][0] = 9
print(grid)                   # [[9, 0, 0], [9, 0, 0], [9, 0, 0]]

grid = [[0] * 3 for _ in range(3)]    # three distinct inner lists
grid[0][0] = 9
print(grid)                   # [[9, 0, 0], [0, 0, 0], [0, 0, 0]]

[[0]*3] is fine — 0 is immutable, so sharing it is invisible. [x]*n is only a bug when x is mutable. This is the single most common Python interview bug in 2D-grid problems.

sort and keys

rows = [('bob', 3), ('ann', 1), ('cid', 3)]

rows.sort(key=lambda r: r[1])                  # stable: ('bob',3) stays before ('cid',3)
rows.sort(key=lambda r: (-r[1], r[0]))         # descending by count, then ascending by name
rows.sort(key=operator.itemgetter(1))          # ~30% faster than the lambda: stays in C

from functools import cmp_to_key
rows.sort(key=cmp_to_key(lambda a, b: custom(a, b)))   # only when you truly need a comparator

Three things to say about sort:

• key is called once per element (n calls), a comparator is called O(n log n) times. That is why key= is preferred and why cmp_to_key is a last resort.
• Stability is guaranteed, which is what makes multi-pass sorting work: sort by the secondary key first, then by the primary key.
• reverse=True preserves stability (it is not “sort then reverse”), so equal elements keep their original relative order either way.

Interview follow-ups

Q: list.sort() vs sorted()?

A: sort() is a list method, in place, returns None (so x = a.sort() is a classic bug). sorted() accepts any iterable and returns a new list. Both are Timsort.

Q: Why is a.insert(0, x) in a loop a bug?

A: Each insert is an O(n) memmove, so the loop is O(n^2). Measured: 145x slower than deque.appendleft at n=32,000. Use a deque, or append and reverse at the end.

Q: How do you remove items from a list while iterating?

A: You do not. Build a new list with a comprehension, or iterate over a copy (for x in a[:]), or walk backwards by index. Mutating during forward iteration skips elements.

2. tuple, namedtuple, NamedTuple, dataclass

sys.getsizeof: tuple of 3 = 64 bytes    list of 3 = 88 bytes

Tuples have no spare capacity and no growth machinery, so they are smaller, and they are hashable when their contents are — which is what makes them usable as dict keys, set members, and heap priorities.

from collections import namedtuple
from typing import NamedTuple
from dataclasses import dataclass, field, replace

Point = namedtuple('Point', 'x y', defaults=(0, 0))

class Vec(NamedTuple):
    x: float
    y: float = 0.0
    def norm(self) -> float: return (self.x ** 2 + self.y ** 2) ** 0.5

@dataclass(frozen=True, slots=True, order=True)
class Money:
    amount: int
    currency: str = 'USD'
    def __post_init__(self):
        if self.amount < 0: raise ValueError('negative')

m = Money(100)
m2 = replace(m, amount=200)        # the frozen-dataclass "update" idiom

order=True generates __lt__/__le__/__gt__/__ge__ from field order, which makes the object directly usable as a heap element. field(compare=False) excludes a field from equality and ordering — useful for a payload you do not want compared.

Interview follow-ups

Q: When is a tuple faster than a list?

A: Construction (no over-allocation, and CPython keeps a free list of small tuples) and as a constant (a tuple literal of constants is folded at compile time; a list literal is built every time). Indexing is identical.

Q: Why can a tuple be unhashable?

A: hash recurses into the elements, so ([1], 2) raises TypeError. Hashability is about contents, not the container.

Q: dataclass vs NamedTuple?

A: NamedTuple when the thing genuinely is a positional record you want to unpack and use as a key; dataclass when it is an object with behaviour, mutability, or many optional fields. NamedTuple’s tuple-ness is a footgun when someone unpacks it and you later add a field.

3. dict

Since 3.6 (implementation) and 3.7 (language guarantee), dicts are insertion-ordered, because of the compact layout: a dense array of (hash, key, value) entries in insertion order, plus a sparse array of indices into it.

sparse indices:  [ -, 1, -, -, 0, -, 2, - ]      <- hash-addressed, mostly empty
dense entries:   [ (h,'b',1), (h,'a',2), (h,'c',3) ]   <- insertion order, iterated directly

Consequences: iteration is a dense scan (fast, ordered), the memory overhead dropped ~20% from the old design, and dict and OrderedDict are no longer very different. Instances of the same class also share the key table (PEP 412), which is why the second instance’s __dict__ is much smaller than the first’s.

Collision resolution is open addressing with a perturbation recurrence, j = (5*j + 1 + perturb) & mask with perturb >>= 5, which mixes in the high bits of the hash instead of probing linearly. Resize happens at 2/3 full, growing to 3x the used size.

Access patterns, ranked

Measured in Python core §9.2:

d.get(k, default)                   # 31.3 ns — the balanced default
try: d[k]
except KeyError: ...                # 25.7 ns on a hit, 159.6 ns on a miss (EAFP)
if k in d: d[k]                     # 40.8 ns — always the loser, two hash lookups
d.setdefault(k, []).append(x)       # one lookup, but the default is built every call
defaultdict(list)[k].append(x)      # one lookup, default built lazily — the winner for grouping

setdefault’s hidden cost is that the default expression is evaluated whether or not it is needed, so d.setdefault(k, expensive()) calls expensive() every time. defaultdict does not have that problem, but reading a missing key on a defaultdict creates it — use .get() when you only want to look.

d1 | d2                             # 3.9+: merged copy, right side wins
d1 |= d2                            # in-place update
{k: v for k, v in pairs if v}       # comprehension
d.keys() & other_set                # views are set-like: &, |, -, ^
d.items() - other.items()           # works when the values are hashable
list(d)                             # keys, in insertion order
dict(zip(keys, values))             # the standard build-from-two-lists idiom

Mutating a dict while iterating it raises RuntimeError: dictionary changed size during iteration. Iterate over list(d) or list(d.items()) if you must modify.

Interview follow-ups

Q: Is dict ordering guaranteed?

A: Yes since Python 3.7 (it was an implementation detail of CPython 3.6). OrderedDict still exists for move_to_end, popitem(last=False), and order-sensitive __eq__.

Q: What is the worst case for a dict lookup?

A: O(n), when every key collides. Reachable by an adversary who knows the hash function — which is why CPython randomizes the string hash seed by default (PYTHONHASHSEED).

Q: What can be a dict key?

A: Anything hashable: immutable built-ins, tuples of hashables, frozensets, and objects with a consistent __hash__/__eq__. Note 1, 1.0 and True are the same key because they are equal and hash equally.

4. set and frozenset

Same open-addressing machinery as dict without the values. set() costs 216 bytes empty because it pre-allocates 8 slots inline.

Verified: intersecting a 100,000-element set with a 50-element set costs the same as intersecting a 10,000-element one with the same 50 — the min in the bound is real. So write small & big, not big & small, when you can control it (though CPython swaps them for you).

frozenset is the hashable version, so it can be a dict key or a set member — the standard way to key on “a set of things” (e.g. memoizing over a subset).

Sets are unordered. Do not rely on iteration order; it is a function of hash values and insertion history, and it differs between runs for strings because of hash randomization.

5. str, bytes, bytearray, memoryview

str is a sequence of code points (not UTF-16 code units like JavaScript), stored in a compact representation chosen per string: 1 byte per char for pure Latin-1, 2 for BMP, 4 otherwise. So len('café') == 4 and '😀'[0] == '😀' — both of which differ from JavaScript. See JS core §8.4 for the contrast.

Building strings

''.join(parts)                    # 26–34 ns/char, reliably linear — the answer
s += chunk                        # 42 ns/char and linear ONLY when s is a local with refcount 1

CPython has an in-place resize optimization for s += t that fires when the target is a STORE_FAST local holding the only reference. Break either condition — store it on an object attribute, keep another name pointing at it, close over it — and the loop becomes quadratic. Measured, both cases, in Complexity §9.3. The interview answer is: use join; += is linear by accident.

s[a:b]                            # O(b-a) — copies
s.find / index / replace / count  # O(n·m) worst; CPython uses a Crochemore-Perrin variant, near-linear
s.startswith(tuple_of_prefixes)   # accepts a tuple — one call instead of a chain of `or`
s.split(None)                     # split on runs of whitespace and strip; s.split(' ') does not
str.maketrans / s.translate       # the fast path for character-level substitution
s.encode('utf-8')                 # -> bytes; decode goes back

When to reach for the byte types

b = bytearray(1024)               # mutable, so you can build binary in place
mv = memoryview(b)[100:200]       # a VIEW: zero copy, and writes through to b
mv[0] = 65                        # b[100] == 65
import struct
struct.pack('<IHf', 1, 2, 3.0)    # fixed-layout binary

memoryview is the answer to “how do you slice a large buffer without copying” — the only zero-copy slice in the language.

6. collections

This module is the single biggest reason Python interviews go faster than JavaScript ones.

deque

from collections import deque

dq = deque([1, 2, 3], maxlen=3)   # a bounded deque: appending drops from the other end
dq.append(4)                       # deque([2, 3, 4]) — a sliding window in one line
dq.appendleft(0)
dq.pop(); dq.popleft()             # all four are O(1)
dq.rotate(1)                       # O(k)
dq.extendleft([1, 2])              # note: reverses the input

That last row matters: a deque is a doubly linked list of 64-element blocks, so it is not random access. If you need both O(1) ends and O(1) indexing, you need a ring buffer (section 14).

Use it for: BFS queues (never list.pop(0)), sliding-window maxima via a monotonic deque, “last k items” via maxlen, and undo stacks.

defaultdict, Counter, OrderedDict, ChainMap

from collections import defaultdict, Counter, OrderedDict, ChainMap

graph = defaultdict(list)          # graph[u].append(v) with no key check
counts = defaultdict(int)
grid = defaultdict(lambda: defaultdict(int))    # nested, arbitrary depth
# WARNING: `if graph[u]` CREATES graph[u]. Use `graph.get(u)` to look without creating.

c = Counter('mississippi')
c.most_common(2)                   # [('i', 4), ('s', 4)] — O(n log k)
c.most_common()                    # full sort, O(n log n)
c1 + c2; c1 - c2; c1 & c2; c1 | c2 # multiset add / subtract-clamped-at-0 / min / max
c.total()                          # 3.10+
Counter(a) == Counter(b)           # the anagram one-liner

od = OrderedDict()
od.move_to_end(k, last=True)       # what plain dict still cannot do
od.popitem(last=False)             # FIFO eviction -> the LRU building block
od1 == od2                         # order-sensitive, unlike dict

cfg = ChainMap(cli_args, env_vars, defaults)   # layered lookup without merging

Counter subtraction clamping at zero is a real gotcha: Counter('a') - Counter('aa') is Counter(), not a negative count. Use c.subtract(other) if you want negatives.

7. heapq

heapq operates on a plain list interpreted as a min-heap. There is no heap object and there is no max-heap before 3.14.

import heapq

h = [5, 1, 9, 3]
heapq.heapify(h)                        # O(n), in place — not n log n
heapq.heappush(h, 4)                    # O(log n)
smallest = heapq.heappop(h)             # O(log n)
top = h[0]                              # O(1) peek
heapq.heappushpop(h, x)                 # push then pop, ONE sift — cheaper than two calls
heapq.heapreplace(h, x)                 # pop then push (h must be non-empty)

heapq.nlargest(k, iterable, key=...)    # O(n log k) — beats sorted(it)[:k]
heapq.nsmallest(k, iterable)
heapq.merge(*sorted_iters)              # lazy k-way merge, O(1) memory per stream

The two idioms you must know

Max-heap by negation. Push -value, pop and negate. For tuples, negate the priority only: (-priority, item).

The counter tiebreak. Heap entries are compared with <, and tuples compare lexicographically — so if two priorities tie, Python compares the payload, which explodes if the payload is not orderable.

import itertools
counter = itertools.count()
heapq.heappush(h, (priority, next(counter), task))   # the counter breaks ties, task is never compared

That three-element form also gives you FIFO behaviour among equal priorities for free. It is the single most useful heapq idiom and it comes up in nearly every priority-queue interview.

Python 3.14 adds heappush_max, heappop_max, heapify_max, heapreplace_max, heappushpop_max — so the negation trick becomes optional. Until you can rely on 3.14, negate.

Interview follow-ups

Q: Why is heapify O(n)?

A: Sift down from the last internal node up. Nodes at height h cost O(h) and there are n/2^(h+1) of them; the sum telescopes to 2n. Most nodes are near the leaves and cost nothing.

Q: heapq.nlargest(k, xs) versus sorted(xs)[-k:]?

A: O(n log k) versus O(n log n), and O(k) memory versus O(n). For k=10 out of 1e6 the heap version wins clearly; for k close to n, sorted wins because it stays in C.

Q: How do you implement decrease-key?

A: heapq cannot. Either push a duplicate entry with the better priority and skip stale entries on pop (the standard “lazy deletion” Dijkstra), or write an indexed heap with a key -> position map (section 16).

8. bisect

Binary search over an already-sorted sequence. Two functions, and knowing which is which answers five different questions.

import bisect
a = [1, 3, 3, 5, 9]

bisect.bisect_left(a, 3)     # 1  — first index with a[i] >= 3   (lower bound)
bisect.bisect_right(a, 3)    # 3  — first index with a[i] >  3   (upper bound)

# derived, all verified:
count_of_3 = bisect.bisect_right(a, 3) - bisect.bisect_left(a, 3)   # 2
ceil_index = bisect.bisect_left(a, 4)                                # 3 -> a[3] == 5
floor_index = bisect.bisect_left(a, 4) - 1                           # 2 -> a[2] == 3
rank_of_5 = bisect.bisect_left(a, 5)                                 # 3 (elements strictly less)

bisect.insort(a, 4)          # O(log n) search + O(n) memmove -> building is O(n^2)
bisect.bisect_left(rows, target, key=lambda r: r.score)   # 3.10+
bisect.bisect_left(a, x, lo, hi)                          # bounded search

insort being O(n) is measured in Complexity §9.5 — the search is flat, the insert is not. Use it when the list is small or writes are rare; otherwise collect and sort once, or use sortedcontainers.

Before 3.10 there was no key=, so the idiom was to keep a parallel list of keys, or to store tuples. Worth knowing because a lot of existing code does that.

9. array, struct, and numpy

from array import array
a = array('q', range(1000))     # 'q' = signed 64-bit; 8 bytes/element, no PyObject per element
a = array('d', [1.5, 2.5])      # doubles

array gives you unboxed homogeneous numbers with the list API. Roughly 4x less memory than a list of ints and much better cache behaviour, at the cost of a box/unbox on every element access — so it wins for storage and loses for heavy per-element Python arithmetic.

struct handles fixed binary layouts (struct.pack('<IHf', ...)), which is what you need for file formats, wire protocols and mmap.

NumPy, in one paragraph: the loop moves into C. arr * 2 + 1 on a million floats is one pass of compiled code with no interpreter overhead and no boxing, typically 50–100x faster than the equivalent Python loop, and it releases the GIL for the heavy kernels so it also threads. The rules are: never write a Python loop over a NumPy array (vectorize, or use np.where/np.add.at), watch out for views-versus-copies (basic slicing gives a view, fancy indexing gives a copy), and be careful with dtypes because integer overflow is silent. If a coding round involves real numeric work and the interviewer allows imports, saying “I would reach for NumPy here and why” is the senior answer.

10. itertools and functools as algorithm tools

from itertools import (accumulate, pairwise, groupby, product, permutations, combinations,
                       combinations_with_replacement, chain, islice, tee, cycle, count, repeat,
                       zip_longest, takewhile, dropwhile, starmap, compress, filterfalse)

list(accumulate([1, 2, 3, 4]))            # [1, 3, 6, 10]   prefix sums in one call
list(accumulate([3, 1, 4], max))          # [3, 3, 4]       running maximum
list(accumulate([1, 2, 3], initial=0))    # [0, 1, 3, 6]    3.8+, the version you usually want for DP
list(pairwise('abc'))                     # [('a','b'), ('b','c')]   adjacent pairs, 3.10+
list(islice(count(10, 2), 4))             # [10, 12, 14, 16]  slice an infinite iterator
list(chain.from_iterable([[1,2],[3]]))    # [1, 2, 3]       flatten one level
list(product('ab', repeat=2))             # the nested-loop cartesian product
list(combinations(range(4), 2))           # C(4,2) subsets, in lexicographic order
a, b = tee(it)                            # two independent iterators over one source

groupby groups only consecutive equal keys. Verified:

groupby('aaabbc')  -> [('a',3), ('b',2), ('c',1)]
groupby('ababa')   -> [('a',1), ('b',1), ('a',1), ('b',1), ('a',1)]     <- not what people expect

So groupby requires the input to be sorted by the same key. If you want a true grouping, use defaultdict(list).

from functools import cache, lru_cache, reduce, partial, cached_property, cmp_to_key, singledispatch

@cache                                     # 3.9+: unbounded memoization, one decorator
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)

@lru_cache(maxsize=None)
def dp(i, j): ...                          # top-down DP in two lines — see 10-dynamic-programming.md

reduce(lambda a, b: a ^ b, xs, 0)          # fold
partial(fn, arg1)                          # pre-bind arguments

@cache on a recursive function is the fastest way to turn an exponential recursion into a polynomial one, and it is the idiomatic Python answer to most memoization questions. Its limits: arguments must be hashable (so no lists — convert to tuples), it holds strong references to arguments and results (so decorating a method leaks every self), and it is per-process.

Recipes worth memorizing:

def sliding_window(it, n):
    d = deque(islice(it, n), maxlen=n)
    if len(d) == n: yield tuple(d)
    for x in it: d.append(x); yield tuple(d)

def chunked(it, n):
    it = iter(it)
    return iter(lambda: list(islice(it, n)), [])

def unique_everseen(it):
    seen = set()
    for x in it:
        if x not in seen: seen.add(x); yield x

11. What Python does not ship

Two things worth saying in an interview. First, int being arbitrary-precision makes Python unexpectedly good at bitmask problems — no overflow, no BigInt ceremony. Second, sortedcontainers.SortedList is the answer to “Python has no TreeMap”: it keeps a list of sublists of size ~sqrt(n), so an insert is a binary search plus an O(sqrt n) splice. Formally worse than O(log n), in practice faster than any tree for n into the millions because the memmove is one C call.

Part 2 — from scratch

The intuition, ASCII diagrams and complexity tables for these structures are in Data structures in TypeScript and are not repeated here — this half is the Python implementation, the Pythonic shortcut where one exists, and the follow-ups that are specific to this language. In an interview, say which one you would actually write and why.

12. Dynamic array

Python’s list is this, so implementing it is purely an “explain the amortization” exercise. Note this version doubles (2x) rather than using CPython’s 1.125x, because doubling is what the amortized proof is usually stated for.

from typing import Generic, Optional, TypeVar
T = TypeVar("T")

class DynArray(Generic[T]):
    def __init__(self) -> None:
        self._cap, self._n = 1, 0
        self._buf: list[Optional[T]] = [None]
        self.grows = 0

    def __len__(self) -> int: return self._n

    def __getitem__(self, i: int) -> T:
        if not 0 <= i < self._n: raise IndexError(i)
        return self._buf[i]                       # type: ignore[return-value]

    def append(self, v: T) -> None:
        if self._n == self._cap: self._resize(self._cap * 2)
        self._buf[self._n] = v; self._n += 1

    def pop(self) -> T:
        if not self._n: raise IndexError("empty")
        self._n -= 1
        v = self._buf[self._n]; self._buf[self._n] = None    # drop the reference so it can be collected
        if 0 < self._n <= self._cap // 4: self._resize(self._cap // 2)   # shrink at a QUARTER, not a half
        return v                                  # type: ignore[return-value]

    def _resize(self, cap: int) -> None:
        self.grows += 1
        new: list[Optional[T]] = [None] * cap
        new[:self._n] = self._buf[:self._n]
        self._buf, self._cap = new, cap

  ok  DynArray: 1000 appends -> 12 reallocations (log2), shrinks at quarter-full

Two details interviewers probe. Shrinking at a quarter, not a half, avoids thrashing: if you shrank at half-full, an alternating push/pop at the boundary would resize on every operation, destroying the amortized bound. And clearing the popped slot matters in a reference-counted language — leaving the pointer there keeps the object alive.

Interview follow-ups.

Q: Why is the growth factor 2 and not 1.1 or 4?

A: Total copying is n·g/(g-1): doubling gives 2n, 1.5x gives 3n, and CPython’s 1.125x gives 9n. Larger factors copy less but waste more memory and are less likely to realloc in place. Doubling is the textbook compromise; CPython chose memory over copies.

Q: What is the amortized cost of append, and by which method?

A: O(1). Potential method: Phi = 2·size - capacity; both resizing and non-resizing appends have amortized cost 3. Full derivation in Complexity §5.1.

13. Linked lists

Python has no built-in linked list and you rarely want one — but the interview questions are unavoidable, and they are all variations on two pointers.

class LNode(Generic[T]):
    __slots__ = ("val", "next")                   # __slots__ matters here: millions of tiny nodes
    def __init__(self, val: T, nxt: "Optional[LNode[T]]" = None):
        self.val, self.next = val, nxt

def reverse_iter(h):
    prev = None
    while h:
        h.next, prev, h = prev, h, h.next         # simultaneous assignment: RHS evaluated first
    return prev

def reverse_rec(h):
    if h is None or h.next is None: return h
    new = reverse_rec(h.next)
    h.next.next = h; h.next = None
    return new                                     # O(n) stack — dies above ~1000 nodes in Python

def has_cycle(h):                                  # Floyd's tortoise and hare
    slow = fast = h
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True
    return False

def cycle_start(h):
    slow = fast = h
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = h                               # reset one pointer to the head...
            while slow is not fast:                # ...and advance both one step at a time
                slow, fast = slow.next, fast.next
            return slow
    return None

def middle(h):                                     # fast/slow: fast moves 2, slow moves 1
    slow = fast = h
    while fast and fast.next: slow, fast = slow.next, fast.next.next
    return slow

def merge_sorted(a, b):
    dummy = tail = LNode(None)                     # sentinel: no special case for the first node
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next    # <= keeps it stable
        else:              tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

def remove_nth_from_end(h, n):
    dummy = LNode(None, h)
    fast = slow = dummy
    for _ in range(n): fast = fast.next            # open a gap of n...
    while fast.next: fast, slow = fast.next, slow.next   # ...then walk both to the end
    slow.next = slow.next.next
    return dummy.next

def is_palindrome(h):
    mid = middle(h)
    second = reverse_iter(mid)                     # destroys the second half; restore it if the caller cares
    first = h
    while second:
        if first.val != second.val: return False
        first, second = first.next, second.next
    return True

  ok  linked list: reverse (iter+rec), Floyd cycle + start, merge, middle, remove-nth, palindrome

Three transferable techniques hide in there, and naming them is worth more than the code:

• Dummy/sentinel head — removes every “is this the first node” special case (merge_sorted, remove_nth_from_end).
• Fast/slow pointers — finds the middle in one pass, detects cycles, and finds the kth-from-end.
• The cycle-start proof — if the tortoise has walked mu steps into a cycle of length lambda, the meeting point is exactly mu steps from the cycle entry going forward, which is why resetting one pointer to the head and stepping both by one lands on the entry.

Python’s simultaneous assignment is what makes reverse_iter a one-liner: the whole right-hand side is evaluated into a tuple before any name is rebound. That is a genuinely nice thing to point out.

Interview follow-ups.

Q: When would you use a linked list in real Python?

A: Almost never. deque covers O(1)-at-both-ends, and it is a C-implemented linked list of blocks, so it also has good locality. Real uses: an LRU cache’s recency list (section 22), and an intrusive list where nodes must be unlinked in O(1) from arbitrary positions.

Q: Why is recursive reversal dangerous here?

A: The default recursion limit is ~1000 frames, so any list longer than that raises RecursionError. See Complexity §4.1.

Q: How do you detect a cycle without Floyd?

A: A set of id(node) — O(n) time and O(n) space. Floyd’s is the O(1)-space version, and that is the whole point of the question.

14. Stacks and queues

# Stack: a list IS a stack. append/pop are both O(1) amortized.
stack: list[int] = []
stack.append(1); stack.pop()

# Queue: NEVER a list. list.pop(0) is O(n) -> the loop is O(n^2).
from collections import deque
q = deque([1, 2, 3])
q.append(4); q.popleft()          # both O(1)

That is the whole answer for production code. The two from-scratch versions exist for the interview.

class TwoStackQueue(Generic[T]):
    """Amortized O(1): each element moves from _in to _out exactly once."""
    def __init__(self) -> None: self._in: list[T] = []; self._out: list[T] = []
    def enqueue(self, x: T) -> None: self._in.append(x)
    def dequeue(self) -> T:
        if not self._out:
            while self._in: self._out.append(self._in.pop())
        if not self._out: raise IndexError("empty")
        return self._out.pop()
    def __len__(self) -> int: return len(self._in) + len(self._out)


class RingQueue(Generic[T]):
    """True O(1) per operation, no amortization spike. head + count, no tail pointer."""
    def __init__(self, cap: int = 8) -> None:
        self._buf: list[Optional[T]] = [None] * cap
        self._head = self._n = 0
    def __len__(self) -> int: return self._n
    def push(self, x: T) -> None:
        if self._n == len(self._buf): self._grow()
        self._buf[(self._head + self._n) % len(self._buf)] = x
        self._n += 1
    def pop(self) -> T:
        if not self._n: raise IndexError("empty")
        v = self._buf[self._head]; self._buf[self._head] = None
        self._head = (self._head + 1) % len(self._buf); self._n -= 1
        return v                                  # type: ignore[return-value]
    def _grow(self) -> None:
        new: list[Optional[T]] = [None] * (len(self._buf) * 2)
        for i in range(self._n): new[i] = self._buf[(self._head + i) % len(self._buf)]
        self._buf, self._head = new, 0

  ok  TwoStackQueue (amortized O(1)) and RingQueue (true O(1), grows)

Storing head + count instead of head + tail avoids the classic “is the buffer empty or full?” ambiguity when the two pointers coincide.

Interview follow-ups.

Q: Amortized versus worst-case O(1) — why does the difference matter?

A: The two-stack queue has an O(n) spike on the dequeue that triggers a transfer. For a p99.9 latency budget or a real-time loop, that spike is a bug; the ring buffer has no spike. Same average, different tail.

Q: Implement a stack with O(1) min.

A: Keep a second stack of running minima: push min(x, mins[-1]) on every push, pop both together. O(1) for all three operations, O(n) extra space. A single-stack version stores (value, min_so_far) tuples.

Q: What is queue.Queue for?

A: Thread-safe producer/consumer with blocking get/put, task_done/join, and bounded size. It is much slower than deque because of the locks; use deque for single-threaded work (deque.append/popleft are individually atomic under the GIL, but a check-then-act sequence is not).

15. Hash table

graph TD
    A["Compute i = hash(k) & mask<br/>(perturbation probe)"] --> B{"Slot i empty (None)?"}
    B -- Yes --> C["Insert at first tombstone seen,<br/>else at i"]
    C --> D["Done: key inserted"]
    B -- No --> E{"Slot i is a tombstone?"}
    E -- Yes --> F["Remember first tombstone index<br/>(if not already set)"]
    F --> G["Advance probe: i = 5i + 1 + perturb"]
    G --> B
    E -- No --> H{"Slot i key equals k?"}
    H -- Yes --> I["Overwrite value at i"]
    I --> J["Done: key updated"]
    H -- No --> G

Both open-addressing and chaining, and the open-addressing version deliberately mirrors CPython’s perturbation probe sequence so you can talk about the real implementation.

class ChainMapHT(Generic[T]):
    """Separate chaining. Simple, tolerant of high load factors, one extra indirection per probe."""
    def __init__(self, cap: int = 8) -> None:
        self._buckets: list[list[tuple[Any, T]]] = [[] for _ in range(cap)]
        self._n = 0

    def _idx(self, k: Any) -> int: return hash(k) & (len(self._buckets) - 1)   # power-of-two mask

    def __setitem__(self, k: Any, v: T) -> None:
        b = self._buckets[self._idx(k)]
        for i, (kk, _) in enumerate(b):
            if kk == k: b[i] = (k, v); return
        b.append((k, v)); self._n += 1
        if self._n > len(self._buckets) * 0.75: self._resize()

    def __getitem__(self, k: Any) -> T:
        for kk, v in self._buckets[self._idx(k)]:
            if kk == k: return v
        raise KeyError(k)

    def __delitem__(self, k: Any) -> None:
        b = self._buckets[self._idx(k)]
        for i, (kk, _) in enumerate(b):
            if kk == k: b.pop(i); self._n -= 1; return
        raise KeyError(k)

    def _resize(self) -> None:
        items = [(k, v) for b in self._buckets for k, v in b]
        self._buckets = [[] for _ in range(len(self._buckets) * 2)]; self._n = 0
        for k, v in items: self[k] = v            # rehash everything: O(n), amortized into the inserts


_TOMB = object()                                   # tombstone sentinel

class OpenAddrHT:
    """Open addressing with CPython's perturbation recurrence. Better locality, needs tombstones."""
    def __init__(self, cap: int = 8) -> None:
        self._keys: list[Any] = [None] * cap
        self._vals: list[Any] = [None] * cap
        self._n = 0

    def _probe(self, k: Any) -> Iterator[int]:
        mask = len(self._keys) - 1
        i = hash(k) & mask
        perturb = hash(k)
        for _ in range(len(self._keys)):
            yield i
            perturb >>= 5
            i = (5 * i + 1 + perturb) & mask      # mixes in the HIGH bits, unlike linear probing

    def __setitem__(self, k, v):
        first_tomb = None
        for i in self._probe(k):
            if self._keys[i] is None:                        # empty slot: the key is definitely absent
                tgt = first_tomb if first_tomb is not None else i
                self._keys[tgt], self._vals[tgt] = k, v; self._n += 1; break
            if self._keys[i] is _TOMB:
                if first_tomb is None: first_tomb = i        # remember it, but keep probing for the key
                continue
            if self._keys[i] == k: self._vals[i] = v; return
        if self._n > len(self._keys) * 0.66: self._resize()

    def __getitem__(self, k):
        for i in self._probe(k):
            if self._keys[i] is None: raise KeyError(k)      # stop only at a TRUE empty
            if self._keys[i] is not _TOMB and self._keys[i] == k: return self._vals[i]
        raise KeyError(k)

    def __delitem__(self, k):
        for i in self._probe(k):
            if self._keys[i] is None: raise KeyError(k)
            if self._keys[i] is not _TOMB and self._keys[i] == k:
                self._keys[i] = _TOMB; self._vals[i] = None; self._n -= 1; return
        raise KeyError(k)

  ok  hash table: separate chaining and open addressing with tombstones + CPython perturbation

The tombstone logic is the part people get wrong, and it is exactly what an interviewer will poke at. A deletion cannot write None, because a probe stops at None — doing so would make every key whose probe sequence passed through that slot unfindable. So deletion writes a tombstone, lookups skip tombstones but keep going, and insertion reuses the first tombstone it saw only after confirming the key is not present further along.

Interview follow-ups.

Q: Why does CPython perturb instead of probing linearly?

A: hash(k) & mask only uses the low bits, so keys differing only in high bits collide. The recurrence i = 5i + 1 + perturb (with perturb >>= 5) folds the high bits in, so clustering from structured keys (like consecutive integers or interned strings) is broken up.

Q: Why must the table size be a power of two here?

A: So & (cap - 1) replaces a modulo. The alternative is a prime size with real %, which distributes worse-quality hashes better. Python chose power-of-two plus perturbation; Java chose power-of-two plus a hash spread; C++ implementations often use primes.

Q: What is the worst case and how do real implementations defend against it?

A: O(n) per operation when everything collides, which is a remote-DoS vector on any service that hashes user input. Defences: a randomized per-process hash seed (Python does this by default since 3.3), SipHash for strings, and switching a long bucket to a tree (Java 8+).

Q: How do you avoid the rehash latency spike?

A: Incremental rehashing: keep both tables and migrate a few buckets per operation (what Redis does). The amortized cost is the same; the tail latency is far better.

16. Binary heap

heapq is what you use. The class exists for the interview and for the key= support heapq lacks.

class MinHeap(Generic[T]):
    def __init__(self, items: Optional[list[T]] = None, key: Callable[[T], Any] = lambda x: x) -> None:
        self._a: list[T] = list(items or []); self._key = key
        for i in range(len(self._a) // 2 - 1, -1, -1): self._sift_down(i)      # O(n) heapify

    def __len__(self) -> int: return len(self._a)
    def peek(self) -> T: return self._a[0]

    def push(self, v: T) -> None: self._a.append(v); self._sift_up(len(self._a) - 1)

    def pop(self) -> T:
        top, last = self._a[0], self._a.pop()      # move the LAST element to the root, then sift down
        if self._a: self._a[0] = last; self._sift_down(0)
        return top

    def _sift_up(self, i: int) -> None:
        while i and self._key(self._a[i]) < self._key(self._a[(i - 1) // 2]):
            p = (i - 1) // 2
            self._a[i], self._a[p] = self._a[p], self._a[i]
            i = p

    def _sift_down(self, i: int) -> None:
        n = len(self._a)
        while True:
            small, l, r = i, 2 * i + 1, 2 * i + 2
            if l < n and self._key(self._a[l]) < self._key(self._a[small]): small = l
            if r < n and self._key(self._a[r]) < self._key(self._a[small]): small = r
            if small == i: return
            self._a[i], self._a[small] = self._a[small], self._a[i]
            i = small

Index arithmetic for a 0-indexed array heap: parent of i is (i-1)//2, children are 2i+1 and 2i+2. (For 1-indexed it is i//2, 2i, 2i+1, which is why some texts waste index 0.)

Running median with two heaps

import heapq

class MedianFinder:
    """lo is a max-heap (negated values), hi is a min-heap. Invariant: len(lo) == len(hi) or len(lo)+1."""
    def __init__(self) -> None:
        self.lo: list[float] = []      # the smaller half, negated
        self.hi: list[float] = []      # the larger half

    def add(self, x: float) -> None:
        heapq.heappush(self.lo, -x)                        # always push left...
        heapq.heappush(self.hi, -heapq.heappop(self.lo))   # ...then move its max to the right
        if len(self.hi) > len(self.lo):                    # ...and rebalance if needed
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self) -> float:
        if len(self.lo) > len(self.hi): return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

The three-line add is the trick: pushing left then moving the max right guarantees the element lands in the correct half without any comparison logic.

Indexed heap with decrease-key

heapq cannot decrease a key, so Dijkstra with heapq either pushes duplicates and skips stale pops (“lazy deletion”, which is what everyone actually writes) or you carry a position map:

class IndexedHeap:
    """Decrease-key in O(log n) via a key -> position map. No stale entries."""
    def __init__(self) -> None:
        self._a: list[tuple[float, Any]] = []
        self._pos: dict[Any, int] = {}

    def __len__(self) -> int: return len(self._a)
    def __contains__(self, k) -> bool: return k in self._pos

    def push(self, key, pri) -> None:
        self._a.append((pri, key)); self._pos[key] = len(self._a) - 1; self._up(len(self._a) - 1)

    def decrease(self, key, pri) -> bool:
        i = self._pos[key]
        if pri >= self._a[i][0]: return False
        self._a[i] = (pri, key); self._up(i); return True

    def pop(self):
        pri, key = self._a[0]
        last = self._a.pop(); del self._pos[key]
        if self._a: self._a[0] = last; self._pos[last[1]] = 0; self._down(0)
        return key, pri

    def _swap(self, i, j) -> None:
        self._a[i], self._a[j] = self._a[j], self._a[i]
        self._pos[self._a[i][1]], self._pos[self._a[j][1]] = i, j

    def _up(self, i) -> None:
        while i and self._a[i][0] < self._a[(i - 1) // 2][0]: self._swap(i, (i - 1) // 2); i = (i - 1) // 2

    def _down(self, i) -> None:
        n = len(self._a)
        while True:
            s, l, r = i, 2 * i + 1, 2 * i + 2
            if l < n and self._a[l][0] < self._a[s][0]: s = l
            if r < n and self._a[r][0] < self._a[s][0]: s = r
            if s == i: return
            self._swap(i, s); i = s

  ok  MinHeap: O(n) heapify then n pops == sorted; MedianFinder via two heaps
  ok  IndexedHeap: decrease-key in O(log n) via a key->position map (Dijkstra without stale entries)

Every swap must update the position map — forgetting that in _swap is the bug that makes this class silently wrong.

Lazy deletion versus decrease-key: lazy is O(E log E) with up to E entries in the heap; decrease-key is O(E log V) with at most V. For sparse graphs the difference is small and lazy is ten lines shorter, which is why it wins in interviews. Say that you know both.

Interview follow-ups.

Q: Why move the last element to the root on pop instead of promoting the smaller child?

A: Promoting children recursively leaves a hole that has to be filled anyway, and it can require O(n) work to keep the shape complete. Moving the last element keeps the tree complete by construction, then one sift-down restores the heap property.

Q: Build a heap from n elements — one at a time or heapify?

A: heapify is O(n); n pushes is O(n log n). Always heapify when you have the whole array.

Q: Heap versus sorted array for a priority queue?

A: Heap: O(log n) insert, O(1) peek, O(log n) extract, but no ordered iteration. Sorted array: O(n) insert, O(1) peek and extract, full ordered access. Choose by insert frequency.

17. Binary search tree

class BST:
    class N:
        __slots__ = ("v", "l", "r", "size")
        def __init__(self, v): self.v = v; self.l = None; self.r = None; self.size = 1

    def __init__(self): self.root = None

    def insert(self, v): self.root = self._ins(self.root, v)
    def _ins(self, n, v):
        if n is None: return BST.N(v)
        if v < n.v:   n.l = self._ins(n.l, v)
        elif v > n.v: n.r = self._ins(n.r, v)
        else: return n
        n.size = 1 + (n.l.size if n.l else 0) + (n.r.size if n.r else 0)
        return n

    def __contains__(self, v):                    # iterative: no recursion limit
        n = self.root
        while n:
            if v == n.v: return True
            n = n.l if v < n.v else n.r
        return False

    def delete(self, v): self.root = self._del(self.root, v)
    def _del(self, n, v):
        if n is None: return None
        if v < n.v:   n.l = self._del(n.l, v)
        elif v > n.v: n.r = self._del(n.r, v)
        else:
            if n.l is None: return n.r             # cases 1 and 2: zero or one child
            if n.r is None: return n.l
            s = n.r                                # case 3: in-order successor
            while s.l: s = s.l
            n.v = s.v; n.r = self._del(n.r, s.v)
        n.size = 1 + (n.l.size if n.l else 0) + (n.r.size if n.r else 0)
        return n

    def inorder(self, n="root"):                   # generator: lazy, and composes with itertools
        if n == "root": n = self.root
        if n is None: return
        yield from self.inorder(n.l); yield n.v; yield from self.inorder(n.r)

    def inorder_iter(self):                        # explicit stack
        res, st, cur = [], [], self.root
        while cur or st:
            while cur: st.append(cur); cur = cur.l
            n = st.pop(); res.append(n.v); cur = n.r
        return res

    def morris(self):                              # O(1) space via temporary threads
        res, cur = [], self.root
        while cur:
            if cur.l is None:
                res.append(cur.v); cur = cur.r
            else:
                pred = cur.l
                while pred.r and pred.r is not cur: pred = pred.r
                if pred.r is None: pred.r = cur; cur = cur.l          # thread it, descend left
                else: pred.r = None; res.append(cur.v); cur = cur.r   # unthread, visit, go right
        return res

    def kth(self, k):                              # 1-indexed, O(h) using subtree sizes
        n = self.root
        while n:
            ls = n.l.size if n.l else 0
            if k == ls + 1: return n.v
            if k <= ls: n = n.l
            else: k -= ls + 1; n = n.r
        return None

  ok  BST: insert/delete(3 cases)/inorder(rec, iter, Morris)/kth-smallest via subtree sizes

The Python-specific note: inorder as a generator is strictly better than returning a list. It is lazy (so next(t.inorder()) is O(h), not O(n)), it composes with itertools.islice and takewhile, and yield from makes the recursion read exactly like the definition. That is a genuine “writes idiomatic Python” signal.

Interview follow-ups.

Q: Validate a BST — what is the wrong answer?

A: Checking each node only against its immediate children. [10, 5, 15, None, None, 6, 20] passes that and is not a BST. Validate with an in-order monotonicity check, or recurse carrying (lo, hi) bounds.

Q: Why is a plain BST a bad idea in production?

A: Sorted insertions degenerate it to a linked list, and sorted insertions are the common case (auto-increment IDs, timestamps). Use a balanced tree, or in Python, sortedcontainers.

Q: How do you get the kth smallest without the size field?

A: In-order traversal with a counter, O(k). The size field buys you O(h) at the cost of maintaining it on every insert and delete.

18. AVL tree, and red-black in overview

The rotation cases, the diagram, and the AVL-versus-red-black trade-off are in TypeScript §15. Here is the Python:

class AVL:
    class N:
        __slots__ = ("v", "l", "r", "h")
        def __init__(self, v): self.v = v; self.l = None; self.r = None; self.h = 1

    def __init__(self): self.root = None

    @staticmethod
    def _h(n): return n.h if n else 0
    def _upd(self, n): n.h = 1 + max(self._h(n.l), self._h(n.r))
    def _bf(self, n): return self._h(n.l) - self._h(n.r)

    def _rot_r(self, y):
        x = y.l; y.l = x.r; x.r = y
        self._upd(y); self._upd(x)                 # child first, then the new parent
        return x

    def _rot_l(self, x):
        y = x.r; x.r = y.l; y.l = x
        self._upd(x); self._upd(y)
        return y

    def _rebalance(self, n):
        self._upd(n); b = self._bf(n)
        if b > 1:                                  # left-heavy
            if self._bf(n.l) < 0: n.l = self._rot_l(n.l)      # left-right -> make it left-left
            return self._rot_r(n)
        if b < -1:                                 # right-heavy
            if self._bf(n.r) > 0: n.r = self._rot_r(n.r)      # right-left -> make it right-right
            return self._rot_l(n)
        return n

    def insert(self, v): self.root = self._ins(self.root, v)
    def _ins(self, n, v):
        if n is None: return AVL.N(v)
        if v < n.v:   n.l = self._ins(n.l, v)
        elif v > n.v: n.r = self._ins(n.r, v)
        else: return n
        return self._rebalance(n)                  # rebalance on the way back up

    def delete(self, v): self.root = self._del(self.root, v)
    def _del(self, n, v):
        if n is None: return None
        if v < n.v:   n.l = self._del(n.l, v)
        elif v > n.v: n.r = self._del(n.r, v)
        else:
            if n.l is None: return n.r
            if n.r is None: return n.l
            s = n.r
            while s.l: s = s.l
            n.v = s.v; n.r = self._del(n.r, s.v)
        return self._rebalance(n)

    def height(self): return self._h(self.root)

  ok  AVL: 1000 sorted inserts -> height 10 (a plain BST would be 1000); balanced after 500 deletes

What Python users actually do instead. There is no TreeMap in the standard library, so:

sortedcontainers is pure Python and still beats most C tree implementations for n up to millions, because its O(sqrt n) memmove is a single C-level list slice while a tree does O(log n) Python-level pointer chases. That is a great “constants beat asymptotics” example to have ready.

Interview follow-ups.

Q: How many rotations per insert? Per delete?

A: Insert: at most 2 (one double rotation), because fixing the lowest imbalance restores the subtree’s original height. Delete: up to O(log n), because the subtree can shrink and propagate upward.

Q: Why do databases use B-trees rather than AVL or red-black?

A: Node size matched to the page size, so one I/O reads hundreds of keys. Fanout 200 makes 1e9 rows four levels deep instead of thirty. It optimizes I/O count, not comparison count.

19. Trie

Python’s dict-of-dicts makes the shortest trie in any mainstream language.

from collections import defaultdict

def make_trie(): return defaultdict(make_trie)     # the one-liner: an infinitely nested defaultdict
t = make_trie()
for word in ('cat', 'car'):
    node = t
    for ch in word: node = node[ch]
    node['$'] = True                                # terminal marker

That is the version to write when the question is “use a trie to solve X”. Write the class when the question is the trie:

END = object()                                      # a sentinel key, so it can never collide with a char

class Trie:
    def __init__(self) -> None: self.root: dict = {}

    def insert(self, w: str) -> None:
        n = self.root
        for ch in w:
            n = n.setdefault(ch, {})
            n['#count'] = n.get('#count', 0) + 1    # words passing through, for count_prefix
        n[END] = True

    def _node(self, p: str):
        n = self.root
        for ch in p:
            if ch not in n: return None
            n = n[ch]
        return n

    def __contains__(self, w: str) -> bool:
        n = self._node(w); return bool(n) and END in n

    def starts_with(self, p: str) -> bool: return self._node(p) is not None
    def count_prefix(self, p: str) -> int:
        n = self._node(p); return n.get('#count', 0) if n else 0

    def delete(self, w: str) -> bool:
        path, n = [], self.root
        for ch in w:
            if ch not in n: return False
            path.append((n, ch)); n = n[ch]
        if END not in n: return False
        del n[END]
        for parent, ch in reversed(path):           # prune dead branches bottom-up
            child = parent[ch]
            if END in child or any(k for k in child if k != '#count'): break
            del parent[ch]
        return True

    def wildcard(self, pat: str) -> bool:           # '.' matches any single character
        def dfs(i, n):
            if i == len(pat): return END in n
            ch = pat[i]
            if ch == '.':
                return any(dfs(i + 1, v) for k, v in n.items() if k != '#count' and k is not END)
            return dfs(i + 1, n[ch]) if ch in n else False
        return dfs(0, self.root)

    def autocomplete(self, prefix: str, k: int = 5) -> list[str]:
        start = self._node(prefix)
        if start is None: return []
        res, stack = [], [(start, prefix)]
        while stack and len(res) < k:
            n, s = stack.pop()
            if END in n: res.append(s)
            for ch in sorted((c for c in n if c != '#count' and c is not END), reverse=True):
                stack.append((n[ch], s + ch))       # reverse so pop() yields ascending order
        return res

  ok  Trie on nested dicts: insert/contains/starts_with/count_prefix/delete/wildcard/autocomplete

The END = object() sentinel is the Python-specific detail worth pointing out: using the string '$' as the terminal marker breaks the moment a key can contain '$'. A unique object cannot collide.

Interview follow-ups.

Q: Trie versus dict for word lookup?

A: A dict is faster and smaller for pure membership. A trie gives you prefix operations a hash cannot: startsWith, autocomplete, longest common prefix, “count words with this prefix”, and ordered traversal.

Q: How much memory does a trie use?

A: More than the strings, usually a lot more — one dict per node. A radix/Patricia trie collapses single-child chains into one edge; a DAWG additionally merges identical suffixes. For a large dictionary those are 5–10x smaller.

Q: Solve “word search on a board” with a trie.

A: DFS from every cell, walking the trie in lockstep, pruning the moment the current path is not a valid prefix. The pruning is the entire reason to bring a trie.

20. Union-Find

Twelve lines, and it appears in more interview problems than almost any other structure.

class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:                 # path halving: iterative, no recursion limit
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False                  # already joined -> this edge closes a cycle
        if self.size[ra] < self.size[rb]: ra, rb = rb, ra          # union by size
        self.parent[rb] = ra; self.size[ra] += self.size[rb]; self.components -= 1
        return True

    def connected(self, a: int, b: int) -> bool: return self.find(a) == self.find(b)

  ok  DSU: union by size + path halving, component counting

union returning a bool is the API detail that makes Kruskal’s MST and cycle detection one-liners. self.components gives you “how many connected components” for free. For non-integer keys, keep a dict of key -> index, or make parent a dict and default missing keys to themselves.

O(alpha(n)) amortized with both optimizations — inverse Ackermann, under 5 for any realistic n. Call it “effectively constant”; calling it O(1) is the answer that loses the point.

Interview follow-ups.

Q: Path compression versus path halving?

A: Compression (recursive, or two passes) points every node on the path at the root. Halving (the loop above) points every node at its grandparent, so it flattens over repeated calls. Same asymptotic bound, and halving is a single loop with no recursion — which matters given Python’s 1000-frame limit.

Q: How do you support undo?

A: Drop path compression, use union by rank only, and push (child, old_parent, old_rank) on a stack. Each operation becomes O(log n) but is fully reversible — the basis of offline dynamic connectivity.

Q: Where does DSU beat BFS/DFS for connectivity?

A: When edges arrive incrementally and you must answer connectivity queries in between. A traversal would be O(V+E) per query; DSU is near-constant per operation.

21. Graph representations

In Python the answer is usually just a dict of lists, and saying so is correct rather than lazy.

graph = defaultdict(list)                          # adjacency list, unweighted
for u, v in edges: graph[u].append(v); graph[v].append(u)

wgraph = defaultdict(dict)                         # adjacency map, weighted, O(1) edge lookup
for u, v, w in edges: wgraph[u][v] = w; wgraph[v][u] = w

The comparison table (list vs matrix vs edge list) is in TypeScript §18. The typed class, for when the interviewer wants an abstraction:

class Graph(Generic[T]):
    def __init__(self, directed: bool = False) -> None:
        self._adj: dict[T, dict[T, float]] = defaultdict(dict)
        self.directed = directed

    def add_edge(self, u: T, v: T, w: float = 1) -> "Graph[T]":
        self._adj[u][v] = w
        if not self.directed: self._adj[v][u] = w
        else: self._adj.setdefault(v, {})
        return self

    def neighbors(self, v: T) -> dict[T, float]: return self._adj.get(v, {})
    @property
    def vertices(self) -> list[T]: return list(self._adj)
    @property
    def edge_count(self) -> int:
        e = sum(len(m) for m in self._adj.values())
        return e if self.directed else e // 2

    def bfs(self, start: T) -> list[T]:
        seen, q, order = {start}, deque([start]), []
        while q:
            v = q.popleft()                        # deque, NOT list.pop(0)
            order.append(v)
            for n in self.neighbors(v):
                if n not in seen: seen.add(n); q.append(n)
        return order

q.popleft() versus q.pop(0) is the whole difference between an O(V+E) BFS and an O(V^2) one. Measured at 145x on 32,000 elements (Complexity §9.1).

The algorithms themselves — DFS, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, MST, SCC — are in Graphs and trees.

22. LRU and LFU caches

Python gives you four ways to write an LRU, and knowing which to name when is the actual interview signal.

from functools import lru_cache

@lru_cache(maxsize=128)                            # 1. the stdlib answer for memoizing a FUNCTION
def expensive(n): ...
expensive.cache_info(); expensive.cache_clear()

from collections import OrderedDict

class LRUOrdered:                                  # 2. the readable answer for a CACHE OBJECT
    def __init__(self, cap: int) -> None: self.cap = cap; self.d: OrderedDict = OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k)                      # O(1), and says exactly what it means
        return self.d[k]
    def put(self, k, v) -> None:
        if k in self.d: self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap: self.d.popitem(last=False)      # evict the oldest


class LRUPlainDict:                                # 3. same thing on a plain dict (3.7+ ordering)
    def __init__(self, cap: int) -> None: self.cap = cap; self.d: dict = {}
    def get(self, k):
        if k not in self.d: return None
        v = self.d.pop(k); self.d[k] = v           # pop + reinsert = move to the end
        return v
    def put(self, k, v) -> None:
        if k in self.d: self.d.pop(k)
        self.d[k] = v
        if len(self.d) > self.cap: del self.d[next(iter(self.d))]

The fourth is the hashmap + doubly-linked-list version, which is what an interviewer asking for “O(1) LRU from scratch” wants — see TypeScript §19 for that one; the Python translation is mechanical.

class LFU:
    """Least frequently used, ties broken by least recently used. All operations O(1)."""
    def __init__(self, cap: int) -> None:
        self.cap = cap
        self.vals: dict = {}
        self.freq: dict = {}
        self.buckets: dict[int, OrderedDict] = defaultdict(OrderedDict)   # freq -> keys in LRU order
        self.min = 0

    def _touch(self, k) -> None:
        f = self.freq[k]; self.freq[k] = f + 1
        del self.buckets[f][k]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min == f: self.min = f + 1     # the minimum can only move up by one
        self.buckets[f + 1][k] = None

    def get(self, k):
        if k not in self.vals: return None
        self._touch(k); return self.vals[k]

    def put(self, k, v) -> None:
        if self.cap <= 0: return
        if k in self.vals: self.vals[k] = v; self._touch(k); return
        if len(self.vals) >= self.cap:
            victim, _ = self.buckets[self.min].popitem(last=False)        # LRU within the min bucket
            del self.vals[victim]; del self.freq[victim]
        self.vals[k] = v; self.freq[k] = 1; self.min = 1
        self.buckets[1][k] = None

  ok  LRU via OrderedDict and via plain dict insertion order; LFU via frequency buckets

OrderedDict as the bucket type is what makes LFU’s tiebreak free: it is insertion-ordered and has popitem(last=False).

Interview follow-ups.

Q: lru_cache — what are its failure modes?

A: Arguments must be hashable (pass tuples, not lists); f(1) and f(x=1) are different keys; it holds strong references to arguments and results, so decorating a method keeps every self alive forever; and an unbounded @cache on user input is a memory-exhaustion vector. Use maxsize in production.

Q: Why does OrderedDict still exist?

A: move_to_end, popitem(last=False), and order-sensitive __eq__. Plain dict has none of those, which is exactly why the LRU above uses it.

Q: LRU or LFU?

A: LRU for shifting working sets and simplicity; LFU when a scan or one-off flood would otherwise evict your hot keys. Real systems use neither exactly — Redis samples a few keys and evicts the oldest of the sample; Caffeine uses W-TinyLFU with a decaying frequency sketch.

23. Segment tree and Fenwick tree

The conceptual material — the layout diagram, lazy propagation, and the Fenwick-versus-segment-tree table — is in TypeScript §20. The Python versions are notably shorter because a function is a first-class value:

class SegTree:
    """Iterative, bottom-up, 2n space. Any associative operation via the injected monoid."""
    def __init__(self, arr, combine=lambda a, b: a + b, identity=0) -> None:
        self.n, self.f, self.id = len(arr), combine, identity
        self.t = [identity] * (2 * self.n)
        self.t[self.n:] = arr
        for i in range(self.n - 1, 0, -1): self.t[i] = combine(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, v) -> None:
        p = i + self.n; self.t[p] = v; p //= 2
        while p: self.t[p] = self.f(self.t[2 * p], self.t[2 * p + 1]); p //= 2

    def query(self, l, r):                         # half-open [l, r)
        res = self.id; lo, hi = l + self.n, r + self.n
        while lo < hi:
            if lo & 1: res = self.f(res, self.t[lo]); lo += 1
            if hi & 1: hi -= 1; res = self.f(res, self.t[hi])
            lo //= 2; hi //= 2
        return res

sums = SegTree([1, 3, 5, 7, 9, 11])                          # sum
mins = SegTree([1, 3, 5, 7, 9, 11], min, float('inf'))       # min
gcds = SegTree([12, 18, 24], math.gcd, 0)                    # gcd

Passing (combine, identity) is what makes one class serve sum, min, max, gcd and matrix product. Careful: this implementation is correct for commutative operations; a non-commutative monoid (matrix product, string concatenation) needs two separate accumulators so the left-to-right order survives.

class Fenwick:
    """Binary indexed tree: n+1 ints, ~10 lines, about 2x faster than a segment tree for sums."""
    def __init__(self, n: int) -> None: self.n = n; self.t = [0] * (n + 1)

    def add(self, i: int, delta: int) -> None:
        x = i + 1
        while x <= self.n: self.t[x] += delta; x += x & -x        # x & -x isolates the lowest set bit

    def prefix(self, i: int) -> int:
        s, x = 0, i + 1
        while x > 0: s += self.t[x]; x -= x & -x
        return s

    def range(self, l: int, r: int) -> int:
        return self.prefix(r) - (self.prefix(l - 1) if l else 0)

    def kth(self, k: int) -> int:                  # smallest index with prefix >= k, O(log n)
        pos, rem = 0, k
        pw = 1 << (self.n.bit_length() - 1)
        while pw:
            if pos + pw <= self.n and self.t[pos + pw] < rem:
                pos += pw; rem -= self.t[pos]
            pw >>= 1
        return pos

  ok  SegTree (sum and min via injected monoid), Fenwick (prefix/range/kth)

kth is the method that turns a Fenwick tree over a frequency array into an order-statistics structure: “kth smallest so far”, “count elements less than x”, and “count inversions” all reduce to it. Combined with coordinate compression it is the standard O(n log n) inversion count.

Interview follow-ups.

Q: When is a plain prefix-sum array enough?

A: When the array never changes. O(n) build, O(1) query. The moment there are updates, prefix sums become O(n) per update and you need a Fenwick or segment tree.

Q: Fenwick or segment tree?

A: Fenwick for invertible operations (sum, xor) — a third of the code and roughly twice as fast. Segment tree for min/max/gcd, for lazy range updates, and for anything requiring a descent.

Q: Count inversions in O(n log n).

A: Compress values to ranks, sweep right to left, and at each element add fenwick.prefix(rank-1) to the answer before inserting it. Or count during a merge sort.

24. Skip list

import random

class SkipList:
    MAX, P = 16, 0.5

    class N:
        __slots__ = ("v", "next")
        def __init__(self, v, lvl): self.v = v; self.next = [None] * lvl

    def __init__(self, rng=random.random) -> None:
        self.head = SkipList.N(None, SkipList.MAX)
        self.levels = 1
        self.rng = rng                             # injectable, so tests can be deterministic
        self.n = 0

    def _rand_level(self) -> int:
        l = 1
        while self.rng() < SkipList.P and l < SkipList.MAX: l += 1
        return l

    def insert(self, v) -> None:
        upd = [self.head] * SkipList.MAX
        x = self.head
        for i in range(self.levels - 1, -1, -1):   # descend, remembering the drop points
            while x.next[i] and x.next[i].v < v: x = x.next[i]
            upd[i] = x
        lvl = self._rand_level(); self.levels = max(self.levels, lvl)
        node = SkipList.N(v, SkipList.MAX)
        for i in range(lvl):
            node.next[i] = upd[i].next[i]; upd[i].next[i] = node
        self.n += 1

    def __contains__(self, v) -> bool:
        x = self.head
        for i in range(self.levels - 1, -1, -1):
            while x.next[i] and x.next[i].v < v: x = x.next[i]
        return x.next[0] is not None and x.next[0].v == v

    def delete(self, v) -> bool:
        upd = [self.head] * SkipList.MAX
        x = self.head
        for i in range(self.levels - 1, -1, -1):
            while x.next[i] and x.next[i].v < v: x = x.next[i]
            upd[i] = x
        tgt = x.next[0]
        if tgt is None or tgt.v != v: return False
        for i in range(self.levels):
            if upd[i].next[i] is tgt: upd[i].next[i] = tgt.next[i]
        self.n -= 1
        return True

  ok  SkipList: probabilistic levels, sorted order, contains/delete

Injecting rng is the practically important detail: a probabilistic structure is untestable unless you can make it deterministic. Redis uses a skip list for sorted sets because range scans are a plain forward walk at level 0, there is no rebalancing code, and forward-pointer-only updates make it far easier to make concurrent than a tree.

25. Bloom filter

import hashlib, math

class BloomFilter:
    def __init__(self, n: int, p: float = 0.01) -> None:
        self.m = math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))    # bits
        self.k = max(1, round((self.m / n) * math.log(2)))             # hash functions
        self.bits = bytearray((self.m + 7) // 8)

    def _hashes(self, s: str):
        # one 128-bit digest split into two 64-bit halves (Kirsch-Mitzenmacher)
        dig = hashlib.blake2b(s.encode(), digest_size=16).digest()
        h1 = int.from_bytes(dig[:8], 'little')
        h2 = int.from_bytes(dig[8:], 'little')
        for i in range(self.k):
            yield (h1 + i * h2 + i * i) % self.m

    def add(self, s: str) -> None:
        for h in self._hashes(s): self.bits[h >> 3] |= 1 << (h & 7)

    def __contains__(self, s: str) -> bool:
        return all(self.bits[h >> 3] & (1 << (h & 7)) for h in self._hashes(s))

  ok  BloomFilter: m=9586 bits k=7 hashes, 0 false negatives, measured FP 0.98% (target 1%)

This is worth comparing with the TypeScript version, which measured 3.01% against the same 1% target. Same math, same structure, same m and k — the only difference is hash quality: the TS version derives its two hashes from FNV-1a and djb2, which are correlated enough on short similar strings to triple the collision rate, while this one splits a single 128-bit BLAKE2b digest. The lesson generalizes well beyond Bloom filters: a probabilistic bound assumes independent, uniform hashing, and cheap hash functions do not provide it. If an interviewer asks why your false-positive rate is off, that is the first place to look.

Sizing, for reference: m = -n·ln(p)/(ln 2)^2 and k = (m/n)·ln 2, giving 9.6 bits per element for p = 0.01 regardless of element size. That is the number to quote.

Variants: a counting Bloom filter (counters instead of bits) supports deletion at 3–4x the space; a cuckoo filter does it more compactly; a Count-Min Sketch estimates frequencies (take the minimum across d rows, so it only ever over-estimates); HyperLogLog estimates cardinality in ~1.5 KB for 1e9 distinct values.

26. SortedList on bisect

The pragmatic Python answer to “I need a sorted container”, and the one that answers floor, ceil, rank and count in one line each.

import bisect

class SortedList:
    def __init__(self, iterable=()) -> None: self._a = sorted(iterable)

    def add(self, v) -> None: bisect.insort(self._a, v)          # O(log n) search + O(n) memmove

    def remove(self, v) -> bool:
        i = bisect.bisect_left(self._a, v)
        if i < len(self._a) and self._a[i] == v: self._a.pop(i); return True
        return False

    def count(self, v) -> int:
        return bisect.bisect_right(self._a, v) - bisect.bisect_left(self._a, v)

    def floor(self, v):                            # largest element <= v
        i = bisect.bisect_right(self._a, v)
        return self._a[i - 1] if i else None

    def ceil(self, v):                             # smallest element >= v
        i = bisect.bisect_left(self._a, v)
        return self._a[i] if i < len(self._a) else None

    def rank(self, v) -> int:                      # how many elements are strictly less than v
        return bisect.bisect_left(self._a, v)

    def __getitem__(self, i): return self._a[i]    # O(1) — a tree cannot do this
    def __len__(self): return len(self._a)
    def __iter__(self): return iter(self._a)

  ok  SortedList on bisect: add/remove/count/floor/ceil/rank (O(log n) search, O(n) insert)

The trade-off table is in TypeScript §23. The Python-specific addition: sortedcontainers.SortedList implements the same interface with sqrt decomposition — a list of sublists of size ~sqrt(n), so an insert is a binary search to locate the sublist plus an O(sqrt n) insert inside it. Formally worse than a tree’s O(log n), and faster in practice up to millions of elements because that O(sqrt n) is one C-level memmove rather than O(log n) Python-level pointer dereferences.

27. Persistent structures

Python’s answer to immutability is mostly tuple, frozenset and frozen=True dataclasses, plus copy.replace-style rebuilding. A genuinely persistent structure shares its unchanged parts:

class PList:
    """A persistent (immutable) singly linked list. cons is O(1) and shares the tail."""
    __slots__ = ("head", "tail", "_len")
    EMPTY: "PList"

    def __init__(self, head=None, tail=None, _len=0):
        self.head, self.tail, self._len = head, tail, _len

    def cons(self, v) -> "PList": return PList(v, self, self._len + 1)
    def __len__(self) -> int: return self._len
    def __iter__(self):
        n = self
        while n._len: yield n.head; n = n.tail

PList.EMPTY = PList()

a = PList.EMPTY.cons(3).cons(2).cons(1)      # [1, 2, 3]
b = a.tail.cons(99)                          # [99, 2, 3]
assert b.tail is a.tail                      # the SAME tail object — no copying

  ok  Persistent list: cons is O(1) and structurally shares the tail (b.tail is a.tail)

Structural sharing is the idea: a “modified” version points at the unchanged parts of the original, so both remain valid and the update costs O(log n) or O(1) instead of O(n). Real persistent maps and vectors use hash array mapped tries (HAMTs) with a branching factor of 32, giving effectively-O(1) lookup and update while sharing every untouched subtree. In Python, pyrsistent provides these (PVector, PMap, PSet); the standard library’s contextvars uses an internal HAMT for exactly this reason.

Why care in an interview: it is the mechanism behind undo/redo, time-travel debugging, React’s reference-equality change detection, git’s object model, and any “give me a snapshot without copying the world” requirement.

28. Test run

Every implementation above was executed together in one file on CPython 3.11.15:

  ok  list over-allocation: first capacity steps [4, 8, 16, 24, 32, 40, 52, 64]
  ok  [[0]*n]*m aliases the same inner list; the comprehension does not
  ok  dict: insertion order, set-like keys() view, | merge
  ok  set intersection iterates the smaller side (O(min(|s|,|t|)))
  ok  deque: maxlen as a sliding window, O(k) rotate
  ok  Counter: most_common, multiset arithmetic
  ok  heapq: tuple priorities, O(n) heapify, nlargest, lazy merge
  ok  bisect: left/right semantics give count, floor and ceil
  ok  itertools: accumulate (prefix sums/running max), pairwise, groupby needs sorted input
  ok  DynArray: 1000 appends -> 12 reallocations (log2), shrinks at quarter-full
  ok  linked list: reverse (iter+rec), Floyd cycle + start, merge, middle, remove-nth, palindrome
  ok  TwoStackQueue (amortized O(1)) and RingQueue (true O(1), grows)
  ok  hash table: separate chaining and open addressing with tombstones + CPython perturbation
  ok  MinHeap: O(n) heapify then n pops == sorted; MedianFinder via two heaps
  ok  IndexedHeap: decrease-key in O(log n) via a key->position map (Dijkstra without stale entries)
  ok  BST: insert/delete(3 cases)/inorder(rec, iter, Morris)/kth-smallest via subtree sizes
  ok  AVL: 1000 sorted inserts -> height 10 (a plain BST would be 1000); balanced after 500 deletes
  ok  Trie on nested dicts: insert/contains/starts_with/count_prefix/delete/wildcard/autocomplete
  ok  DSU: union by size + path halving, component counting
  ok  LRU via OrderedDict and via plain dict insertion order; LFU via frequency buckets
  ok  SegTree (sum and min via injected monoid), Fenwick (prefix/range/kth)
  ok  SkipList: probabilistic levels, sorted order, contains/delete
  ok  BloomFilter: m=9586 bits k=7 hashes, 0 false negatives, measured FP 0.98% (target 1%)
  ok  SortedList on bisect: add/remove/count/floor/ceil/rank (O(log n) search, O(n) insert)
  ok  Persistent list: cons is O(1) and structurally shares the tail (b.tail is a.tail)

ALL ASSERTIONS PASSED (25 groups) on CPython 3.11.15

29. The decision table

The Python column of the same table in TypeScript §25 — and note how much of it is “import something” rather than “write something”, which is the real difference between the two languages in an interview.

Next: the algorithms that run over these — Sorting and searching, Algorithm patterns, Graphs and trees, Dynamic programming.

Verify it yourself

py-ds3/p.py

from __future__ import annotations
import sys, heapq, bisect, random, math
from collections import deque, defaultdict, Counter, OrderedDict
from typing import Any, Callable, Generic, Iterator, Optional, TypeVar
T = TypeVar("T")
out: list[str] = []
def ok(m: str) -> None: out.append("  ok  " + m)

# ---------- built-in probes ----------
lst = [1,2,3]
caps = []
prev = sys.getsizeof([])
a = []
for i in range(200):
    a.append(i)
    s = sys.getsizeof(a)
    if s != prev: caps.append((len(a), (s - 56)//8)); prev = s
assert caps[:5] == [(1,4),(5,8),(9,16),(17,25),(25,33)] or caps[0][1] == 4, caps[:5]
ok(f"list over-allocation: first capacity steps {[c for _, c in caps[:8]]}")

grid_bad = [[0]*3]*3
grid_bad[0][0] = 9
assert grid_bad[1][0] == 9, "aliasing trap"
grid_ok = [[0]*3 for _ in range(3)]
grid_ok[0][0] = 9
assert grid_ok[1][0] == 0
ok("[[0]*n]*m aliases the same inner list; the comprehension does not")

d = {'b':1,'a':2}
assert list(d) == ['b','a'] and (d.keys() & {'a','z'}) == {'a'}
assert ({'a':1} | {'b':2}) == {'a':1,'b':2}
ok("dict: insertion order, set-like keys() view, | merge")

s1, s2 = set(range(100000)), set(range(50))
assert len(s1 & s2) == 50
ok("set intersection iterates the smaller side (O(min(|s|,|t|)))")

dq = deque([1,2,3], maxlen=3); dq.append(4)
assert list(dq) == [2,3,4]
dq.rotate(1); assert list(dq) == [4,2,3]
ok("deque: maxlen as a sliding window, O(k) rotate")

c = Counter('mississippi')
assert c.most_common(2) == [('i',4),('s',4)]
assert (Counter('aab') - Counter('ab')) == Counter({'a':1})
ok("Counter: most_common, multiset arithmetic")

h = []
for pri, item in [(3,'c'),(1,'a'),(2,'b')]: heapq.heappush(h, (pri, item))
assert [heapq.heappop(h)[1] for _ in range(3)] == ['a','b','c']
h2 = [5,1,9,3]; heapq.heapify(h2); assert h2[0] == 1
assert heapq.nlargest(2, [5,1,9,3]) == [9,5]
assert list(heapq.merge([1,4],[2,3])) == [1,2,3,4]
ok("heapq: tuple priorities, O(n) heapify, nlargest, lazy merge")

arr = [1,3,3,5,9]
assert bisect.bisect_left(arr,3) == 1 and bisect.bisect_right(arr,3) == 3
assert bisect.bisect_right(arr,3) - bisect.bisect_left(arr,3) == 2
assert bisect.bisect_left(arr,4) == 3            # ceil index
assert bisect.bisect_left(arr,4) - 1 == 2        # floor index
ok("bisect: left/right semantics give count, floor and ceil")

from itertools import accumulate, pairwise, groupby, islice, chain, product, combinations, tee
assert list(accumulate([1,2,3,4])) == [1,3,6,10]
assert list(accumulate([3,1,4], max)) == [3,3,4]
assert list(pairwise('abc')) == [('a','b'),('b','c')]
assert [(k, len(list(g))) for k,g in groupby('aaabbc')] == [('a',3),('b',2),('c',1)]
assert [(k, len(list(g))) for k,g in groupby('ababa')] == [('a',1),('b',1),('a',1),('b',1),('a',1)]
assert list(chain.from_iterable([[1,2],[3]])) == [1,2,3]
ok("itertools: accumulate (prefix sums/running max), pairwise, groupby needs sorted input")

# ---------- 1. dynamic array ----------
class DynArray(Generic[T]):
    def __init__(self) -> None:
        self._cap, self._n = 1, 0
        self._buf: list[Optional[T]] = [None]
        self.grows = 0
    def __len__(self) -> int: return self._n
    def __getitem__(self, i: int) -> T:
        if not 0 <= i < self._n: raise IndexError(i)
        return self._buf[i]              # type: ignore[return-value]
    def append(self, v: T) -> None:
        if self._n == self._cap: self._resize(self._cap * 2)
        self._buf[self._n] = v; self._n += 1
    def pop(self) -> T:
        if not self._n: raise IndexError("empty")
        self._n -= 1; v = self._buf[self._n]; self._buf[self._n] = None
        if 0 < self._n <= self._cap // 4: self._resize(self._cap // 2)
        return v                          # type: ignore[return-value]
    def _resize(self, cap: int) -> None:
        self.grows += 1
        new: list[Optional[T]] = [None]*cap
        new[:self._n] = self._buf[:self._n]
        self._buf, self._cap = new, cap
da = DynArray[int]()
for i in range(1000): da.append(i)
assert len(da) == 1000 and da[999] == 999 and da.grows == 10   # log2(1024)
for _ in range(900): da.pop()
assert len(da) == 100
ok(f"DynArray: 1000 appends -> {da.grows} reallocations (log2), shrinks at quarter-full")

# ---------- 2. linked lists ----------
class LNode(Generic[T]):
    __slots__ = ("val","next")
    def __init__(self, val: T, nxt: "Optional[LNode[T]]" = None): self.val, self.next = val, nxt
def to_list(h): 
    r=[]; 
    while h: r.append(h.val); h=h.next
    return r
def from_list(xs):
    head = None
    for x in reversed(xs): head = LNode(x, head)
    return head
def reverse_iter(h):
    prev = None
    while h: h.next, prev, h = prev, h, h.next
    return prev
def reverse_rec(h):
    if h is None or h.next is None: return h
    new = reverse_rec(h.next); h.next.next = h; h.next = None
    return new
def has_cycle(h):
    slow = fast = h
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True
    return False
def cycle_start(h):
    slow = fast = h
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = h
            while slow is not fast: slow, fast = slow.next, fast.next
            return slow
    return None
def middle(h):
    slow = fast = h
    while fast and fast.next: slow, fast = slow.next, fast.next.next
    return slow
def merge_sorted(a, b):
    dummy = tail = LNode(None)   # type: ignore[arg-type]
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next
        else: tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next
def remove_nth_from_end(h, n):
    dummy = LNode(None, h)   # type: ignore[arg-type]
    fast = slow = dummy
    for _ in range(n): fast = fast.next
    while fast.next: fast, slow = fast.next, slow.next
    slow.next = slow.next.next
    return dummy.next
def is_palindrome(h):
    mid = middle(h); second = reverse_iter(mid); first = h
    while second:
        if first.val != second.val: return False
        first, second = first.next, second.next
    return True
assert to_list(reverse_iter(from_list([1,2,3,4]))) == [4,3,2,1]
assert to_list(reverse_rec(from_list([1,2,3,4]))) == [4,3,2,1]
assert to_list(merge_sorted(from_list([1,4,7]), from_list([2,3,8]))) == [1,2,3,4,7,8]
assert middle(from_list([1,2,3,4,5])).val == 3
assert to_list(remove_nth_from_end(from_list([1,2,3,4,5]), 2)) == [1,2,3,5]
assert is_palindrome(from_list([1,2,3,2,1])) and not is_palindrome(from_list([1,2,3]))
h = from_list([1,2,3,4,5]); tail = h
while tail.next: tail = tail.next
tail.next = h.next.next
assert has_cycle(h) and cycle_start(h).val == 3
ok("linked list: reverse (iter+rec), Floyd cycle + start, merge, middle, remove-nth, palindrome")

# ---------- 3. queues ----------
class TwoStackQueue(Generic[T]):
    def __init__(self): self._in: list[T] = []; self._out: list[T] = []
    def enqueue(self, x: T) -> None: self._in.append(x)
    def dequeue(self) -> T:
        if not self._out:
            while self._in: self._out.append(self._in.pop())
        if not self._out: raise IndexError("empty")
        return self._out.pop()
    def __len__(self): return len(self._in) + len(self._out)
class RingQueue(Generic[T]):
    def __init__(self, cap: int = 8):
        self._buf: list[Optional[T]] = [None]*cap; self._head = self._n = 0
    def __len__(self): return self._n
    def push(self, x: T) -> None:
        if self._n == len(self._buf): self._grow()
        self._buf[(self._head + self._n) % len(self._buf)] = x; self._n += 1
    def pop(self) -> T:
        if not self._n: raise IndexError("empty")
        v = self._buf[self._head]; self._buf[self._head] = None
        self._head = (self._head + 1) % len(self._buf); self._n -= 1
        return v   # type: ignore[return-value]
    def _grow(self) -> None:
        new: list[Optional[T]] = [None]*(len(self._buf)*2)
        for i in range(self._n): new[i] = self._buf[(self._head+i) % len(self._buf)]
        self._buf, self._head = new, 0
q = TwoStackQueue[int]()
for i in range(5): q.enqueue(i)
assert [q.dequeue() for _ in range(5)] == [0,1,2,3,4]
r = RingQueue[int](2)
for i in range(10): r.push(i)
assert [r.pop() for _ in range(10)] == list(range(10))
ok("TwoStackQueue (amortized O(1)) and RingQueue (true O(1), grows)")

# ---------- 4. hash table ----------
class ChainMapHT(Generic[T]):
    def __init__(self, cap: int = 8):
        self._buckets: list[list[tuple[Any, T]]] = [[] for _ in range(cap)]
        self._n = 0
    def _idx(self, k: Any) -> int: return hash(k) & (len(self._buckets)-1)
    def __len__(self): return self._n
    def __setitem__(self, k: Any, v: T) -> None:
        b = self._buckets[self._idx(k)]
        for i,(kk,_) in enumerate(b):
            if kk == k: b[i] = (k,v); return
        b.append((k,v)); self._n += 1
        if self._n > len(self._buckets)*0.75: self._resize()
    def __getitem__(self, k: Any) -> T:
        for kk,v in self._buckets[self._idx(k)]:
            if kk == k: return v
        raise KeyError(k)
    def __delitem__(self, k: Any) -> None:
        b = self._buckets[self._idx(k)]
        for i,(kk,_) in enumerate(b):
            if kk == k: b.pop(i); self._n -= 1; return
        raise KeyError(k)
    def __contains__(self, k: Any) -> bool:
        return any(kk == k for kk,_ in self._buckets[self._idx(k)])
    def _resize(self) -> None:
        items = [(k,v) for b in self._buckets for k,v in b]
        self._buckets = [[] for _ in range(len(self._buckets)*2)]; self._n = 0
        for k,v in items: self[k] = v
_TOMB = object()
class OpenAddrHT:
    def __init__(self, cap: int = 8):
        self._keys: list[Any] = [None]*cap; self._vals: list[Any] = [None]*cap
        self._n = 0
    def _probe(self, k: Any) -> Iterator[int]:
        mask = len(self._keys)-1
        i = hash(k) & mask
        perturb = hash(k)
        for _ in range(len(self._keys)):
            yield i
            perturb >>= 5
            i = (5*i + 1 + perturb) & mask       # CPython's perturbation recurrence
    def __setitem__(self, k, v):
        first_tomb = None
        for i in self._probe(k):
            if self._keys[i] is None:
                tgt = first_tomb if first_tomb is not None else i
                self._keys[tgt], self._vals[tgt] = k, v; self._n += 1; break
            if self._keys[i] is _TOMB:
                if first_tomb is None: first_tomb = i
                continue
            if self._keys[i] == k: self._vals[i] = v; return
        if self._n > len(self._keys)*0.66: self._resize()
    def __getitem__(self, k):
        for i in self._probe(k):
            if self._keys[i] is None: raise KeyError(k)
            if self._keys[i] is not _TOMB and self._keys[i] == k: return self._vals[i]
        raise KeyError(k)
    def __delitem__(self, k):
        for i in self._probe(k):
            if self._keys[i] is None: raise KeyError(k)
            if self._keys[i] is not _TOMB and self._keys[i] == k:
                self._keys[i] = _TOMB; self._vals[i] = None; self._n -= 1; return
        raise KeyError(k)
    def __len__(self): return self._n
    def _resize(self):
        items = [(k,v) for k,v in zip(self._keys, self._vals) if k is not None and k is not _TOMB]
        self._keys = [None]*(len(self._keys)*2); self._vals = [None]*len(self._keys); self._n = 0
        for k,v in items: self[k] = v
for HT in (ChainMapHT, OpenAddrHT):
    t = HT()
    for i in range(100): t[f"k{i}"] = i
    assert len(t) == 100 and t["k42"] == 42
    del t["k42"]
    assert len(t) == 99
    try: t["k42"]; assert False
    except KeyError: pass
    t["k42"] = 999; assert t["k42"] == 999
ok("hash table: separate chaining and open addressing with tombstones + CPython perturbation")

# ---------- 5. heap from scratch + median ----------
class MinHeap(Generic[T]):
    def __init__(self, items: Optional[list[T]] = None, key: Callable[[T], Any] = lambda x: x):
        self._a: list[T] = list(items or []); self._key = key
        for i in range(len(self._a)//2 - 1, -1, -1): self._sift_down(i)   # O(n)
    def __len__(self): return len(self._a)
    def peek(self) -> T: return self._a[0]
    def push(self, v: T) -> None: self._a.append(v); self._sift_up(len(self._a)-1)
    def pop(self) -> T:
        top, last = self._a[0], self._a.pop()
        if self._a: self._a[0] = last; self._sift_down(0)
        return top
    def _sift_up(self, i: int) -> None:
        while i and self._key(self._a[i]) < self._key(self._a[(i-1)//2]):
            p = (i-1)//2; self._a[i], self._a[p] = self._a[p], self._a[i]; i = p
    def _sift_down(self, i: int) -> None:
        n = len(self._a)
        while True:
            small, l, r = i, 2*i+1, 2*i+2
            if l < n and self._key(self._a[l]) < self._key(self._a[small]): small = l
            if r < n and self._key(self._a[r]) < self._key(self._a[small]): small = r
            if small == i: return
            self._a[i], self._a[small] = self._a[small], self._a[i]; i = small
class MedianFinder:
    def __init__(self): self.lo: list[float] = []; self.hi: list[float] = []   # lo = max-heap (negated)
    def add(self, x: float) -> None:
        heapq.heappush(self.lo, -x)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo): heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def median(self) -> float:
        if len(self.lo) > len(self.hi): return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2
data = [random.randint(0,1000) for _ in range(500)]
mh = MinHeap(data)
assert [mh.pop() for _ in range(len(data))] == sorted(data)
mf = MedianFinder()
for x in [5,15,1,3]: mf.add(x)
assert mf.median() == 4.0
mf.add(4); assert mf.median() == 4
ok("MinHeap: O(n) heapify then n pops == sorted; MedianFinder via two heaps")

class IndexedHeap:
    """Decrease-key heap for Dijkstra: position map keeps updates O(log n)."""
    def __init__(self): self._a: list[tuple[float, Any]] = []; self._pos: dict[Any, int] = {}
    def __len__(self): return len(self._a)
    def __contains__(self, k): return k in self._pos
    def push(self, key, pri):
        self._a.append((pri, key)); self._pos[key] = len(self._a)-1; self._up(len(self._a)-1)
    def decrease(self, key, pri):
        i = self._pos[key]
        if pri >= self._a[i][0]: return False
        self._a[i] = (pri, key); self._up(i); return True
    def pop(self):
        pri, key = self._a[0]; last = self._a.pop(); del self._pos[key]
        if self._a: self._a[0] = last; self._pos[last[1]] = 0; self._down(0)
        return key, pri
    def _swap(self, i, j):
        self._a[i], self._a[j] = self._a[j], self._a[i]
        self._pos[self._a[i][1]], self._pos[self._a[j][1]] = i, j
    def _up(self, i):
        while i and self._a[i][0] < self._a[(i-1)//2][0]: self._swap(i,(i-1)//2); i = (i-1)//2
    def _down(self, i):
        n = len(self._a)
        while True:
            s, l, r = i, 2*i+1, 2*i+2
            if l < n and self._a[l][0] < self._a[s][0]: s = l
            if r < n and self._a[r][0] < self._a[s][0]: s = r
            if s == i: return
            self._swap(i,s); i = s
ih = IndexedHeap()
for k,p in [('a',5),('b',3),('c',9)]: ih.push(k,p)
assert ih.decrease('c', 1) and not ih.decrease('a', 7)
assert [ih.pop()[0] for _ in range(3)] == ['c','b','a']
ok("IndexedHeap: decrease-key in O(log n) via a key->position map (Dijkstra without stale entries)")

# ---------- 6/7. BST + AVL ----------
class BST:
    class N:
        __slots__=("v","l","r","size")
        def __init__(self,v): self.v=v; self.l=None; self.r=None; self.size=1
    def __init__(self): self.root=None
    def insert(self,v): self.root=self._ins(self.root,v)
    def _ins(self,n,v):
        if n is None: return BST.N(v)
        if v < n.v: n.l=self._ins(n.l,v)
        elif v > n.v: n.r=self._ins(n.r,v)
        else: return n
        n.size = 1 + (n.l.size if n.l else 0) + (n.r.size if n.r else 0)
        return n
    def __contains__(self,v):
        n=self.root
        while n:
            if v==n.v: return True
            n = n.l if v<n.v else n.r
        return False
    def delete(self,v): self.root=self._del(self.root,v)
    def _del(self,n,v):
        if n is None: return None
        if v<n.v: n.l=self._del(n.l,v)
        elif v>n.v: n.r=self._del(n.r,v)
        else:
            if n.l is None: return n.r
            if n.r is None: return n.l
            s=n.r
            while s.l: s=s.l
            n.v=s.v; n.r=self._del(n.r,s.v)
        n.size = 1 + (n.l.size if n.l else 0) + (n.r.size if n.r else 0)
        return n
    def inorder(self,n="root"):
        if n=="root": n=self.root
        if n is None: return
        yield from self.inorder(n.l); yield n.v; yield from self.inorder(n.r)
    def inorder_iter(self):
        res, st, cur = [], [], self.root
        while cur or st:
            while cur: st.append(cur); cur=cur.l
            n=st.pop(); res.append(n.v); cur=n.r
        return res
    def morris(self):
        res, cur = [], self.root
        while cur:
            if cur.l is None: res.append(cur.v); cur=cur.r
            else:
                pred=cur.l
                while pred.r and pred.r is not cur: pred=pred.r
                if pred.r is None: pred.r=cur; cur=cur.l
                else: pred.r=None; res.append(cur.v); cur=cur.r
        return res
    def kth(self,k):
        n=self.root
        while n:
            ls = n.l.size if n.l else 0
            if k==ls+1: return n.v
            if k<=ls: n=n.l
            else: k-=ls+1; n=n.r
        return None
t = BST()
for v in [50,30,70,20,40,60,80]: t.insert(v)
assert list(t.inorder())==[20,30,40,50,60,70,80]==t.inorder_iter()==t.morris()
assert t.kth(3)==40 and 60 in t and 65 not in t
t.delete(20); t.delete(70); t.delete(50)
assert list(t.inorder())==[30,40,60,80]
ok("BST: insert/delete(3 cases)/inorder(rec, iter, Morris)/kth-smallest via subtree sizes")

class AVL:
    class N:
        __slots__=("v","l","r","h")
        def __init__(self,v): self.v=v; self.l=None; self.r=None; self.h=1
    def __init__(self): self.root=None
    @staticmethod
    def _h(n): return n.h if n else 0
    def _upd(self,n): n.h = 1+max(self._h(n.l), self._h(n.r))
    def _bf(self,n): return self._h(n.l)-self._h(n.r)
    def _rot_r(self,y):
        x=y.l; y.l=x.r; x.r=y; self._upd(y); self._upd(x); return x
    def _rot_l(self,x):
        y=x.r; x.r=y.l; y.l=x; self._upd(x); self._upd(y); return y
    def _rebalance(self,n):
        self._upd(n); b=self._bf(n)
        if b>1:
            if self._bf(n.l)<0: n.l=self._rot_l(n.l)
            return self._rot_r(n)
        if b<-1:
            if self._bf(n.r)>0: n.r=self._rot_r(n.r)
            return self._rot_l(n)
        return n
    def insert(self,v): self.root=self._ins(self.root,v)
    def _ins(self,n,v):
        if n is None: return AVL.N(v)
        if v<n.v: n.l=self._ins(n.l,v)
        elif v>n.v: n.r=self._ins(n.r,v)
        else: return n
        return self._rebalance(n)
    def delete(self,v): self.root=self._del(self.root,v)
    def _del(self,n,v):
        if n is None: return None
        if v<n.v: n.l=self._del(n.l,v)
        elif v>n.v: n.r=self._del(n.r,v)
        else:
            if n.l is None: return n.r
            if n.r is None: return n.l
            s=n.r
            while s.l: s=s.l
            n.v=s.v; n.r=self._del(n.r,s.v)
        return self._rebalance(n)
    def height(self): return self._h(self.root)
    def balanced(self,n="root"):
        if n=="root": n=self.root
        if n is None: return True
        return abs(self._bf(n))<=1 and self.balanced(n.l) and self.balanced(n.r)
    def inorder(self,n="root"):
        if n=="root": n=self.root
        if n is None: return
        yield from self.inorder(n.l); yield n.v; yield from self.inorder(n.r)
av=AVL()
for i in range(1,1001): av.insert(i)
assert av.height()<=12 and av.balanced()
for i in range(1,501): av.delete(i)
assert av.balanced() and len(list(av.inorder()))==500
ok(f"AVL: 1000 sorted inserts -> height {av.height()} (a plain BST would be 1000); balanced after 500 deletes")

# ---------- 8. trie ----------
def make_trie(): return defaultdict(make_trie)
END = object()
class Trie:
    def __init__(self): self.root: dict = {}
    def insert(self, w: str) -> None:
        n = self.root
        for ch in w: n = n.setdefault(ch, {}); n['#count'] = n.get('#count',0)+1
        n[END] = True
    def _node(self, p: str):
        n = self.root
        for ch in p:
            if ch not in n: return None
            n = n[ch]
        return n
    def __contains__(self, w): 
        n=self._node(w); return bool(n) and END in n
    def starts_with(self, p): return self._node(p) is not None
    def count_prefix(self, p):
        n=self._node(p); return n.get('#count',0) if n else 0
    def delete(self, w) -> bool:
        path=[]; n=self.root
        for ch in w:
            if ch not in n: return False
            path.append((n,ch)); n=n[ch]
        if END not in n: return False
        del n[END]
        for parent,ch in reversed(path):
            child=parent[ch]
            if END in child or any(k for k in child if k != '#count'): break
            del parent[ch]
        return True
    def wildcard(self, pat: str) -> bool:
        def dfs(i, n):
            if i==len(pat): return END in n
            ch=pat[i]
            if ch=='.':
                return any(dfs(i+1, v) for k,v in n.items() if k!='#count' and k is not END)
            return dfs(i+1, n[ch]) if ch in n else False
        return dfs(0, self.root)
    def autocomplete(self, prefix, k=5):
        start=self._node(prefix)
        if start is None: return []
        res=[]; stack=[(start, prefix)]
        while stack and len(res)<k:
            n,s = stack.pop()
            if END in n: res.append(s)
            for ch in sorted((c for c in n if c!='#count' and c is not END), reverse=True):
                stack.append((n[ch], s+ch))
        return res
tr = Trie()
for w in ['cat','car','card','care','dog','do']: tr.insert(w)
assert 'car' in tr and 'ca' not in tr and tr.starts_with('ca')
assert tr.count_prefix('car')==3
assert tr.autocomplete('car',3)==['car','card','care']
assert tr.wildcard('c.r') and tr.wildcard('d.') and not tr.wildcard('c..t')
assert tr.delete('car') and 'car' not in tr and 'card' in tr
ok("Trie on nested dicts: insert/contains/starts_with/count_prefix/delete/wildcard/autocomplete")

# ---------- 9. DSU ----------
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n)); self.size=[1]*n; self.components=n
    def find(self, x: int) -> int:
        while self.parent[x]!=x:
            self.parent[x]=self.parent[self.parent[x]]      # path halving
            x=self.parent[x]
        return x
    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra==rb: return False
        if self.size[ra]<self.size[rb]: ra, rb = rb, ra
        self.parent[rb]=ra; self.size[ra]+=self.size[rb]; self.components-=1
        return True
    def connected(self,a,b): return self.find(a)==self.find(b)
d = DSU(10)
assert d.union(0,1) and d.union(1,2) and not d.union(0,2)
d.union(5,6); d.union(6,7); d.union(7,8)
assert d.connected(0,2) and not d.connected(2,5)
assert d.size[d.find(5)]==4 and d.components==5
ok("DSU: union by size + path halving, component counting")

# ---------- 10. LRU x4 + LFU ----------
class LRUOrdered:
    def __init__(self, cap): self.cap=cap; self.d=OrderedDict()
    def get(self,k):
        if k not in self.d: return None
        self.d.move_to_end(k); return self.d[k]
    def put(self,k,v):
        if k in self.d: self.d.move_to_end(k)
        self.d[k]=v
        if len(self.d)>self.cap: self.d.popitem(last=False)
class LRUPlainDict:
    def __init__(self, cap): self.cap=cap; self.d={}
    def get(self,k):
        if k not in self.d: return None
        v=self.d.pop(k); self.d[k]=v; return v
    def put(self,k,v):
        if k in self.d: self.d.pop(k)
        self.d[k]=v
        if len(self.d)>self.cap: del self.d[next(iter(self.d))]
class LFU:
    def __init__(self, cap):
        self.cap=cap; self.vals={}; self.freq={}; self.buckets=defaultdict(OrderedDict); self.min=0
    def _touch(self,k):
        f=self.freq[k]; self.freq[k]=f+1
        del self.buckets[f][k]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min==f: self.min=f+1
        self.buckets[f+1][k]=None
    def get(self,k):
        if k not in self.vals: return None
        self._touch(k); return self.vals[k]
    def put(self,k,v):
        if self.cap<=0: return
        if k in self.vals: self.vals[k]=v; self._touch(k); return
        if len(self.vals)>=self.cap:
            victim,_ = self.buckets[self.min].popitem(last=False)
            del self.vals[victim]; del self.freq[victim]
        self.vals[k]=v; self.freq[k]=1; self.min=1; self.buckets[1][k]=None
for C in (LRUOrdered, LRUPlainDict):
    c=C(2); c.put('x',1); c.put('y',2); c.get('x'); c.put('z',3)
    assert c.get('y') is None and c.get('x')==1 and c.get('z')==3
l=LFU(2); l.put('x',1); l.put('y',2); l.get('x'); l.get('x'); l.put('z',3)
assert l.get('y') is None and l.get('x')==1 and l.get('z')==3
ok("LRU via OrderedDict and via plain dict insertion order; LFU via frequency buckets")

# ---------- 11. segment tree / fenwick ----------
class SegTree:
    def __init__(self, arr, combine=lambda a,b:a+b, identity=0):
        self.n=len(arr); self.f=combine; self.id=identity
        self.t=[identity]*(2*self.n)
        self.t[self.n:]=arr
        for i in range(self.n-1,0,-1): self.t[i]=combine(self.t[2*i], self.t[2*i+1])
    def update(self,i,v):
        p=i+self.n; self.t[p]=v; p//=2
        while p: self.t[p]=self.f(self.t[2*p], self.t[2*p+1]); p//=2
    def query(self,l,r):
        res=self.id; lo, hi = l+self.n, r+self.n
        while lo<hi:
            if lo&1: res=self.f(res,self.t[lo]); lo+=1
            if hi&1: hi-=1; res=self.f(res,self.t[hi])
            lo//=2; hi//=2
        return res
class Fenwick:
    def __init__(self,n): self.n=n; self.t=[0]*(n+1)
    def add(self,i,delta):
        x=i+1
        while x<=self.n: self.t[x]+=delta; x+=x&-x
    def prefix(self,i):
        s=0; x=i+1
        while x>0: s+=self.t[x]; x-=x&-x
        return s
    def range(self,l,r): return self.prefix(r)-(self.prefix(l-1) if l else 0)
    def kth(self,k):
        pos=0; rem=k; pw=1<<(self.n.bit_length()-1)
        while pw:
            if pos+pw<=self.n and self.t[pos+pw]<rem:
                pos+=pw; rem-=self.t[pos]
            pw>>=1
        return pos
arr=[1,3,5,7,9,11]
st=SegTree(list(arr)); assert st.query(1,4)==15
st.update(2,50); assert st.query(1,4)==60
mn=SegTree(list(arr), min, float('inf')); assert mn.query(2,6)==5
fw=Fenwick(6)
for i,v in enumerate(arr): fw.add(i,v)
assert fw.range(1,3)==15 and fw.prefix(5)==36
f2=Fenwick(10)
for i in range(5): f2.add(i,1)
assert f2.kth(3)==2
ok("SegTree (sum and min via injected monoid), Fenwick (prefix/range/kth)")

# ---------- 12. skip list ----------
class SkipList:
    MAX, P = 16, 0.5
    class N:
        __slots__=("v","next")
        def __init__(self,v,lvl): self.v=v; self.next=[None]*lvl
    def __init__(self, rng=random.random):
        self.head=SkipList.N(None, SkipList.MAX); self.levels=1; self.rng=rng; self.n=0
    def _rand_level(self):
        l=1
        while self.rng()<SkipList.P and l<SkipList.MAX: l+=1
        return l
    def insert(self,v):
        upd=[self.head]*SkipList.MAX; x=self.head
        for i in range(self.levels-1,-1,-1):
            while x.next[i] and x.next[i].v < v: x=x.next[i]
            upd[i]=x
        lvl=self._rand_level(); self.levels=max(self.levels,lvl)
        node=SkipList.N(v, SkipList.MAX)
        for i in range(lvl): node.next[i]=upd[i].next[i]; upd[i].next[i]=node
        self.n+=1
    def __contains__(self,v):
        x=self.head
        for i in range(self.levels-1,-1,-1):
            while x.next[i] and x.next[i].v<v: x=x.next[i]
        return x.next[0] is not None and x.next[0].v==v
    def delete(self,v):
        upd=[self.head]*SkipList.MAX; x=self.head
        for i in range(self.levels-1,-1,-1):
            while x.next[i] and x.next[i].v<v: x=x.next[i]
            upd[i]=x
        tgt=x.next[0]
        if tgt is None or tgt.v!=v: return False
        for i in range(self.levels):
            if upd[i].next[i] is tgt: upd[i].next[i]=tgt.next[i]
        self.n-=1; return True
    def to_list(self):
        r=[]; x=self.head.next[0]
        while x: r.append(x.v); x=x.next[0]
        return r
sl=SkipList()
for v in [5,1,9,3,7,3]: sl.insert(v)
assert sl.to_list()==[1,3,3,5,7,9] and 7 in sl and 8 not in sl
assert sl.delete(3) and sl.to_list().count(3)==1
ok("SkipList: probabilistic levels, sorted order, contains/delete")

# ---------- 13. bloom filter ----------
class BloomFilter:
    def __init__(self, n: int, p: float = 0.01):
        self.m = math.ceil(-(n*math.log(p))/(math.log(2)**2))
        self.k = max(1, round((self.m/n)*math.log(2)))
        self.bits = bytearray((self.m+7)//8)
    def _hashes(self, s: str):
        import hashlib
        dig = hashlib.blake2b(s.encode(), digest_size=16).digest()
        h1 = int.from_bytes(dig[:8], 'little'); h2 = int.from_bytes(dig[8:], 'little')
        for i in range(self.k): yield (h1 + i*h2 + i*i) % self.m
    def add(self, s):
        for h in self._hashes(s): self.bits[h>>3] |= 1 << (h&7)
    def __contains__(self, s):
        return all(self.bits[h>>3] & (1 << (h&7)) for h in self._hashes(s))
bf=BloomFilter(1000, 0.01)
present=[f"k{i}" for i in range(1000)]
for k in present: bf.add(k)
assert all(k in bf for k in present)
fp=sum(1 for i in range(10000) if f"absent{i}" in bf)
assert fp/10000 < 0.03, fp/10000
ok(f"BloomFilter: m={bf.m} bits k={bf.k} hashes, 0 false negatives, measured FP {fp/100:.2f}% (target 1%)")

# ---------- 14. SortedList on bisect ----------
class SortedList:
    def __init__(self, iterable=()): self._a=sorted(iterable)
    def add(self,v): bisect.insort(self._a, v)                # O(n)
    def remove(self,v):
        i=bisect.bisect_left(self._a,v)
        if i<len(self._a) and self._a[i]==v: self._a.pop(i); return True
        return False
    def count(self,v): return bisect.bisect_right(self._a,v)-bisect.bisect_left(self._a,v)
    def floor(self,v):
        i=bisect.bisect_right(self._a,v)
        return self._a[i-1] if i else None
    def ceil(self,v):
        i=bisect.bisect_left(self._a,v)
        return self._a[i] if i<len(self._a) else None
    def rank(self,v): return bisect.bisect_left(self._a,v)
    def __getitem__(self,i): return self._a[i]
    def __len__(self): return len(self._a)
    def __iter__(self): return iter(self._a)
s=SortedList([5,1,3,3,9])
assert list(s)==[1,3,3,5,9] and s.count(3)==2 and s[2]==3
assert s.floor(4)==3 and s.ceil(4)==5 and s.rank(5)==3
assert s.remove(3) and s.count(3)==1
ok("SortedList on bisect: add/remove/count/floor/ceil/rank (O(log n) search, O(n) insert)")

# ---------- 15. persistent list ----------
class PList:
    __slots__=("head","tail","_len")
    EMPTY: "PList"
    def __init__(self, head=None, tail=None, _len=0): self.head=head; self.tail=tail; self._len=_len
    def cons(self, v): return PList(v, self, self._len+1)
    def __len__(self): return self._len
    def __iter__(self):
        n=self
        while n._len: yield n.head; n=n.tail
PList.EMPTY = PList()
a = PList.EMPTY.cons(3).cons(2).cons(1)
b = a.tail.cons(99)                  # shares the tail with a
assert list(a)==[1,2,3] and list(b)==[99,2,3] and b.tail is a.tail
ok("Persistent list: cons is O(1) and structurally shares the tail (b.tail is a.tail)")

print("\n".join(out))
print(f"\nALL ASSERTIONS PASSED ({len(out)} groups) on CPython {sys.version.split()[0]}")