---
title: "Algorithms"
book: "Interviews III: Code"
subject: quant
language: en
chapter: 1
exercises: 0
source: https://one-course.com/books/quant/20/en/chapter/1-algorithms
license: CC-BY-NC-SA-4.0
credit: "One Quant Book, One Course (one-course.com)"
---

# Chapter 1 — Algorithms

Choosing the data structure before writing the loop, stating its cost, and getting the edges right: empty input, ties, duplicates and values that can be negative. Prices, order books and streams appear where they change the problem. Write each solution as you would on a whiteboard, in Python or C++, then say what it costs.

**Question 1.1 ★ QD, Dev, QR, QT • any • junior.**

You are given a list of prices in time order. The drawdown at a moment is the highest price so far minus the price now. Write a function that returns the largest drawdown in the list, in one pass and with constant extra memory. What does it return for `[100, 120, 90, 110, 80, 130]`?

**Answer to Question 1.1.**

Keep the highest price seen so far, and at each price update the largest gap below it, as in [Listing 1.1](#lst-iv3-al-drawdown). It takes $O(n)$ time and $O(1)$ memory, and the example returns 40: the fall from 120 to 80.

```python
def max_drawdown(prices):
    peak = None
    worst = 0
    for p in prices:
        if peak is None or p > peak:
            peak = p
        worst = max(worst, peak - p)
    return worst
```

***Listing 1.1.** One pass with a running peak. code/interviews-3/01-algorithms/python/iv_drawdown.py*

A later price can only be measured against a peak that came before it, and the running peak is the best such peak at every moment, so no earlier pair needs looking at again. A list with no fall, or an empty one, returns 0.

**Classic wrong answer.** “Highest price minus lowest price.” That ignores the order. In the example it gives 130 minus 80, which is 50, but 130 comes after 80, so that move is a rise. For `[1, 2, 3, 10]` it gives 9, and the true drawdown is 0.

**Follow-up.** *And as a percentage of the peak?* The same scan, with `(peak - p) / peak`. It can pick a different fall: `[100, 50, 1000, 600]` has its worst fall in money at 400, from 1000, and its worst in percent at 50%, from 100.

**Follow-up.** *The largest profit from one buy and one later sell?* The mirror image: keep the running low and update the largest gap above it.

**Question 1.2 ★ QD, Dev, LLE • any • junior.**

Given a list of integers and a target, return the positions of two different elements that add up to the target, or report that there are none. It must run in time proportional to the length of the list on average. What should it return for the list `[3, 4]` and the target 6?

**Answer to Question 1.2.**

Walk the list once with a dictionary from value to position, and look up the partner before inserting the current element, as in [Listing 1.2](#lst-iv3-al-twosum). It takes $O(n)$ average time and $O(n)$ memory. For `[3, 4]` and target 6 it reports no pair.

```python
def two_sum(xs, target):
    seen = {}                     # value -> a position where it occurred
    for j, x in enumerate(xs):
        i = seen.get(target - x)
        if i is not None:         # looked up before inserting, so i != j
            return i, j
        seen[x] = j
    return None
```

***Listing 1.2.** Look up, then insert. code/interviews-3/01-algorithms/python/iv_two_sum.py*

Each pair is found when its later element arrives, because its earlier element is then in the dictionary, so one pass is enough. The order of the two lines inside the loop is the whole point: since the current element is not yet inserted, it cannot pair with itself, while `[3, 3]` with target 6 still gives positions 0 and 1.

**Classic wrong answer.** Filling the dictionary first and then looking up. On `[3, 4]` with target 6 it finds 3 as the partner of 3 and returns positions 0 and 0.

**Follow-up.** *And if the list is already sorted?* Use two pointers from the ends: move the left one up if the sum is too small, and the right one down if it is too large. That needs $O(1)$ memory, and sorting first costs $O(n \log n)$ and loses the positions unless you sort them along with the values.

**Follow-up.** *What is the worst case of the dictionary?* If many keys collide, a lookup degrades towards a scan, and the whole loop towards $O(n^2)$. On untrusted input, ordered maps give a firm $O(n \log n)$.

**Question 1.3 ★ QD, Dev, LLE, QT • market maker, crypto, hedge fund • junior.**

The sell side of an order book is a list of levels, each a price and a size, from the lowest price up. A market buy order takes the cheapest shares first. Write a function that takes the levels and a quantity, and returns the fills, the quantity left unfilled and the total cost. For the levels `(100, 300), (101, 200), (103, 500)` and an order for 600 shares, what are the fills and the average price paid?

**Answer to Question 1.3.**

The fills are 300 at 100, 200 at 101 and 100 at 103, for a total of 60 500 and an average price of about 100.83. [Listing 1.3](#lst-iv3-al-sweep) walks the levels. It takes time proportional to the number of levels touched, not the number of shares.

```python
def sweep(asks, qty):
    """asks: (price, size) from the lowest price up. Returns fills, unfilled size, cost."""
    fills, cost = [], 0
    for price, size in asks:
        if qty == 0:
            break
        take = min(size, qty)
        fills.append((price, take))
        cost += price * take
        qty -= take
    return fills, qty, cost
```

***Listing 1.3.** Walking the book. code/interviews-3/01-algorithms/python/iv_sweep.py*

The cost is $300 \times 100 + 200 \times 101 + 100 \times 103 = 60\,500$, and $60\,500 / 600 \approx 100.83$, which is 0.83 above the best offer: that gap is the price of the order’s size. Prices and sizes stay integers, in ticks and lots, so the running cost is exact.

The edge the function must not hide is an order larger than the book. For 1200 shares it fills 1000 and returns 200 unfilled, at a cost of 101 700. The average price per share filled is 101.70, and dividing by the 1200 requested would give a false 84.75. So compute the average over what was filled, and report what was not. The function also leaves the book as it found it, which a caller may or may not want: say which you chose.

**Follow-up.** *How much can you buy at or below a limit price of 101?* Stop at the first level above the limit: here, 500 shares. For many such queries on one snapshot, store the cumulative sizes and use binary search.

**Question 1.4 ★ QD, Dev, LLE, QR • any • junior.**

Write a class whose method `update(x)` takes the next number of a stream and returns the mean of the last $k$ numbers, or of all of them while there are fewer than $k$. Each update must take constant time and the class may keep $O(k)$ memory. Then run it in your head with $k = 3$ on the Python floats `1e16, 1.0, 1.0, 1.0`: what does the last call return if the class keeps a running total, subtracting the value that leaves and then adding the new one, and what is the true mean?

**Answer to Question 1.4.**

Keep a circular buffer of the last $k$ values and a running total, as in [Listing 1.4](#lst-iv3-al-rolling): on each update subtract the value leaving and add the value arriving. With those floats the last call returns $1/3$, about 0.333, and the true mean is 1.

```python
class RollingMean:
    def __init__(self, k):
        self.k = k
        self.buf = [0] * k        # the last k values, overwritten in a circle
        self.n = 0                # how many values have arrived
        self.total = 0

    def update(self, x):
        i = self.n % self.k
        if self.n >= self.k:
            self.total -= self.buf[i]
        self.buf[i] = x
        self.total += x
        self.n += 1
        return self.total / min(self.n, self.k)
```

***Listing 1.4.** A circular buffer and a running total. code/interviews-3/01-algorithms/python/iv_rolling_mean.py*

The rounding is what breaks it. Doubles near $10^{16}$ are 2 apart, so `1e16 + 1.0` rounds back to `1e16`, and both 1.0 values vanish from the total. When `1e16` leaves the window, the total falls to 0, and then the last 1.0 is added, so the mean comes out as $1/3$ over a window that holds three 1.0 values. The error stays in the total from then on.

The same drift happens on ordinary prices, only more slowly: after two million updates with prices near 100, the total in our test no longer equals the sum of its ten values, though it is off by far less than a millionth. Two cures: hold prices as integer ticks, for which the sum stays exact in Python, and in C++ too until it overflows. Or recompute the total from the buffer every so often.

**Classic wrong answer.** “Sum the buffer on each call.” It is correct, and it costs $O(k)$ per update, which the question rules out.

**Question 1.5 ★ QD, Dev, QR • any • junior.**

A string holds only the characters `(`, `)`, `[`, `]`, `{` and `}`. Write a function that decides whether every bracket is closed by the matching kind, in the right order. What does it return for `([)]`, and for the empty string?

**Answer to Question 1.5.**

Use a stack: push each opening bracket, and on each closing one pop and compare, as in [Listing 1.5](#lst-iv3-al-brackets). It takes $O(n)$ time and up to $O(n)$ memory. `([)]` returns false, and the empty string returns true.

```python
def balanced(s):
    closes = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in closes:
            if not stack or stack.pop() != closes[c]:
                return False
        else:
            stack.append(c)
    return not stack
```

***Listing 1.5.** A stack of open brackets. code/interviews-3/01-algorithms/python/iv_brackets.py*

There are two ways to fail, and both must be caught: a closing bracket with an empty stack or a wrong partner, and a stack left non-empty at the end, as with `((`.

**Classic wrong answer.** One counter per kind of bracket. On `([)]` each counter goes up by one and back to zero without ever going negative, so it reports true. The order is what a counter cannot see.

**Follow-up.** *With only round brackets, can you save the memory?* Yes: one counter is enough, since there is only one possible partner. It must never go negative, and it must end at 0.

**Follow-up.** *What is the longest valid stretch of a string of round brackets?* Keep a stack of positions, with the position just before the current stretch at the bottom. Each close pops, and the length is the current position minus the new top. For `)()())` it is 4.

**Question 1.6 ★ QD, Dev, LLE • any • junior.**

A sorted list of $n$ prices may contain repeats. Write a function that returns the first position whose value is at least $x$, or $n$ if there is none, in $O(\log n)$ time. What does it return for `[1, 2, 2, 2, 3]` with $x = 2$, and with $x = 4$? In C++ with `int` positions, what is wrong with computing the midpoint as `(lo + hi) / 2`?

**Answer to Question 1.6.**

It returns 1 for $x = 2$ and 5 for $x = 4$. [Listing 1.6](#lst-iv3-al-lowerbound) keeps the invariant that the answer lies between `lo` and `hi`, both ends included, which is why `hi` starts at $n$ rather than $n - 1$: $n$ itself is a possible answer.

```python
def lower_bound(xs, target):
    lo, hi = 0, len(xs)               # the answer is always in [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
```

***Listing 1.6.** First position at least the target. code/interviews-3/01-algorithms/python/iv_lower_bound.py*

If the middle value is too small, the answer is further right, past the middle. If not, the middle itself may be the answer, so `hi` moves to it and not past it. The range shrinks at every step because `mid` is always below `hi`, so the loop ends.

In C++, `lo + hi` can exceed the largest `int` once the positions pass about a billion, and signed overflow is undefined behaviour. `lo + (hi - lo) / 2` cannot overflow.

**Classic wrong answer.** Stopping as soon as `xs[mid] == x`. That finds some position of the value, not the first: on five copies of the value it stops in the middle at once.

**Follow-up.** *How many times does $x$ occur?* The first position above $x$ minus the first position at least $x$: 4 minus 1 is 3 for the list and $x = 2$. Each is one binary search, so the count costs $O(\log n)$ however many copies there are.

**Question 1.7 ★ QD, Dev • any • junior.**

Symbols arrive one at a time. Write a class with `add(symbol)` and `first_unique()`, where the second returns the earliest symbol seen exactly once so far, or nothing if there is none. Both must take constant time on average. What does it return after A, B, A, C, B?

**Answer to Question 1.7.**

After A, B, A, C, B it returns C. [Listing 1.7](#lst-iv3-al-firstunique) keeps the symbols seen once in an `OrderedDict`, and those seen more often in a set.

```python
from collections import OrderedDict


class FirstUnique:
    def __init__(self):
        self.once = OrderedDict()     # seen exactly once, in order of arrival
        self.repeated = set()

    def add(self, symbol):
        if symbol in self.repeated:
            return
        if symbol in self.once:
            del self.once[symbol]
            self.repeated.add(symbol)
        else:
            self.once[symbol] = True

    def first_unique(self):
        return next(iter(self.once), None)
```

***Listing 1.7.** An ordered dictionary and a set. code/interviews-3/01-algorithms/python/iv_first_unique.py*

A symbol moves at most once from the dictionary to the set, and never back. An `OrderedDict` is a hash table threaded on a linked list, so deleting from the middle and reading the first key, which is the answer, are both constant time on average. The memory is proportional to the number of distinct symbols.

In C++ the same structure is a `std::list` of candidates and an `unordered_map` from symbol to its place in the list, with a null place meaning repeated.

**Classic wrong answer.** A plain `dict`, since it too keeps insertion order. In CPython `next(iter(d))` walks past the deleted entries at the front of its table, and they stay there until an insert resizes it. When the oldest symbols keep leaving, each call costs $O(n)$, and the stream is quadratic.

**Follow-up.** *A queue of arrivals instead?* It works: pop the front for good while it is repeated, and read what is left. Each symbol is popped once, so the cost is constant amortised, which the stem allows. A scan from the start on each call is the version that is $O(n)$.

**Follow-up.** *And if you only want it at the end, not after each symbol?* Count everything, then walk the input once more: simpler, though it needs the input to still be there.

**Question 1.8 ★ QD, Dev, LLE • any • junior.**

Each node of a singly linked list has a value and a pointer to the next node. Reverse the list in place, with constant extra memory, and return the new head. What should it do on an empty list? In Python, what happens to the short recursive version on a list of 100 000 nodes with the default settings?

**Answer to Question 1.8.**

Walk the list with two pointers and turn each link around, as in [Listing 1.8](#lst-iv3-al-revlist). It takes $O(n)$ time and $O(1)$ extra memory, and an empty list returns an empty list, because the loop does not run and `prev` is still `None`.

```python
class Node:
    def __init__(self, val, next=None):
        self.val, self.next = val, next


def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev
```

***Listing 1.8.** Turning each link around. code/interviews-3/01-algorithms/python/iv_reverse_list.py*

At each step everything before `head` is already reversed, with `prev` at its front. The assignment of three names is evaluated on the right first, so no pointer is lost. Written out in C++ you need a temporary for `next`, and forgetting it is the usual bug.

The recursive version is three lines, and it uses one stack frame per node. Python’s default recursion limit is 1000, so on 100 000 nodes it raises `RecursionError`. In C++ the same code can overflow the stack, and that crash has no exception to catch.

**Classic wrong answer.** Reversing the values in place by copying them to a list and back. It answers a different question: a node held elsewhere now has another value, and it uses $O(n)$ memory.

**Follow-up.** *Reverse only from position $a$ to position $b$?* Walk to the node before $a$, reverse $b - a + 1$ links in the same way, then join the two ends back on.

**Question 1.9 ★ LLE, QD, Dev • any • junior.**

For a positive integer `x`, what does the expression `x & (x - 1)` compute? Use it to test whether `x` is a power of two, and to count its set bits. Then round a requested size up to the next power of two, and say why a ring buffer wants that size.

**Answer to Question 1.9.**

It clears the lowest set bit: 12 is binary 1100 and `12 & 11` is binary 1000, which is 8. [Listing 1.9](#lst-iv3-al-bits) uses it for all three tasks.

```python
def is_power_of_two(x):
    return x > 0 and x & (x - 1) == 0


def count_set_bits(x):
    n = 0
    while x:
        x &= x - 1                    # clears the lowest set bit
        n += 1
    return n


def next_power_of_two(x):             # the smallest power of two >= x, for x >= 1
    return 1 << (x - 1).bit_length()
```

***Listing 1.9.** Three uses of the lowest set bit. code/interviews-3/01-algorithms/python/iv_bits.py*

Subtracting 1 turns the lowest set bit into 0 and every zero below it into 1, and the `&` removes those. So `x` is a power of two exactly when the result is 0, since it then had one set bit. The test must rule out 0 separately, because `0 & -1` is 0 too. The count loops once per set bit, not once per bit.

The rounding works since `x - 1` has the same bit length as the answer’s exponent: 1000 rounds to 1024, and 1024 stays 1024. A ring buffer of size $2^m$ turns the wrap of a growing counter `i` into `i & (size - 1)`, which is one cheap instruction, where `%` on an unknown size is an integer division. The counter may also overflow an unsigned type safely, because the wrap of a power of two lines up with the mask.

**Follow-up.** *What would you use in real C++20?* The header `<bit>` has `std::has_single_bit`, `std::popcount` and `std::bit_ceil`, which compile to a single instruction where the processor has one.

**Question 1.10 ★ QD, Dev, LLE • any • junior.**

A file should hold every sequence number from 1 to $n$, in no particular order, but exactly one is missing. Find it in one pass with constant extra memory. What do you return for `[3, 1, 5, 2]` with $n = 5$? If you add up the numbers in a signed 64-bit integer, can that overflow? What if two are missing?

**Answer to Question 1.10.**

XOR all of $1, \dots, n$ together with all the values present, as in [Listing 1.10](#lst-iv3-al-missing). Each number present cancels, and what is left is the missing one. For the example it returns 4. It takes $O(n)$ time and $O(1)$ memory.

```python
def missing(seqs, n):
    x = 0
    for i in range(1, n + 1):
        x ^= i
    for s in seqs:
        x ^= s
    return x
```

***Listing 1.10.** Everything present cancels. code/interviews-3/01-algorithms/python/iv_missing.py*

The other classic is the sum: $n(n + 1)/2$ minus the total of what is there. It overflows a signed 64-bit integer once $n(n + 1)/2$ passes $2^{63} - 1$, which happens near $n = 4.3 \times 10^9$. Sequence numbers can reach that on a long-running feed, and XOR can never overflow, which is why it is the safer of the two.

If the file is in order, you need neither: compare each number with the last one plus one.

**Classic wrong answer.** Sorting first, or using a set. Both give the right number, and neither meets the memory limit.

**Follow-up.** *And when two are missing?* The XOR now holds $a \oplus b$. It is non-zero, so pick one of its set bits, on which $a$ and $b$ differ. Then XOR again, over only the numbers with that bit set, which gives $a$, and $b$ follows. For `[3, 5, 2]` with $n = 5$ the missing pair is 1 and 4.

**Question 1.11 ★ QD, Dev • any • junior.**

Design a stack with `push`, `pop` and `min`, each taking constant time in the worst case. Values can repeat. Why is a single variable holding the current minimum not enough?

**Answer to Question 1.11.**

Keep a second stack of the minimum at each depth where it changed, as in [Listing 1.11](#lst-iv3-al-minstack). All three operations are $O(1)$ in the worst case, and the extra memory is at most $O(n)$.

```python
class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []                # the minimum at each depth where it changed

    def push(self, x):
        self.items.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)

    def pop(self):
        x = self.items.pop()
        if x == self.mins[-1]:
            self.mins.pop()
        return x

    def min(self):
        return self.mins[-1]
```

***Listing 1.11.** A second stack of minima. code/interviews-3/01-algorithms/python/iv_min_stack.py*

A single variable fails on `pop`: when the current minimum leaves, the variable cannot tell you the previous one without a scan. The second stack holds exactly that history.

The comparison in `push` must be `<=` and not `<`. Push 1, 1 and pop once: the minimum is still 1, and with `<` the single entry on the second stack would have been popped, leaving nothing.

**Classic wrong answer.** A heap beside the stack. It finds the minimum, but pop would have to delete an arbitrary value from the heap, so it costs more and does nothing extra here.

**Follow-up.** *The same for a queue?* Build it from two such stacks, so the minimum is the smaller of the two stacks’ minima, at $O(1)$ amortised; or use a deque of increasing values, as for a sliding window minimum.

**Question 1.12 ★ QD, Dev, LLE • any • junior.**

Build a first-in, first-out queue using only two stacks. One `pop` may move every element, so why is the cost still constant per operation over a long run? Would you use it on a path where each single operation has a latency limit?

**Answer to Question 1.12.**

Push onto `inbox`. To pop, take from `outbox`, and when it is empty first move all of `inbox` across, which reverses it into arrival order, as in [Listing 1.12](#lst-iv3-al-twostack). Each element is moved at most once, so $n$ operations do at most $n$ moves in all: amortised $O(1)$.

```python
class Queue:
    def __init__(self):
        self.inbox, self.outbox = [], []
        self.moves = 0

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1
        return self.outbox.pop()
```

***Listing 1.12.** Moving only when the output is empty. code/interviews-3/01-algorithms/python/iv_two_stack_queue.py*

Follow one element: pushed once, moved once, popped once. That is three operations, however long the queue gets. The expensive pop pays for the cheap operations that came before it, which is what amortised means. It is not an average over random inputs, and it holds for every sequence.

Order is preserved because `outbox` is never refilled until it is empty, so everything in it is older than everything in `inbox`.

On a path with a latency limit, I would not use it. Amortised $O(1)$ still allows one `pop` that moves a million elements, and that one message is the one that misses the limit. A ring buffer gives a true worst-case constant.

**Classic wrong answer.** “Move everything back to `inbox` after each pop.” It stays correct, and costs $O(n)$ per operation.

**Question 1.13 ★ QD, Dev, LLE, QT • market maker, crypto, hedge fund • junior.**

A feed sends prices as decimal text, such as 101.25, with a tick of 0.01. Write a function that turns the text into an integer number of ticks, without floating point, and refuses text with more than two decimals. In Python, what does `int(float(s) * 100)` give for the text 1.15? What must your function return for the text -0.05?

**Answer to Question 1.13.**

[Listing 1.13](#lst-iv3-al-ticks) splits the text at the point and adds up integers. The float version gives 114 for the text 1.15, which is one tick wrong. The text -0.05 must give $-5$.

```python
def to_ticks(s):
    """The text s, in integer hundredths. ValueError beyond 2 decimals."""
    negative = s.startswith("-")
    whole, _, frac = (s[1:] if negative else s).partition(".")
    if len(frac) > 2 or not (whole + frac).isdigit():
        raise ValueError(s)
    ticks = int(whole or "0") * 100 + int(frac.ljust(2, "0"))
    return -ticks if negative else ticks
```

***Listing 1.13.** Text to integer ticks, with no float. code/interviews-3/01-algorithms/python/iv_ticks.py*

1.15 has no exact binary form. The nearest double is slightly below it, the product comes out as 114.99999999999999, and `int` cuts it towards zero. Rounding first, with `round(float(s) * 100)`, cures this example, and it still sends the value through a float, which goes wrong for prices large enough to lose the digit, and it cannot refuse text with too many decimals.

The sign has to be taken off first and put back at the end. A parser that reads the whole part as an integer sees `-0` for -0.05. That is plain 0, so the sign is gone and the result is $+5$: a bid at the wrong side of zero. This matters on spreads, which can be negative.

**Classic wrong answer.** “Compare the float with an epsilon.” Trading code then holds prices as non-exact keys, and two feeds can disagree on whether a price equals a level.

**Follow-up.** *And in C++?* `std::from_chars` parses each integer part without touching the locale or allocating, so it suits a hot path.

**Question 1.14 ★ QD, Dev, QR, QT • any • junior.**

You have a list of daily profits and losses. Return the largest sum over a non-empty contiguous stretch of days, and where it starts and ends, in one pass. What do you return for `[-2, 3, -1, 4, -5]`, and for `[-3, -1, -2]`?

**Answer to Question 1.14.**

It returns a sum of 6, from position 1 to position 3, for the first list, and $-1$, the single element at position 1, for the second. [Listing 1.14](#lst-iv3-al-kadane) is Kadane’s algorithm: $O(n)$ time and $O(1)$ memory.

```python
def best_stretch(xs):
    """Largest sum of a non-empty stretch, with its first and last positions."""
    best = (xs[0], 0, 0)
    here, start = xs[0], 0
    for i, x in enumerate(xs[1:], 1):
        if here < 0:                  # a negative past can only hurt
            here, start = x, i
        else:
            here += x
        best = max(best, (here, start, i), key=lambda t: t[0])
    return best
```

***Listing 1.14.** The best stretch ending here. code/interviews-3/01-algorithms/python/iv_kadane.py*

`here` is the best sum over stretches ending at the current day. If the best stretch ending at the previous day is negative, then dropping it does better, so the new stretch starts today. Otherwise extending it does better. Every stretch ends somewhere, so the largest `here` ever seen is the answer.

The stem says non-empty. That is why the code starts from the first element and not from 0: starting from 0 returns 0 on an all-negative list, which is the sum of no days. An empty list has no such stretch, so the listing raises `IndexError`: say that this is your choice.

**Classic wrong answer.** Sorting the days, or summing the positive ones. Both ignore that the days must be contiguous: the first list’s positive days add to 7, and no stretch reaches that.

**Follow-up.** *How does this relate to maximum drawdown?* Take cumulative profit. A stretch’s sum is one cumulative value minus an earlier one, so this is the largest rise, and the largest drawdown is the same scan on the opposite sign.

**Question 1.15 ★ QD, Dev, QR • any • junior.**

Given a list of integers, return a list in which position $i$ holds the product of all the other elements. Do it in $O(n)$ time, without division, and with no extra array beyond the output. What do you return for `[2, 3, 0, 4]`? Why does “multiply everything, then divide” fail on that list?

**Answer to Question 1.15.**

It returns `[0, 0, 24, 0]`. [Listing 1.15](#lst-iv3-al-product) makes two passes: one multiplies in everything to the left of each position, the other everything to the right. That takes $O(n)$ time, and the output list is the only array.

```python
def product_except_self(xs):
    out = [1] * len(xs)
    left = 1
    for i, x in enumerate(xs):
        out[i] = left                 # the product of everything before i
        left *= x
    right = 1
    for i in range(len(xs) - 1, -1, -1):
        out[i] *= right               # and of everything after i
        right *= xs[i]
    return out
```

***Listing 1.15.** A left pass and a right pass. code/interviews-3/01-algorithms/python/iv_product_except.py*

The total product of that list is 0, so dividing it by 0 at position 2 fails, and dividing by 2 at position 0 gives 0, which is right only by luck of the other positions. With division you would need to count the zeros: two or more make every output 0, and exactly one makes every output 0 except at that position.

The list `[2, 3, 0, 0]` shows the case of two zeros, and it returns all zeros.

**Classic wrong answer.** Using logarithms and subtracting. Zeros and negative values have no logarithm, and rounding gives inexact results in any case.

**Follow-up.** *In C++ with 64-bit integers, what can go wrong?* The running products can overflow even when every output fits, for instance if a zero comes after large values, and signed overflow is undefined behaviour. Python’s integers do not overflow.

**Question 1.16 ★ QD, Dev, LLE, QT • any • junior.**

What do `-7 // 2` and `-7 % 2` give in Python 3, and `-7 / 2` and `-7 % 2` give for `int` in C++20? A calendar spread can have a negative price. Write a function, in either language, that rounds an integer price down to a multiple of a tick, so that $-7$ with a tick of 5 gives $-10$.

**Answer to Question 1.16.**

Python 3 gives $-4$ and $1$, as `//` rounds down and the remainder takes the sign of the divisor. C++20 gives $-3$ and $-1$, as `/` truncates towards zero and the remainder takes the sign of the dividend. In C++ [Listing 1.16](#lst-iv3-al-floorsnap) corrects for that.

```cpp
std::int64_t snap_down(std::int64_t x, std::int64_t tick) {
    const std::int64_t r = x % tick;     // has the sign of x
    return r < 0 ? x - r - tick : x - r;
}
```

***Listing 1.16.** Rounding down in C++. code/interviews-3/01-algorithms/cpp/floor_snap.cpp*

In both languages the quotient times the divisor plus the remainder gives back the value, which is why the two answers pair up: $-4 \times 2 + 1$ and $-3 \times 2 - 1$ are both $-7$.

In Python the function is one expression, `p - p % tick`, because the remainder is never negative for a positive tick. So $-7$ with tick 5 gives $-7 - 3 = -10$. The C++ remainder for those values is $-2$, and subtracting it alone gives $-5$, which is the wrong way: rounding towards zero, not down. So when the remainder is negative, the function takes off one more tick.

**Classic wrong answer.** `x / tick * tick` in C++. It gives $-5$ for $-7$, the wrong way on a negative spread, and it looks correct on every positive test.

**Follow-up.** *Is this behaviour of C++ guaranteed?* Yes: the standard says that integer division discards the fractional part, and that $(a/b) \times b + a \% b = a$. The only exceptions are division by zero, and the most negative value divided by $-1$, which is undefined.

**Question 1.17 ★★ QD, Dev, LLE, QR • any • junior, experienced.**

Given $n$ numbers and a window size $k$, return the largest number in each run of $k$ consecutive numbers. The running time must be proportional to $n$, however large $k$ is. What do you return for `[1, 3, 2, 5, 4, 1]` with $k = 3$? One step of your loop may do a lot of work, so how do you justify that running time?

**Answer to Question 1.17.**

Keep a deque of positions whose values strictly decrease, as in [Listing 1.17](#lst-iv3-al-winmax). The front is always the window’s maximum. The example returns `[3, 5, 5, 5]`.

```python
def window_max(xs, k):
    out = []
    q = deque()                       # positions, with their values strictly decreasing
    for i, x in enumerate(xs):
        while q and xs[q[-1]] <= x:   # x outlives and beats these: never a maximum again
            q.pop()
        q.append(i)
        if q[0] <= i - k:             # the front has slid out of the window
            q.popleft()
        if i >= k - 1:
            out.append(xs[q[0]])
    return out
```

***Listing 1.17.** A monotone deque. code/interviews-3/01-algorithms/python/iv_window_max.py*

When `x` arrives, any older value that is no larger can never be a maximum again: `x` is at least as big and leaves the window later. So those values are popped from the back. Then the front is dropped if it has slid out. What remains is decreasing, and its first value is the largest in the window.

A single step can pop up to $k$ entries, which is why the bound per step looks like $k$. The right count is over the whole run: each position is pushed once and popped at most once, so all the `while` loops together do at most $n$ pops. The total is $O(n)$, amortised, for any $k$, with $O(k)$ memory.

**Classic wrong answer.** A heap of the window. It works with lazy deletion, but stale entries pile up: on a rising list none reaches the root, so it costs $O(n \log n)$ and $O(n)$ memory. Even $O(n \log k)$ would be ruled out by the question.

**Follow-up.** *The largest minus the smallest in each window?* Run two deques, one for the maximum and one for the minimum, and subtract.

**Follow-up.** *A window of the last 60 seconds of a stream, rather than the last $k$ items?* The same deque, holding timestamps too: evict from the front by time. Memory is then bounded by the number of events inside the time span, not by a constant you chose.

**Question 1.18 ★★ QD, Dev, QR • any • junior, experienced.**

A list of integers can contain negative values. Count the contiguous stretches of the list whose sum is exactly $T$, in time proportional to the length of the list on average. For `[1, -1, 1]` and $T = 1$, what is the count? Why does a window with two pointers, which grows while the sum is below $T$ and shrinks while it is above, not work here?

**Answer to Question 1.18.**

Use prefix sums and a hash map, as in [Listing 1.18](#lst-iv3-al-subsum). A stretch from $i$ to $j$ sums to $T$ exactly when $\text{prefix}_j - \text{prefix}_{i} = T$, so at each $j$ you count how many earlier prefixes equal $\text{prefix}_j - T$. It takes $O(n)$ average time and $O(n)$ memory, and the example has 3 such stretches.

```python
from collections import Counter


def count_sum(xs, target):
    seen = Counter({0: 1})        # the empty prefix
    prefix = count = 0
    for x in xs:
        prefix += x
        count += seen[prefix - target]
        seen[prefix] += 1         # after the lookup, so an empty span never counts
    return count
```

***Listing 1.18.** Counting prefix sums seen so far. code/interviews-3/01-algorithms/python/iv_subarray_sum.py*

For `[1, -1, 1]`, the prefixes are 0, 1, 0, 1. The three stretches are the first element, the last element and the whole list. The counter starts with one empty prefix, so that a stretch beginning at position 0 counts, and the current prefix goes in after the lookup, so that with $T = 0$ an empty stretch does not count.

**Classic wrong answer.** Two pointers. Growing and shrinking relies on the sum rising when the window grows and falling when it shrinks, which needs values that are never negative. With a negative value, a window above $T$ may come back to $T$ if you grow it further. On this example it counts only 2 of the 3, since it holds one window per end, while the last position ends two stretches that sum to 1.

**Follow-up.** *Stretches whose sum is divisible by $m$?* Keep prefixes modulo $m$, and count earlier equal ones. Mind the sign: take the residue into $0, \dots, m-1$, which Python’s `%` does for you and C++’s does not.

**Follow-up.** *The memory is a problem and all values are positive. Now what?* Then two pointers are right, with $O(1)$ extra memory.

**Question 1.19 ★★ QD, Dev, LLE • any • junior, experienced.**

Each order has an integer open time and a later integer close time, and it is alive at time $t$ when $\text{open} \le t < \text{close}$. Given $n$ orders, in no particular order, find the largest number alive at once and the first time that number is reached, in $O(n \log n)$ time. What do you return for the two orders $(1, 2)$ and $(2, 3)$?

**Answer to Question 1.19.**

Sort the opens and closes together as events and sweep, as in [Listing 1.19](#lst-iv3-al-alive). At equal times, closes must come before opens. It takes $O(n \log n)$ time and $O(n)$ memory. For the two orders, the answer is 1, first reached at time 1.

```python
def peak_alive(orders):
    """orders: (open, close), alive for open <= t < close. Returns (peak, first time)."""
    events = []
    for start, end in orders:
        events.append((start, +1))
        events.append((end, -1))
    events.sort()                 # at equal times -1 sorts first: closes before opens
    alive = peak = 0
    when = None
    for t, delta in events:
        alive += delta
        if alive > peak:
            peak, when = alive, t
    return peak, when
```

***Listing 1.19.** A sweep over opens and closes. code/interviews-3/01-algorithms/python/iv_alive.py*

Between events the count does not change, so its peak is reached at an event, and the first time it rises to the peak is an open. The tie-break is where the half-open rule lives. An order closing at 2 is no longer alive at 2, so it must leave before an order opening at 2 enters. Here that needs nothing extra: Python sorts tuples by their second field on a tie, and $-1$ sorts below $+1$.

**Classic wrong answer.** Processing opens first at equal times. The example then counts 2 at time 2, though the two orders are never alive together.

**Follow-up.** *And if the orders already arrive sorted by open time?* Keep a min-heap of the closing times of orders alive. Before each open, pop those with a close no later than it, and the heap’s size is the count. It still costs $O(n \log n)$ in the worst case, but it needs memory only for orders alive at once, so it works on a stream.

**Follow-up.** *Times are integers in a small range $0, \dots, R$?* Add $+1$ at each open and $-1$ at each close in an array of size $R + 1$, then take a running sum: $O(n + R)$, with no sort.

**Question 1.20 ★★ QD, Dev, QR, DS • any • junior, experienced.**

You have $n$ trades, each a symbol, a price and a quantity, with $m$ distinct symbols. Return the $k$ symbols with the largest total notional (price times quantity), largest first, breaking ties by symbol name. Give a solution that costs less than sorting all $m$ symbols when $k$ is small. What goes wrong if trades keep arriving and you must answer at any moment?

**Answer to Question 1.20.**

Add up the notional per symbol in a hash map, then take the top $k$ with a heap of size $k$, as in [Listing 1.20](#lst-iv3-al-topk). It takes $O(n)$ average time to total and $O(m \log k)$ to select, with $O(m)$ memory.

```python
import heapq
from collections import Counter


def top_k(trades, k):
    """trades: (symbol, price, qty). The k largest notionals, ties broken by symbol name."""
    notional = Counter()
    for symbol, price, qty in trades:
        notional[symbol] += price * qty
    return heapq.nsmallest(k, notional.items(), key=lambda item: (-item[1], item[0]))
```

***Listing 1.20.** Totals, then a bounded heap. code/interviews-3/01-algorithms/python/iv_top_k.py*

`heapq.nsmallest` with key `(-notional, symbol)` keeps a heap of the $k$ best candidates so far. If you write the heap by hand, it is a min-heap of notional, whose root is the weakest candidate kept: each new symbol either replaces the root or is thrown away. The tie-break must then be reversed in that heap, because the root has to be the worst, which here means the later name. That inversion is the usual bug. For $k$ close to $m$, sorting is simply better, and `quickselect` finds the top $k$ set in $O(m)$ on average, if the order within them does not matter.

For trades `AAA 100 3`, `BBB 50 10`, `CCC 300 1`, `AAA 100 2` and `DDD 10 1`, the top three are AAA 500, BBB 500 and CCC 300.

If trades keep arriving, the heap breaks, because a symbol’s total changes while it sits in the heap, or while it sits outside it, and a heap cannot find and raise an entry. One fix is an ordered set of (notional, symbol), plus the map: each trade removes and reinserts one entry, for $O(\log m)$ per trade, and reading the top $k$ costs $O(k)$. Another is to push a new entry per update and discard stale ones when they reach the root.

**Classic wrong answer.** “A heap of size $k$ works on the stream too.” Once a symbol has been dropped from the heap, its running total is what decides whether it comes back, so you still need all the totals and a way to compare against the current root at every trade.

**Question 1.21 ★★ QD, Dev, LLE • market maker, crypto, hedge fund • junior, experienced.**

In Python, you have $K$ feeds, each an iterator of `(timestamp, message)` pairs in time order, where each message is a dictionary. Write a generator that yields all pairs in time order. At equal timestamps the feed with the lower number goes first, and it may hold only one pair per feed in memory. What does it cost for $N$ pairs in all? What happens to your generator when one feed goes quiet for an hour?

**Answer to Question 1.21.**

Keep a heap with one entry per feed, holding that feed’s next pair, as in [Listing 1.21](#lst-iv3-al-merge). It costs $O(N \log K)$ in time and $O(K)$ in memory. If one feed goes quiet, the generator stops yielding as soon as that feed’s turn comes, and waits: it cannot know whether an older message is still on its way.

```python
import heapq


def merge_feeds(feeds):
    """feeds: iterators of (timestamp, message), each in time order. Yields the merge."""
    its = [iter(f) for f in feeds]
    heap = []
    for n, it in enumerate(its):
        head = next(it, None)
        if head is not None:
            heap.append((head[0], n, head[1]))   # n breaks ties: messages never compared
    heapq.heapify(heap)
    while heap:
        ts, n, message = heap[0]
        yield ts, message
        head = next(its[n], None)
        if head is None:
            heapq.heappop(heap)
        else:
            heapq.heapreplace(heap, (head[0], n, head[1]))
```

***Listing 1.21.** A heap with one entry per feed. code/interviews-3/01-algorithms/python/iv_merge_feeds.py*

The smallest remaining timestamp is always at the head of some feed, so it is in the heap. After yielding it, you read that feed’s next pair and replace the root, which costs $\log K$. Since a feed has at most one entry in the heap, the pair (timestamp, feed number) is unique, so Python never has to compare two messages.

The generator reads only what it must, so it works on endless feeds: merging one feed ticking every 2 with another ticking every 3 gives 2, 3, 4, 6, 6, with the lower-numbered feed first at the tie.

The quiet feed is the real-world part. A merge in time order can emit a message only when every feed has shown it something later, so the slowest feed sets the pace. The usual fix is a heartbeat, which each feed sends with its current time so that the others can advance, or a timeout after which you mark a feed stale and go on without it, at the price of possible disorder when it comes back.

**Classic wrong answer.** Pushing `(timestamp, message)`. It seems to work until two messages share a timestamp. Python then compares the dictionaries and raises `TypeError`.

**Follow-up.** *Concatenate and sort?* $O(N \log N)$ and all of $N$ in memory, which fails on a stream.

**Question 1.22 ★★ QD, Dev, QR, DS • any • junior, experienced.**

Numbers arrive one at a time. Design a class with `add(x)` and `median()`, where `median` is the middle value, or the mean of the two middle values when the count is even. Say what each method costs. What would you change if every value is an integer number of ticks between 0 and 1000?

**Answer to Question 1.22.**

Keep two heaps, as in [Listing 1.22](#lst-iv3-al-median): a max-heap for the smaller half and a min-heap for the larger half, with sizes that differ by at most one. Then `add` is $O(\log n)$ and `median` is $O(1)$, with $O(n)$ memory. With integer ticks in 0 to 1000, keep an array of 1001 counts instead.

```python
import heapq


class StreamMedian:
    def __init__(self):
        self.low = []             # the smaller half, negated: a max-heap
        self.high = []            # the larger half: a min-heap

    def add(self, x):
        heapq.heappush(self.low, -heapq.heappushpop(self.high, x))
        if len(self.low) > len(self.high):
            heapq.heappush(self.high, -heapq.heappop(self.low))

    def median(self):
        if len(self.high) > len(self.low):
            return self.high[0]
        return (self.high[0] - self.low[0]) / 2
```

***Listing 1.22.** Two heaps. code/interviews-3/01-algorithms/python/iv_median_stream.py*

The median sits at the boundary between the two halves, so only the two roots matter. Each `add` pushes through `high` first, so that the smallest of the larger half moves across, then moves one back if `low` has grown too large. That single route keeps both rules true without a special case: every value in `low` is at most every value in `high`, and `high` holds the extra one when the count is odd. Python’s `heapq` has only a min-heap, so `low` stores negated values, and the even case reads $(\text{high}_0 - \text{low}_0) / 2$. For the values 5, 1, 9, 3 it gives 4.

With a bounded range, an `add` is one increment, $O(1)$. The median can then be found by walking the counts, or kept with a pointer that moves as values arrive; the memory is a constant 1001 counters, however long the stream runs. That is a real saving, since the heaps hold every value for ever.

Before the first `add` there is no median, and the listing raises `IndexError`: say that this is your choice.

**Classic wrong answer.** Keeping a sorted list with binary search. The search is $O(\log n)$, but the insert moves up to $n$ items, so a stream costs $O(n^2)$. It is fine for small $n$, and worth saying so.

**Follow-up.** *And if old values must leave as well?* A heap cannot remove from the middle, so that is a harder problem: a sliding median. You need lazy deletion or a balanced tree.

**Question 1.23 ★★ QD, Dev, QR, DS • any • junior, experienced.**

A stream of unknown length passes once. Keep exactly $k$ items in memory, so that when the stream ends each $k$-subset of what passed is equally likely to be the one you hold. Write the function and prove it, at least for the probability that a given item is kept.

**Answer to Question 1.23.**

Keep the first $k$ items. Then the item at 0-based position $i$ replaces a uniformly chosen slot with probability $k/(i+1)$, as in [Listing 1.23](#lst-iv3-al-reservoir). This is reservoir sampling: $O(n)$ time and $O(k)$ memory, and every $k$-subset is equally likely.

```python
def reservoir(stream, k, rng):
    sample = []
    for i, x in enumerate(stream):        # i items came before x
        if i < k:
            sample.append(x)
        else:
            j = rng.randrange(i + 1)      # uniform on 0..i, so P(j < k) = k / (i + 1)
            if j < k:
                sample[j] = x
    return sample
```

***Listing 1.23.** Reservoir sampling. code/interviews-3/01-algorithms/python/iv_reservoir.py*

The proof goes by induction on the number of items seen, $i$. Suppose after $i$ items each is held with probability $k/i$. Item $i+1$ enters with probability $k/(i+1)$, as the code says. An earlier item survives that step unless the newcomer enters and picks its slot, so it is held with probability

$$
\frac{k}{i}\Bigl(1 - \frac{k}{i+1} \cdot \frac{1}{k}\Bigr) = \frac{k}{i} \cdot \frac{i}{i+1} = \frac{k}{i+1}.
$$

The base case is $i = k$, where all are held. The test checks this identity exactly, and goes further: for $n = 5$ and $k = 2$ it enumerates all 60 equally likely sequences of draws, and each of the 10 subsets appears exactly 6 times. A seeded simulation agrees: with 20 items and $k = 5$, each is kept about a quarter of the time. All 20 agree to within about one percentage point, over 40 000 runs.

**Classic wrong answer.** Replacing with probability $1/(i+1)$, the rule for $k = 1$. The last item is then kept with probability $1/n$, where it should be $k/n$.

**Follow-up.** *And if items have weights?* Give item $i$ the key $u_i^{1/w_i}$, with $u_i$ uniform on 0 to 1, and keep the $k$ largest keys in a heap. For $k = 1$, item $i$ survives with probability $w_i / \sum_j w_j$; the simulation agrees, for weights 1, 2 and 5.

**Question 1.24 ★★ QD, Dev, LLE • any • junior, experienced.**

In C++20, write a cache with a fixed capacity and two operations: `get(key)` returns the value if present, and `put(key, value)` inserts or overwrites. When it is full, inserting a new key discards the key used longest ago, where both `get` and `put` count as use. Both operations must take constant time on average. Why would `std::vector` or `std::deque` not do for the recency order?

**Answer to Question 1.24.**

Use a doubly linked list in recency order, and a hash map from key to the list iterator, as in [Listing 1.24](#lst-iv3-al-lru). `splice` relinks a node to the front in $O(1)$, without touching any iterator. So both operations are $O(1)$ on average, and memory is $O(\text{capacity})$.

```cpp
template <class K, class V>
class Lru {
public:
    explicit Lru(std::size_t capacity) : capacity_(capacity) {}

    std::optional<V> get(const K& key) {
        auto it = where_.find(key);
        if (it == where_.end()) return std::nullopt;
        items_.splice(items_.begin(), items_, it->second);  // relinks: iterators stay valid
        return it->second->second;
    }

    void put(const K& key, V value) {
        if (capacity_ == 0) return;
        if (auto it = where_.find(key); it != where_.end()) {
            it->second->second = std::move(value);
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        if (items_.size() == capacity_) {
            where_.erase(items_.back().first);
            items_.pop_back();
        }
        items_.emplace_front(key, std::move(value));
        where_[key] = items_.begin();
    }

private:
    std::size_t capacity_;
    std::list<std::pair<K, V>> items_;  // most recently used at the front
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> where_;
};
```

***Listing 1.24.** A list and a map of its iterators. code/interviews-3/01-algorithms/cpp/lru.hpp*

Three things must all be cheap: finding a key, moving it to the front, and removing the oldest. The hash map gives the first, and the list gives the other two. The map stores iterators, which is safe only because `std::list` never invalidates an iterator to a surviving element, and `splice` does not either. A `std::vector` would shift elements on every move, costing $O(n)$. A `std::deque` can only push and pop at its ends, so moving from the middle costs $O(n)$ too, and inserting at the ends invalidates all its iterators.

The test runs random operations against a slow model in Python, under AddressSanitizer and UndefinedBehaviorSanitizer too, and they agree. The eviction removes the map entry before popping the node, because the key is read out of the node. Note that `get` writes: it changes the list.

**Classic wrong answer.** “Timestamp each entry and scan for the oldest.” Reads are fast, and eviction is $O(n)$. A heap of timestamps also fails, because each `get` would have to change a key inside the heap.

**Follow-up.** *Is this thread-safe if readers use a shared lock?* No, since `get` moves a node, so readers need exclusive access. Under contention, split the cache into shards with one lock each, or update recency in batches.

**Follow-up.** *The list’s nodes are scattered in memory. Does that matter?* Each step can be a cache miss, plus one allocation per insert. A hot-path version holds nodes in a fixed array and links them by integer index, with the same logic.

**Question 1.25 ★★ QD, Dev, LLE • any • junior.**

A singly linked list may end in a cycle, so that following the pointers never reaches an end. With constant extra memory, decide whether it does and return the node where the cycle begins. Explain why your second phase lands exactly on that node.

**Answer to Question 1.25.**

Run Floyd’s two pointers, as in [Listing 1.25](#lst-iv3-al-cycle): one moves one step at a time, the other two. If they meet, there is a cycle. Then put one back at the head and move both one step at a time: they meet at the start of the cycle. It takes $O(n)$ time and $O(1)$ memory.

```python
def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:              # they met inside the cycle
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None
```

***Listing 1.25.** Two speeds, then the same speed. code/interviews-3/01-algorithms/python/iv_cycle.py*

Let the tail before the cycle have $a$ nodes, and let the cycle have length $c$. Say they meet after the slow pointer has walked $s$ steps. The fast one has walked $2s$, and the extra $s$ steps must be a whole number of laps, so $s$ is a multiple of $c$. The meeting point is $s$ steps from the head. Walking $a$ more steps from there reaches $s + a$ steps from the head, which is the cycle’s start and then a whole number of laps. A walker from the head reaches the same node after $a$ steps, so the two meet there, and they cannot meet sooner since the walker is not on the cycle before then.

**Classic wrong answer.** “Store visited nodes in a set.” It is correct and clearest, but it takes $O(n)$ memory, which the stem rules out.

**Follow-up.** *How long is the cycle?* After they meet, hold one still and walk the other round until it comes back, counting.

**Question 1.26 ★★ QD, Dev, QR • any • junior.**

You have a list of trading halts, each a start and an end time, in no order, and two that touch or overlap count as one. Return the merged halts in time order, and the total time halted. What do you return for $(8, 10)$, $(1, 3)$, $(10, 12)$, $(2, 6)$? What if halts arrive one at a time and you need the merged list after each?

**Answer to Question 1.26.**

Sort by start, then sweep and extend the last merged halt whenever the next one starts at or before its end, as in [Listing 1.26](#lst-iv3-al-intervals). It returns $(1, 6)$ and $(8, 12)$, for 9 hours in all. It takes $O(n \log n)$ time.

```python
def merge(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return [tuple(x) for x in out]


def covered(intervals):
    return sum(end - start for start, end in merge(intervals))
```

***Listing 1.26.** Sort by start, then extend or begin. code/interviews-3/01-algorithms/python/iv_intervals.py*

After sorting, a new halt cannot overlap anything before the last merged one, because every earlier merged halt ended before the last one began. So one comparison is enough. The `max` matters: a short halt inside a long one, such as $(2, 3)$ after $(1, 6)$, must not shrink the end. The test `start <= end` is where touching halts count as one, and changing it to `<` makes $(8, 10)$ and $(10, 12)$ stay apart.

The total is the sum of the merged lengths, 5 plus 4. Adding the raw lengths gives 2 + 4 + 2 + 2 = 10, which counts the overlap from 2 to 3 twice.

**Classic wrong answer.** Sorting by end time. Then $(1, 10)$ comes after $(2, 3)$ and $(4, 5)$, and a single look back at the last merged halt misses that the long one swallows them all.

**Follow-up.** *And when halts arrive one at a time?* Keep the merged halts in an ordered map from start to end. Find the neighbours by binary search, and absorb the ones that overlap: $O(\log n)$ for the search, and each halt is removed at most once, so the cost is amortised $O(\log n)$ per arrival in a tree.

**Question 1.27 ★★ QD, Dev, QR • any • junior.**

Given a list of daily prices, return for each day the number of days until a strictly higher price, or 0 if none comes. It must run in $O(n)$ time. What do you return for `[100, 101, 103, 99, 97, 100, 104, 101]`? One step may do a lot of work, so why is the total linear?

**Answer to Question 1.27.**

It returns `[1, 1, 4, 2, 1, 1, 0, 0]`. [Listing 1.27](#lst-iv3-al-nextgreater) keeps a monotone stack of the days still waiting for a higher price, and each new price settles every waiting day it beats.

```python
def days_until_higher(prices):
    out = [0] * len(prices)
    waiting = []                      # days with no higher price yet
    for i, p in enumerate(prices):
        while waiting and prices[waiting[-1]] < p:
            j = waiting.pop()
            out[j] = i - j
        waiting.append(i)
    return out
```

***Listing 1.27.** A stack of days still waiting. code/interviews-3/01-algorithms/python/iv_next_greater.py*

The prices on the stack never rise from bottom to top, as any price that beats the top pops it before going on. So if the new price does not beat the top, it beats nothing below either, and the loop can stop.

Take 103 on day 2: it waits while 99, 97 and 100 come in and pile up or pop one another, and it is settled at day 6 by 104, which gives 4.

A single price can pop many entries, so one step can cost a lot. Yet every day is pushed once and popped at most once, so across the whole list the pops number at most $n$: amortised $O(1)$ per day, $O(n)$ in total, and $O(n)$ memory in the worst case.

**Classic wrong answer.** Two nested loops scanning forward. On a falling list every day scans to the end: $n(n - 1)/2$ comparisons.

**Follow-up.** *For each day, how many days in a row, ending today, had a price at or below today’s?* The same stack looked at from the other side: pop everything at or below today’s price, then the span is the distance to the new top. For `[100, 80, 60, 70, 60, 75, 85]` it gives 1, 1, 1, 2, 1, 4, 6.

**Question 1.28 ★★ QD, Dev, QT • any • junior.**

You must send exactly $n$ shares, and each child order must have a size from a fixed list. Find the fewest child orders, and which sizes they are, or report that it cannot be done. With sizes 1, 3 and 4 and $n = 6$, what does taking the largest size that fits give, and what is the true answer? Say what your method costs.

**Answer to Question 1.28.**

Largest-first gives 4, 1, 1, which is three orders, while the true answer is 3, 3, which is two. [Listing 1.28](#lst-iv3-al-clips) uses dynamic programming over quantities, in $O(ns)$ time and $O(n)$ memory for $s$ sizes.

```python
def fewest_clips(sizes, n):
    inf = n + 1
    best = [0] + [inf] * n            # best[q]: fewest clips adding up to exactly q
    used = [0] * (n + 1)
    for q in range(1, n + 1):
        for s in sizes:
            if s <= q and best[q - s] + 1 < best[q]:
                best[q], used[q] = best[q - s] + 1, s
    if best[n] == inf:
        return None
    clips = []
    while n:
        clips.append(used[n])
        n -= used[n]
    return clips
```

***Listing 1.28.** Fewest orders for each quantity. code/interviews-3/01-algorithms/python/iv_clips.py*

An exact fill of $q$ ends with some last size $s$, and what comes before it is an exact fill of $q - s$. So `best[q]` is one more than the smallest `best[q - s]`. Recording the size chosen at each $q$ gives back the list by walking down. If no combination works, `best[n]` keeps its sentinel, and with sizes 2 and 4 the function returns nothing for $n = 5$.

Note that $ns$ is not polynomial in the input’s length, because $n$ is written in about $\log n$ bits. On the whiteboard the question is rarely large enough to care, but say so if $n$ can be $10^9$.

**Classic wrong answer.** “Largest first is optimal, like making change.” It holds for some size lists, such as 1, 5, 10 and 25, and it fails for this one, and largest-first can also fail to finish at all: with sizes 3 and 4, 6 has the answer 3, 3, yet largest-first takes 4 and gets stuck at 2.

**Follow-up.** *How many ways are there, if order does not matter?* Loop over the sizes outside and the quantities inside, so that each combination is counted once: there are 4 ways for sizes 1, 3, 4 and $n = 6$.

**Question 1.29 ★★ QD, Dev, QR, QT • any • junior, experienced.**

You have a list of daily prices, and may hold at most one share at a time. You may buy and sell as often as you like, and each completed round trip costs a fee $f$. Return the largest total profit in $O(n)$ time and constant memory. What do you get for `[10, 13, 12, 18, 14, 19]` with $f = 2$? What does your method return with no fee, and with a fee of a million?

**Answer to Question 1.29.**

The answer is 9: buy at 10 and sell at 18 for 6, then buy at 14 and sell at 19 for 3. [Listing 1.29](#lst-iv3-al-tradefee) keeps two numbers, the best wealth while flat and while holding, updated once per day. With no fee it returns the sum of all the rises, here 14; with a fee of a million it returns 0.

```python
def max_profit_with_fee(prices, fee):
    flat, holding = 0, float("-inf")  # the best wealth so far, not holding and holding
    for p in prices:
        holding = max(holding, flat - p)
        flat = max(flat, holding + p - fee)
    return flat
```

***Listing 1.29.** Two states, one pass. code/interviews-3/01-algorithms/python/iv_trade_fee.py*

At the close of each day you are either flat or holding one share, and each state’s best wealth depends only on yesterday’s two values. To hold today, you held already or you buy from flat. To be flat today, you were flat already or you sell and pay the fee. No trade is ever forced, so `flat` starts at 0 and can only rise, which is why a large fee gives 0 and not a loss.

Update order is safe here: using today’s `holding` in today’s `flat` only allows a buy and a sell at the same price on one day, which loses the fee and so is never chosen.

**Classic wrong answer.** Trading every rise and paying the fee each time. Here that is $(3 - 2) + (6 - 2) + (5 - 2) = 8$, less than 9, as holding through the dip from 13 to 12 saves a fee and gives up only 1 of price.

**Follow-up.** *At most two round trips?* Keep four states instead: holding first, flat after first, holding second, flat after second.

**Question 1.30 ★★ QD, Dev, DS • any • junior.**

You are matching two lists of security names. Write a function for the edit distance between two strings: the fewest single-character insertions, deletions and substitutions that turn one into the other. It should take $O(mn)$ time and only $O(\min(m, n))$ memory. What is the distance from ABCD to ACBD? What do you lose by keeping only one row?

**Answer to Question 1.30.**

The distance from ABCD to ACBD is 2: two substitutions, since there is no swap operation here. [Listing 1.30](#lst-iv3-al-edit) fills the classic table one row at a time, in $O(mn)$ time and $O(\min(m, n))$ memory.

```python
def edit_distance(a, b):
    if len(a) < len(b):
        a, b = b, a                   # keep the shorter one as the row
    row = list(range(len(b) + 1))
    for i, x in enumerate(a, 1):
        diag, row[0] = row[0], i
        for j, y in enumerate(b, 1):
            cost = diag + (x != y)    # substitute, or keep
            diag = row[j]
            row[j] = min(cost, row[j] + 1, row[j - 1] + 1)
    return row[-1]
```

***Listing 1.30.** One row of the table at a time. code/interviews-3/01-algorithms/python/iv_edit.py*

Let $D(i, j)$ be the distance from the first $i$ characters of one string to the first $j$ of the other. The last operation either keeps or substitutes the last characters, which costs 0 or 1 on top of $D(i - 1, j - 1)$, or it deletes one, or inserts one, each 1 on top of the cell above or to the left. The first row and column are the lengths: $D(i, 0) = i$.

Each cell needs only its left neighbour, the cell above, and the diagonal. A single row plus one saved variable, `diag`, holds all three.

The price of one row is that you get the number and not the edits. To recover which edits to make, keep the full table, or use Hirschberg’s divide-and-conquer method, which needs linear memory and about twice the time.

**Classic wrong answer.** Comparing sets or sorted letters. ABCD and ACBD have the same letters, so those methods call them identical.

**Follow-up.** *And if a swap of neighbours costs 1?* Add one more case, from $D(i - 2, j - 2)$, when the two pairs are swapped. ABCD to ACBD then costs 1. This is why name matching often uses that variant.

**Question 1.31 ★★ QD, Dev, QR • any • junior, experienced.**

There are $n$ accounts. Pairs arrive one at a time, each saying that two accounts belong to the same group, and links carry over: if $a$ goes with $b$ and $b$ with $c$, then $a$ goes with $c$. At any moment you must answer whether two accounts are in one group, and how many groups there are. Write it, and say what it costs per operation. What can your structure not do?

**Answer to Question 1.31.**

Use union-find, as in [Listing 1.31](#lst-iv3-al-unionfind): every group is a tree of parent pointers, and two accounts are in one group if they reach the same root. With union by size and path compression, $m$ operations cost $O(m\,\alpha(n))$, where $\alpha$ is the inverse Ackermann function, which is below 5 for any $n$ that fits in memory.

```python
class Groups:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # halve the path
            x = self.parent[x]
        return x

    def link(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a            # the smaller tree goes under the larger
        self.size[a] += self.size[b]
        self.count -= 1

    def same(self, a, b):
        return self.find(a) == self.find(b)
```

***Listing 1.31.** Parent pointers, kept flat. code/interviews-3/01-algorithms/python/iv_union_find.py*

Union by size keeps the trees shallow: an account’s depth grows only when its tree is merged under a larger one, so its tree at least doubles each time, and depth is at most $\log_2 n$. Path halving then flattens what it walks through. The number of groups is a counter that falls by one on each real merge.

What it cannot do is split a group. A link cannot be removed, because the structure forgets which pair made it. If removals are known in advance, process the whole sequence backwards, which turns them into merges.

**Classic wrong answer.** Labelling each account with its group number and relabelling on merge. A `same` check is $O(1)$, and each merge scans $O(n)$. Relabelling only the smaller group gives $O(n \log n)$ for all merges, which is fine for a simple answer, though worse than the trees.

**Follow-up.** *Why not breadth-first search on each query?* It answers correctly at $O(V + E)$ per query. If queries are frequent, that is far too slow.

**Question 1.32 ★★ QD, Dev, QR • any • junior, experienced.**

A nightly batch has $n$ tasks, and a list of pairs $(a, b)$ meaning that $a$ must finish before $b$ starts. Return an order that respects them all, or report that none exists, in time linear in tasks and pairs. Now give the tasks durations, and any number may run at once. Tasks A, B, C and D take 3, 2, 4 and 1 hours, B and C need A, and D needs B and C. When does everything finish?

**Answer to Question 1.32.**

[Listing 1.32](#lst-iv3-al-topo) is Kahn’s topological sort: start from tasks waiting on nothing, and whenever a task finishes, release those waiting only on it. It takes $O(n + e)$ time for $e$ pairs. If some task never gets released, there is a cycle. The batch finishes at hour 8.

```python
from collections import deque


def run_order(n, edges):
    """edges: (a, b) means a before b. Returns an order, or None on a cycle."""
    after = [[] for _ in range(n)]
    waiting = [0] * n
    for a, b in edges:
        after[a].append(b)
        waiting[b] += 1
    ready = deque(i for i in range(n) if waiting[i] == 0)
    order = []
    while ready:
        a = ready.popleft()
        order.append(a)
        for b in after[a]:
            waiting[b] -= 1
            if waiting[b] == 0:
                ready.append(b)
    return order if len(order) == n else None
```

***Listing 1.32.** Releasing tasks as their last dependency ends. code/interviews-3/01-algorithms/python/iv_topo.py*

An order exists exactly when the pairs have no cycle. Each task on a cycle is waiting for another on that cycle, so none of them ever reaches a waiting count of zero. Conversely, if the graph has no cycle, some task always has no unfinished dependencies, so the loop finishes all of them. So comparing the length of `order` with $n$ is the whole cycle test.

With unlimited parallel workers, each task starts when the last of its dependencies ends, so walk the tasks in topological order and take the `max`. A ends at 3. B ends at 5 and C at 7. D starts at 7 and ends at 8. The chain A, C, D is the critical path, and speeding up B changes nothing.

**Classic wrong answer.** “Add up the durations.” That gives 10, which is the time on one worker. It says nothing about the parallel case.

**Follow-up.** *And if only two tasks may run at once?* Scheduling with a limited number of workers is NP-hard in general, so you use a heuristic, such as starting the task with the longest path still ahead of it.

**Question 1.33 ★★ QD, Dev • any • junior.**

A grid of $r$ rows and $c$ columns has some cells walled off. You move one cell at a time, up, down, left or right. Find the fewest moves from a start cell to a goal cell, or report that it cannot be reached. For the rows `..#`, `.#.` and `...` (with `#` a wall), going from top left to bottom right, what is the answer? Why does depth-first search not give it? Does it matter whether you mark a cell when you push it or when you pop it?

**Answer to Question 1.33.**

The answer is 4 moves: down, down, right, right. [Listing 1.33](#lst-iv3-al-grid) uses breadth-first search, in $O(rc)$ time and memory.

```python
from collections import deque


def shortest_path(grid, start, goal):
    """grid: strings, with # for a wall. Returns the number of moves, or None."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            return dist[goal]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if (0 <= nr < len(grid) and 0 <= nc < len(grid[0])
                    and grid[nr][nc] != "#" and (nr, nc) not in dist):
                dist[nr, nc] = dist[r, c] + 1  # marked when pushed, not when popped
                queue.append((nr, nc))
    return None
```

***Listing 1.33.** Breadth-first search with marking on push. code/interviews-3/01-algorithms/python/iv_grid.py*

The queue holds cells in order of distance: everything at distance $d$ comes out before anything at $d + 1$. So the first time a cell is reached is by a shortest route, and it never needs another look. Depth-first search has no such order. On an open grid it can wander along a long route first and mark cells as visited, so the first path it finds says nothing about the shortest, and fixing it means trying all paths.

Marking does matter, for cost rather than for correctness. Marked on pop, a cell can be pushed once by each of its up to four neighbours before it is first popped. It still gives the right distance, but the queue is larger, by up to four times, and each repeat scans its neighbours again.

**Classic wrong answer.** “Use Dijkstra.” It works, and it brings a $\log$ factor for nothing, since every move costs the same.

**Follow-up.** *Some moves cost 0 and some 1?* Use a deque: push a cell reached at cost 0 to the front and one at cost 1 to the back. This keeps the same ordering, with no heap, and is still linear.

**Question 1.34 ★★ QD, Dev, LLE • any • junior, experienced.**

Trading venues are joined by one-way links, each with a latency in microseconds that is never negative. Find the fastest route from one venue to every other, with the route itself, and say what it costs for $V$ venues and $E$ links. With links A to B of 5, A to C of 2, C to B of 1 and B to D of 1, what is the fastest time from A to D, and by which route? What goes wrong if some link has a negative weight?

**Answer to Question 1.34.**

The fastest route from A to D takes 4 microseconds, by A, C, B, D. [Listing 1.34](#lst-iv3-al-dijkstra) is Dijkstra’s algorithm with a binary heap, in $O((V + E) \log V)$ time. The predecessors give the route, walked back from the target.

```python
import heapq


def fastest(links, source):
    """links: {venue: [(next_venue, cost >= 0), ...]}. Returns distances, predecessors."""
    dist, before = {source: 0}, {}
    heap = [(0, source)]
    while heap:
        d, v = heapq.heappop(heap)
        if d > dist[v]:               # a stale entry: v was reached faster since
            continue
        for w, cost in links.get(v, ()):
            if d + cost < dist.get(w, float("inf")):
                dist[w], before[w] = d + cost, v
                heapq.heappush(heap, (d + cost, w))
    return dist, before
```

***Listing 1.34.** Dijkstra with lazy deletion. code/interviews-3/01-algorithms/python/iv_dijkstra.py*

Python’s heap cannot lower a key, so each improvement pushes a new entry, and the entry left behind is skipped when it surfaces. That is the `d > dist[v]` line. The heap then holds up to $E$ entries, which changes nothing in the bound, since $\log E$ is at most $2 \log V$.

The proof rests on non-negative weights: when the smallest entry comes out, nothing still waiting can reach it more cheaply, as any other route passes through an entry at least as large. A negative link breaks this. With A to B of 2, A to C of 3 and C to B of $-2$, the version with a closed set finalises B at 2, while the true answer is 1. The lazy version above does find 1 when a node is revisited, but its running time can then explode, and if a negative cycle is reachable the loop never ends. For negative links use Bellman–Ford, at $O(VE)$.

**Classic wrong answer.** “Breadth-first search.” It finds the fewest links. Here that gives A, B, D at 6 microseconds, with one hop fewer and a worse time.

**Follow-up.** *One target only?* Stop when it comes off the heap. Its distance is final at that moment.

**Question 1.35 ★★ QD, Dev, QR • any • junior, experienced.**

A list of order slices, all with positive sizes, must be sent in the given order over $d$ days, with every day taking a contiguous run of slices. Minimise the largest day’s total. What is the answer for `[4, 9, 3, 7, 8]` with $d = 2$, and with $d = 3$? Find a method faster than trying the cuts, and say why it needs the sizes to be positive.

**Answer to Question 1.35.**

The answer is 16 for $d = 2$, from the split 4, 9, 3 and 7, 8, and 13 for $d = 3$, from 4, 9 and 3, 7 and 8. [Listing 1.35](#lst-iv3-al-splitdays) uses binary search on the answer, in $O(n \log S)$ time, where $S$ is the sum.

```python
def smallest_largest_day(sizes, days):
    def days_needed(cap):
        used, load = 1, 0
        for s in sizes:
            if load + s > cap:
                used, load = used + 1, 0
            load += s
        return used

    lo, hi = max(sizes), sum(sizes)   # no day can hold less than the largest slice
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo
```

***Listing 1.35.** Binary search on the largest day. code/interviews-3/01-algorithms/python/iv_split_days.py*

Turn the question around. Given a cap on each day, can it be done within $d$ days? That has a simple answer: fill each day greedily until the next slice would pass the cap. Taking as much as possible today never hurts, since it leaves less for later. And the answer is monotone: if a cap works, every larger cap works. That is what lets you binary search the cap, between the largest slice and the sum.

Positive sizes are what makes the greedy test right. With a negative slice, adding one more may lower a day’s total, so greedy filling is no longer optimal, and its count can even rise with the cap: on `[8, 2, -5, 8, -1, 4]`, caps 8, 9, 10 and 11 give 2, 2, 3 and 2 days. The binary search then has nothing sound to test. The largest slice is no longer a lower bound either, since a day can hold less than one of its slices.

**Classic wrong answer.** “Aim for the average, sum divided by $d$, and cut when you pass it.” For $d = 2$ the average is 15.5, and cutting before you pass it gives 13 and then 18, so its largest day is 18, against the true 16.

**Follow-up.** *The classic alternative?* Dynamic programming over (position, days used), at $O(n^2 d)$, which also gives the cuts, and is needed if the cost of a day is not the sum.

**Question 1.36 ★★ QD, Dev, QR • any • junior, experienced.**

Find the $k$-th smallest of $n$ numbers in $O(n)$ average time, without sorting them all. Why does your method go quadratic on a sorted list if the pivot is always the first element? What happens on a list where all values are equal, if you partition into “below the pivot” and “not below the pivot”? How do you avoid both?

**Answer to Question 1.36.**

Quickselect: partition around a random pivot, and keep only the side holding position $k$, as in [Listing 1.36](#lst-iv3-al-quickselect). On average that is $O(n)$, because the work falls roughly geometrically. Three groups (below, equal, above) and a random pivot avoid both of the bad cases.

```python
import random


def kth_smallest(xs, k, rng=random):
    """The value with k elements below it in sorted order, k from 0."""
    xs = list(xs)
    lo, hi = 0, len(xs)
    while True:
        pivot = xs[rng.randrange(lo, hi)]
        below = [x for x in xs[lo:hi] if x < pivot]
        equal = sum(1 for x in xs[lo:hi] if x == pivot)
        if k < lo + len(below):
            xs[lo:hi] = below
            hi = lo + len(below)
        elif k < lo + len(below) + equal:
            return pivot
        else:
            above = [x for x in xs[lo:hi] if x > pivot]
            lo += len(below) + equal
            xs[lo:hi] = above
            hi = lo + len(above)
```

***Listing 1.36.** Three groups around a random pivot. code/interviews-3/01-algorithms/python/iv_quickselect.py*

With the first element as pivot on a sorted list, each step removes one element only. Finding the largest of 100 then costs $99 + 98 + \dots + 1 = 4950$ comparisons, which is $n(n-1)/2$.

With all values equal and two groups, every value lands in “not below the pivot”, so again only the pivot leaves at each step, and 100 equal values looking for position 99 cost 4950 comparisons too. The three-way split ends at once, as the whole list is the “equal” group and $k$ falls within it, after one pass.

A random pivot makes the bad path unlikely, whatever the input is, so no adversary and no sorted input can force it. If you must have a worst-case guarantee, median of medians gives $O(n)$ in the worst case, with a larger constant.

**Classic wrong answer.** “Use a heap of size $k$.” That is $O(n \log k)$, which is fine and works on a stream, and it does not meet the average-time bound asked for here.

**Follow-up.** *Is it in place?* The listing copies for clarity. A real version partitions in place, and that is what `std::nth_element` does. It leaves the list reordered, which a caller may not want.

**Question 1.37 ★★ QD, Dev • any • junior.**

Given a list of integers, return every distinct triple of values that adds up to zero, each once, in $O(n^2)$ time. What do you return for `[-2, 0, 1, 1, 2, -1, -1]`? Where do repeats get in, and how do you keep them out without a set of results?

**Answer to Question 1.37.**

It returns $(-2, 0, 2)$, $(-2, 1, 1)$, $(-1, -1, 2)$ and $(-1, 0, 1)$. [Listing 1.37](#lst-iv3-al-threesum) sorts, fixes the smallest value of the triple, and walks two pointers inward on the rest. It takes $O(n^2)$ time and $O(1)$ memory beyond the sort and the output.

```python
def three_sum(xs, target=0):
    xs = sorted(xs)
    out = []
    for i, a in enumerate(xs):
        if i and xs[i - 1] == a:
            continue                  # the same first value gives the same triples
        lo, hi = i + 1, len(xs) - 1
        while lo < hi:
            s = a + xs[lo] + xs[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                out.append((a, xs[lo], xs[hi]))
                lo += 1
                while lo < hi and xs[lo] == xs[lo - 1]:
                    lo += 1
    return out
```

***Listing 1.37.** Sort, fix one value, then two pointers. code/interviews-3/01-algorithms/python/iv_three_sum.py*

For a fixed first value, the pair must add up to its negative. On a sorted range, a sum that is too small can only be fixed by moving the left pointer up, and one too large by moving the right pointer down, so each pointer moves at most $n$ times.

Repeats get in at two places, and the code stops both. Equal first values give the same triples, so all but the first are skipped. And after a hit, equal second values give the same pair again, so `lo` steps past them. The right pointer then needs no extra care: once `lo` has changed value, the same `hi` gives a different sum and moves on.

**Classic wrong answer.** Three nested loops with a set of sorted triples. It is correct, at $O(n^3)$. A set also hides the question of where the repeats came from.

**Follow-up.** *With a hash set in place of two pointers?* Also $O(n^2)$, it works without sorting, but keeping the triples distinct is more awkward, and it takes $O(n)$ extra memory.

**Question 1.38 ★★ QD, Dev, DS • any • junior.**

A tape is a list of symbols, one per trade. Return the length of the longest contiguous stretch holding at most $k$ distinct symbols, in $O(n)$ time. What do you return for the tape A, B, A, C, C, D, D, D with $k = 2$? How would you count the stretches holding exactly $k$ distinct symbols?

**Answer to Question 1.38.**

The answer is 5, for the stretch C, C, D, D, D. [Listing 1.38](#lst-iv3-al-kdistinct) grows a sliding window at the right and shrinks it at the left whenever it holds too many symbols, in $O(n)$ time and $O(k)$ memory.

```python
from collections import Counter


def longest_k_distinct(tape, k):
    count = Counter()
    best = left = 0
    for right, s in enumerate(tape):
        count[s] += 1
        while len(count) > k:
            count[tape[left]] -= 1
            if not count[tape[left]]:
                del count[tape[left]]
            left += 1
        best = max(best, right - left + 1)
    return best
```

***Listing 1.38.** A window with a count per symbol. code/interviews-3/01-algorithms/python/iv_k_distinct.py*

A stretch with at most $k$ distinct symbols contains only such stretches, so the rule is monotone: for each right end, there is a leftmost valid start, and it never moves left as the right end moves right. That is why the pointers only go forward, and each moves at most $n$ times. A symbol’s entry is deleted as its count hits 0, since `len(count)` is what is being compared with $k$.

The window is a valid stretch at every step, so the largest one seen is the answer, and it also gives you the leftmost start for each end: all later starts up to the end are valid too. This gives the follow-up.

**Classic wrong answer.** Counting exactly $k$ with one window directly. When the window holds exactly $k$, it isn’t clear which starts count, as several left ends can give exactly $k$ too.

**Follow-up.** *And counting stretches with exactly $k$ distinct?* At each right end, the number of valid stretches with at most $k$ is `right - left + 1`. Sum those, and take the sum for at most $k - 1$ away from the sum for at most $k$. For the tape above and $k = 2$ this gives 11.

**Question 1.39 ★★ LLE, QD, Dev • market maker, hedge fund, crypto • junior, experienced.**

In C++20, write a hash table from non-zero 64-bit keys to 64-bit values, with linear probing in one flat array of a power-of-two size, that does not allocate after construction. It has `put`, `get` and `erase`. Why is a plain “clear the slot” a wrong `erase`, and what do you do instead? Why does the table have to stay far from full?

**Answer to Question 1.39.**

[Listing 1.39](#lst-iv3-al-flatmap) is such a table, with open addressing. Clearing a slot on `erase` breaks `get`, as a later key that probed past that slot now looks absent. The fix used here is backward-shift deletion: move later entries back into the hole where that is allowed.

```cpp
// Linear probing with backward-shift deletion. The key 0 marks an empty slot.
class FlatMap {
    std::vector<std::uint64_t> keys_, vals_;
    std::size_t mask_;

    std::size_t home(std::uint64_t k) const {
        return (k * 0x9E3779B97F4A7C15ULL >> 20) & mask_;
    }

public:
    explicit FlatMap(std::size_t power_of_two)
        : keys_(power_of_two), vals_(power_of_two), mask_(power_of_two - 1) {}

    void put(std::uint64_t k, std::uint64_t v) {       // k != 0, and the table never fills
        std::size_t i = home(k);
        while (keys_[i] != 0 && keys_[i] != k) i = (i + 1) & mask_;
        keys_[i] = k;
        vals_[i] = v;
    }
    std::optional<std::uint64_t> get(std::uint64_t k) const {
        for (std::size_t i = home(k); keys_[i] != 0; i = (i + 1) & mask_)
            if (keys_[i] == k) return vals_[i];
        return std::nullopt;
    }
    void erase(std::uint64_t k) {
        std::size_t i = home(k);
        while (keys_[i] != k) {
            if (keys_[i] == 0) return;
            i = (i + 1) & mask_;
        }
        for (std::size_t j = (i + 1) & mask_; keys_[j] != 0; j = (j + 1) & mask_) {
            if (((j - home(keys_[j])) & mask_) >= ((j - i) & mask_)) {  // j may move to i
                keys_[i] = keys_[j];
                vals_[i] = vals_[j];
                i = j;
            }
        }
        keys_[i] = 0;
    }
};
```

***Listing 1.39.** Flat table with backward shift. code/interviews-3/01-algorithms/cpp/flat_map.hpp*

`get` stops at the first empty slot, which is safe only if no key lies beyond a gap in its probe sequence. After a plain clear, that rule breaks. The usual alternatives are a tombstone, a marker that `get` walks past and `put` may reuse, which needs periodic rehashing because tombstones pile up, or the shift used here. A key at slot `j` can move back to the hole at `i` only if its home slot is not cyclically between them, which is what the distance test checks. With an unsigned type and a mask, the wrap-around needs nothing more.

Being full is a matter of probe lengths. Near load $\alpha$, an unsuccessful lookup with linear probing inspects about $\frac{1}{2}(1 + 1/(1 - \alpha)^2)$ slots. In a simulation at $2^{16}$ slots that is about 2.5 at load 0.5, and about 50 at load 0.9, and at load 1 a search for an absent key never ends here: there is no empty slot to stop at. So keep the load near a half.

**Classic wrong answer.** “Use `std::unordered_map`.” It is correct, but it allocates a node per key, and the cache misses are what this design avoids.

**Question 1.40 ★★ QD, Dev, LLE • any • junior.**

Implement a binary min-heap in an array, with `push`, `pop` and a constructor from $n$ items. Say what each costs. Why does building it by sifting down from the last parent take $O(n)$, while $n$ pushes can take $O(n \log n)$?

**Answer to Question 1.40.**

[Listing 1.40](#lst-iv3-al-heap) holds the tree in an array, with the children of $i$ at $2i + 1$ and $2i + 2$. `push` and `pop` take $O(\log n)$, the minimum is at the root in $O(1)$, and the constructor takes $O(n)$.

```python
class MinHeap:
    def __init__(self, items=()):
        self.a = list(items)
        for i in range(len(self.a) // 2 - 1, -1, -1):
            self._down(i)             # from the last parent up to the root

    def push(self, x):
        self.a.append(x)
        i = len(self.a) - 1
        while i and self.a[i] < self.a[(i - 1) // 2]:
            self.a[i], self.a[(i - 1) // 2] = self.a[(i - 1) // 2], self.a[i]
            i = (i - 1) // 2

    def pop(self):
        top, last = self.a[0], self.a.pop()
        if self.a:
            self.a[0] = last
            self._down(0)
        return top

    def _down(self, i):
        while (child := 2 * i + 1) < len(self.a):
            if child + 1 < len(self.a) and self.a[child + 1] < self.a[child]:
                child += 1
            if self.a[i] <= self.a[child]:
                return
            self.a[i], self.a[child] = self.a[child], self.a[i]
            i = child
```

***Listing 1.40.** An array heap. code/interviews-3/01-algorithms/python/iv_heap.py*

`push` puts the item at the end and swaps it upward. `pop` moves the last item to the root and swaps it downward with the smaller child. Comparing with the smaller child is the point: with the larger, that child could end up above the other one, breaking the order.

The build is linear because of where the work falls. Half the nodes are leaves and sift nothing. A node at height $h$ sifts at most $h$ levels, and there are at most $\lceil n/2^{h+1} \rceil$ nodes at height $h$, so the total is about $\sum_h h\,n/2^{h+1} = n$. Sifting up by pushes is the opposite: most nodes are near the bottom, and each may rise all the way. On a descending list of 1024 items, pushes make 8 204 swaps, while the build makes 1 015.

**Classic wrong answer.** “The build makes $n/2$ calls of cost $\log n$, so it is $O(n \log n)$.” That is a true upper bound, not a tight one. It ignores that most calls are near the bottom and cheap.

**Follow-up.** *How do you lower a key already in the heap?* Keep a map from item to its position, updating it at each swap, then sift up. An array heap has no way to find an item otherwise.

**Question 1.41 ★★ QD, Dev, LLE • any • junior, experienced.**

In a list of order IDs, every ID appears exactly twice except two, which appear once. Find those two in $O(n)$ time and constant extra memory. What do you return for `[4, 7, 4, 9, 7, 2]`? What if every ID appears three times except one?

**Answer to Question 1.41.**

It returns 9 and 2. [Listing 1.41](#lst-iv3-al-twosingles) XORs everything to get $a \oplus b$, picks a bit on which they differ, and XORs again over just the IDs with that bit set. It takes $O(n)$ time and $O(1)$ memory.

```python
def two_singles(ids):
    both = 0
    for x in ids:
        both ^= x                     # the pairs cancel, leaving a ^ b
    low = both & -both                # a bit on which a and b differ
    a = 0
    for x in ids:
        if x & low:
            a ^= x                    # the pairs cancel in this half too
    return a, both ^ a
```

***Listing 1.41.** XOR, split on one bit, XOR again. code/interviews-3/01-algorithms/python/iv_two_singles.py*

XOR cancels pairs, so the first pass leaves $9 \oplus 2$, binary $1001 \oplus 0010 = 1011$, which is 11. That is not 0 because the two differ. A set bit of it, here the lowest, `both & -both`, which gives 1, splits the IDs into two groups. Each ID that appears twice falls in one group with its twin and cancels again, and the two singles fall in different groups, by the choice of the bit. So the XOR of one group is one of the singles, and $a \oplus b \oplus a$ gives the other.

The trick `x & -x` works because negation in two’s complement flips all bits above the lowest set bit and keeps that bit.

**Classic wrong answer.** Using the sum and the XOR together. The two facts do not determine the pair: 1 and 6, 2 and 5, and 3 and 4 all have sum 7 and XOR 7. Splitting on a bit is what gives a proof.

**Follow-up.** *Every ID three times except one?* XOR cannot cancel three copies. Count each bit position modulo 3: a remainder of 1 means that the single has that bit. That is $O(32n)$ time with constant memory, and it gives 5 for `[7, 7, 7, 5, 9, 9, 9]`.

**Question 1.42 ★★ QD, Dev, LLE • market maker, crypto, bank • junior, experienced.**

An exchange accepts at most $N$ messages in any window of $T$ seconds. Write `allow(now)`, with times that never go down, so that you never break the limit. With $N = 2$ and $T = 10$, and a window that holds times above `now - T` up to `now`, what do you answer for times 0, 1, 10, 10 and 11? Why is a counter reset every $T$ seconds not enough, and how does a token bucket compare?

**Answer to Question 1.42.**

The answers are yes, yes, yes, no, yes. [Listing 1.42](#lst-iv3-al-ratelimit) keeps the times of the accepted messages still inside the window. That costs $O(N)$ memory and amortised $O(1)$ time, and it never breaks the limit.

```python
from collections import deque


class Limiter:
    """At most n accepted messages in any half-open time span of width t."""

    def __init__(self, n, t):
        self.n, self.t = n, t
        self.accepted = deque()

    def allow(self, now):             # times never go down
        while self.accepted and self.accepted[0] <= now - self.t:
            self.accepted.popleft()
        if len(self.accepted) == self.n:
            return False
        self.accepted.append(now)
        return True
```

***Listing 1.42.** An exact sliding window. code/interviews-3/01-algorithms/python/iv_rate_limit.py*

At time 10, the message at 0 has left the window, so 1 and 10 fill it, and the second message at 10 is refused. At 11 the message at 1 has left, so there is room again. Refused messages are not stored, as they did not reach the exchange.

A counter reset every $T$ seconds looks right, and yet it can double the rate at a boundary. With a reset at time 10, messages at 9, 9, 10 and 10 all pass, which is 4 inside a window of 2 seconds, against a limit of 2. What breaking the limit costs you is the venue’s own rule, so read its specification.

A token bucket keeps only a balance and a time, so it uses $O(1)$ memory, and that suits a hot path. But the bucket allows a full burst of $N$ plus refill, so at a rate of $N/T$ it can send up to about $2N$ in a window of $T$, unless you size it down to stay under the exchange’s rule: $N/2$ of each is the usual way to make it safe.

**Classic wrong answer.** “Delay rather than refuse.” That is a separate choice, made after this check. A queue of delayed orders must also be cancellable, so that you do not send a price that has gone stale.

**Question 1.43 ★★ QD, Dev, DS • any • junior.**

Write a store with `set(key, value, t)` and `get(key, t)`, where `get` returns the value with the latest time at or before $t$, or nothing. For each key, times arrive in increasing order. What does each call cost? What changes if times can arrive out of order? How would you join two sorted time series this way in linear time?

**Answer to Question 1.43.**

Keep, for each key, a growing array of times and one of values. `set` appends, at amortised $O(1)$, and `get` is a binary search at $O(\log m)$ for $m$ entries under that key, as in [Listing 1.43](#lst-iv3-al-asof). The memory is proportional to all the writes.

```python
from bisect import bisect_right
from collections import defaultdict


class AsOfStore:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key, value, t):     # times increase for each key
        self.times[key].append(t)
        self.values[key].append(value)

    def get(self, key, t):
        i = bisect_right(self.times.get(key, ()), t)  # a read adds no key
        return self.values[key][i - 1] if i else None
```

***Listing 1.43.** Binary search over each key’s times. code/interviews-3/01-algorithms/python/iv_as_of.py*

`bisect_right` returns the position after the last time at or before $t$, so the entry just before it is the answer, and a position of 0 means there is none. A value set at exactly $t$ counts as “at or before”, and choosing `bisect_left` there is the usual bug: it returns the previous value. For example, with values at 1 and 3, `get` at 3 gives the second and `get` at 2 gives the first.

Out-of-order times break the cheap append. `bisect.insort` keeps the order, and each insert costs $O(m)$ for the shift, which is fine if late arrivals are rare and land near the end. If they are common, use an ordered map, at $O(\log m)$ for both. In either case, say what an insert does to an answer already given: a query for a past time can now return a different value, and research code that needs replays must also store when each value was learned.

**Classic wrong answer.** “Scan back from the end.” It is fine for a query at the latest time, and it is linear for any old one.

**Follow-up.** *Joining two sorted series as of each trade?* Walk both with two pointers, carrying the last quote seen, at $O(m + n)$: no binary search at all. Trades at 1, 2 and 5 with quotes at 2 and 4 get none, the quote at 2, and the quote at 4.

**Question 1.44 ★★ QD, Dev • any • junior.**

Design a set of order IDs with `insert`, `remove` and `pick`, where `pick` returns an ID uniformly at random. All three must take constant time on average. Why is a hash set on its own not enough? What is the classic bug in `remove`?

**Answer to Question 1.44.**

Keep a list of the items plus a dictionary from item to position, as in [Listing 1.44](#lst-iv3-al-randomset). `pick` takes a uniform position in the list. All three operations are $O(1)$ on average.

```python
import random


class RandomSet:
    def __init__(self):
        self.items, self.where = [], {}

    def insert(self, x):
        if x in self.where:
            return False
        self.where[x] = len(self.items)
        self.items.append(x)
        return True

    def remove(self, x):
        if x not in self.where:
            return False
        i, last = self.where.pop(x), self.items.pop()
        if last != x:                 # move the last element into the hole
            self.items[i] = last
            self.where[last] = i
        return True

    def pick(self, rng=random):
        return self.items[rng.randrange(len(self.items))]
```

***Listing 1.44.** A list and a dictionary of positions. code/interviews-3/01-algorithms/python/iv_random_set.py*

A hash set alone has no way to name its $i$-th element, so a uniform pick needs a scan, or else a random walk across buckets, which favours elements that are alone in a bucket. A list alone picks well, and it needs a scan to remove.

The trick for removal is that the list has no need to stay in order. Moving the last element into the hole costs one step and leaves no gap.

The classic bug is at the end of the list. If $x$ is the last element, a naive version pops the last and writes it back into position $i$, which is now past the end, and that either raises an error or leaves a stale entry behind. Here `last != x` guards it. The other classic bug is to forget to update the moved element’s position in the dictionary.

Uniformity is checked by simulation in the test: after a random sequence of inserts and removes, each of the items still in the set comes out with about the same frequency.

**Follow-up.** *And if each item has a weight?* The list no longer helps. With fixed weights, use the alias method. If they change, a tree of partial sums gives $O(\log n)$ per operation.

**Question 1.45 ★★ QD, Dev, QR • any • junior.**

Write a shuffle of $n$ items that makes all $n!$ orders equally likely, in place and in $O(n)$ time, given a uniform random integer function. A colleague instead swaps each position with a uniformly chosen position from the whole list. For three items, how many equally likely random outcomes does that give, and why can it not be fair?

**Answer to Question 1.45.**

[Listing 1.45](#lst-iv3-al-shuffle) is the Fisher–Yates shuffle, which draws each position only from the part not yet fixed. The colleague’s version has $3^3 = 27$ equally likely outcomes, and 27 is not divisible by the $3! = 6$ orders, so it cannot be fair.

```python
import random


def shuffle(xs, rng=random):
    for i in range(len(xs) - 1, 0, -1):
        j = rng.randrange(i + 1)      # from the part not yet fixed, i included
        xs[i], xs[j] = xs[j], xs[i]
```

***Listing 1.45.** Fisher–Yates, from the end. code/interviews-3/01-algorithms/python/iv_shuffle.py*

Fisher–Yates makes $n$ choices, then $n - 1$, and so on down to 2: that is $n!$ equally likely paths in all, one for each order, so each order comes out with probability $1/n!$. The last position gets each item with probability $1/n$, and then the same is true of what remains.

For the colleague’s version, count by enumeration. Starting from `1, 2, 3`, the order 1, 3, 2 comes up 5 times out of 27, as do 2, 1, 3 and 2, 3, 1. The orders 1, 2, 3 and 3, 1, 2 and 3, 2, 1 come up 4 times each. So the bias is $5/27$ against $4/27$. It does not fade for larger $n$, since $n^n$ is never divisible by $n!$ for $n \ge 3$: $n - 1$ divides $n!$ and shares no prime factor with $n^n$.

**Classic wrong answer.** “Attach a random key to each item and sort.” It is fair if the keys never tie, but it costs $O(n \log n)$. A comparator that returns a random answer is not fair, and it can break the sort.

**Follow-up.** *Is one random generator enough for a large $n$?* A 64-bit state has only $2^{64}$ sequences, and $21!$ is already more than that, so most orders of even a short deck cannot come up.

**Question 1.46 ★★ QD, Dev • any • junior.**

A binary tree holds distinct keys. Decide whether it is a valid binary search tree: everything in each node’s left subtree is smaller than the node, and everything in its right subtree is larger. Why does comparing each node only with its two children fail? Give a tree that passes that check and is not valid. What about a tree 100 000 levels deep?

**Answer to Question 1.46.**

Walk the tree carrying the open range each key must lie in, as in [Listing 1.46](#lst-iv3-al-bst). Going left sets a new upper limit, and going right a new lower limit. It takes $O(n)$ time, and $O(h)$ memory for a tree of height $h$. A stack in place of recursion handles 100 000 levels.

```python
def is_bst(node, low=None, high=None):
    """node: (key, left, right) or None. Every key must lie strictly between its limits."""
    stack = [(node, low, high)]
    while stack:
        n, lo, hi = stack.pop()
        if n is None:
            continue
        key, left, right = n
        if (lo is not None and key <= lo) or (hi is not None and key >= hi):
            return False
        stack.append((left, lo, key))
        stack.append((right, key, hi))
    return True
```

***Listing 1.46.** Each node inside a range from above. code/interviews-3/01-algorithms/python/iv_bst.py*

The condition is on whole subtrees, and a node’s direct children do not cover that. Take root 5, with left child 1, with right child 6, and 6 has left child 4. Each node is correct compared with its children, and yet 4 sits in the right subtree of 5, so the tree is invalid. In the listing, by the time you reach 4, its range is from 5 to 6, and 4 falls outside it.

The other classic route is an in-order walk, which must visit the keys in strictly increasing order. It needs only the previous key and is correct, and it takes the same time and memory.

Recursion in Python stops near a depth of 1000 by default, and in C++ a tree that deep can overflow the stack, depending on its size. That is why the listing keeps its own stack.

**Classic wrong answer.** “Compare with the children”, which accepts the tree above. It is the most common wrong answer, since it looks right on every valid tree drawn on a board.

**Follow-up.** *The $k$-th smallest key?* Walk in order and stop after $k$ keys: $O(h + k)$. If this is asked often, keep each subtree’s size in its node, for $O(h)$.

**Question 1.47 ★★ QR, QD, DS • hedge fund, market maker, bank • junior, experienced.**

Write a class that takes a stream of floats and returns the running mean and sample variance, in constant time and memory per value. Why not simply keep the count, the sum and the sum of squares? What does that give in double precision for the four values $10^9 + 4$, $10^9 + 7$, $10^9 + 13$ and $10^9 + 16$, whose true sample variance is 30? How do you handle an exponentially weighted version?

**Answer to Question 1.47.**

[Listing 1.47](#lst-iv3-al-welford) is Welford’s method: it updates the mean and the sum of squared gaps from it, in $O(1)$ per value. On the four values it gives 30. The count, sum and sum of squares method gives $-170.67$ in double precision, a negative variance.

```python
class RunningStats:
    def __init__(self):
        self.n, self.mean, self.m2 = 0, 0.0, 0.0

    def add(self, x):
        self.n += 1
        d = x - self.mean
        self.mean += d / self.n
        self.m2 += d * (x - self.mean)

    def variance(self):               # the sample variance, for n >= 2
        return self.m2 / (self.n - 1)
```

***Listing 1.47.** Welford’s update. code/interviews-3/01-algorithms/python/iv_welford.py*

The formula $(\sum x^2 - (\sum x)^2/n) / (n - 1)$ subtracts two numbers near $4 \times 10^{18}$, which is far above $2^{53}$, so doubles there are about 512 apart. The difference is near 90, so what is left is mostly rounding error. Welford’s works on gaps from the current mean, which are small, so little is lost. The product $d \times (x - \text{mean})$ uses the mean before and after the update, and it is never negative, so the sum stays non-negative.

A check at the extreme: if all values are equal, each gap is 0, so the variance is exactly 0, whatever their size.

**Classic wrong answer.** “Subtract the first value from everything.” It helps on this example, but it needs that value kept, and a stream that drifts away from it brings the problem back.

**Follow-up.** *And exponentially weighted?* With decay $\lambda$, let $d = x - \text{mean}$. Then $\text{mean} \mathrel{+}= (1 - \lambda)\,d$ and $\text{var} = \lambda(\text{var} + (1 - \lambda)\,d^2)$. Each is $O(1)$, and no window is kept.

**Follow-up.** *And a window of the last $k$?* Keep the $k$ values too, and undo the oldest by the reverse update. Rounding builds up, so recompute from time to time.

**Question 1.48 ★★ LLE, QD, Dev • market maker, crypto, hedge fund • junior, experienced.**

A column of integer prices moves by small steps. Store it as differences, each difference mapped to an unsigned integer by the zigzag rule (0, $-1$, 1, $-2$ become 0, 1, 2, 3) and written as a varint (seven bits per byte, with the top bit set on all bytes but the last, lowest bits first). Write the encoder and decoder. How many bytes does `[1000, 1001, 999, 1300]` take? Why zigzag at all?

**Answer to Question 1.48.**

[Listing 1.48](#lst-iv3-al-varint) encodes the differences 1000, 1, $-2$ and 301. They become 2000, 2, 3 and 602 by zigzag, which take 2, 1, 1 and 2 bytes: 6 bytes in all, against 32 for four plain 64-bit integers.

```python
def encode(values):
    out, last = bytearray(), 0
    for v in values:
        d = v - last
        last = v
        z = 2 * d if d >= 0 else -2 * d - 1   # zigzag: 0, -1, 1, -2 become 0, 1, 2, 3
        while z >= 0x80:
            out.append(z & 0x7F | 0x80)
            z >>= 7
        out.append(z)
    return bytes(out)


def decode(data):
    out, last, z, shift = [], 0, 0, 0
    for b in data:
        z |= (b & 0x7F) << shift
        shift += 7
        if b < 0x80:
            last += z // 2 if z % 2 == 0 else -(z + 1) // 2
            out.append(last)
            z, shift = 0, 0
    return out
```

***Listing 1.48.** Differences, zigzag and varint. code/interviews-3/01-algorithms/python/iv_varint.py*

A varint spends one byte for values below 128, and one more for each further seven bits. So 2 and 3 fit in one byte each, while 602 needs two, because it is at or above 128 and below 16 384.

Zigzag exists for small negative values. Written as a 64-bit two’s complement number, $-2$ has its top bits set, so as an unsigned varint it takes ten bytes, the longest of all. Zigzag folds the number line, so that a small magnitude gives a small code whatever the sign, and $-2$ takes a single byte.

The decoder reverses each step: read seven bits at a time until a byte with a clear top bit, undo the zigzag, add to the running value. If a price is unchanged, the difference is 0, a single byte of 0. So the method is at its best on quiet prices.

**Classic wrong answer.** “Compress with a general compressor instead.” It helps, and it is complementary, as differences make the data more compressible. It also costs far more per message, and it does not allow decoding a single value cheaply.

**Follow-up.** *What does one corrupt byte do?* It breaks every later value, since each depends on the running total. Column formats write a full value at the start of each block, so that damage stays local and you can seek.

**Question 1.49 ★★★ QD, Dev, LLE • market maker, crypto, hedge fund • junior, experienced.**

A market receives buy and sell orders, each with an ID, a price and a quantity. In C++20, write a structure that can add an order, cancel an order by its ID, and return the best bid and best offer with the total quantity at each. State what each operation costs, with $L$ the number of price levels. Duplicate IDs and cancels of unknown IDs must be refused. There is no matching: the two sides simply sit there.

**Answer to Question 1.49.**

Use one ordered map per side, from price to a level holding total quantity and order count, and a hash map from ID to the order and an iterator to its level, as in [Listing 1.49](#lst-iv3-al-book). Adding costs $O(\log L)$, since it may need to find or create the level. Canceling is $O(1)$ on average, and the best price is $O(1)$.

```cpp
enum class Side { Bid, Ask };
struct Level { long qty = 0; long orders = 0; };
struct Top { long price; long qty; };

class Book {
public:
    bool add(long id, Side side, long price, long qty) {
        if (qty <= 0 || orders_.count(id)) return false;
        auto level = levels_[idx(side)].try_emplace(price).first;
        level->second.qty += qty;
        level->second.orders += 1;
        orders_.emplace(id, Order{side, qty, level});
        return true;
    }
    bool cancel(long id) {
        auto it = orders_.find(id);
        if (it == orders_.end()) return false;
        const Order& o = it->second;
        o.level->second.qty -= o.qty;
        if (--o.level->second.orders == 0) levels_[idx(o.side)].erase(o.level);
        orders_.erase(it);
        return true;
    }
    std::optional<Top> best_bid() const {
        return top(levels_[0].crbegin(), levels_[0].crend());
    }
    std::optional<Top> best_ask() const {
        return top(levels_[1].cbegin(), levels_[1].cend());
    }
private:
    using Levels = std::map<long, Level>;
    struct Order { Side side; long qty; Levels::iterator level; };
    static int idx(Side s) { return s == Side::Bid ? 0 : 1; }
    template <class It> static std::optional<Top> top(It first, It last) {
        if (first == last) return std::nullopt;
        return Top{first->first, first->second.qty};
    }
    Levels levels_[2];                         // price -> level; iterators survive inserts
    std::unordered_map<long, Order> orders_;   // id -> where the order sits
};
```

***Listing 1.49.** A book of levels and an index of orders. code/interviews-3/01-algorithms/cpp/book.hpp*

The ID map is what makes cancels cheap. A cancel names only the ID, so without it you would search every level. Storing the map iterator goes one step further: there is no second lookup by price, since iterators into a `std::map` survive inserts and erases of other keys. Erasing through an iterator is amortised constant by the standard, and it is safe to remove the level when its last order leaves, so an empty level never shows up as the best. Reading the best uses `begin` on the ask side and `rbegin` on the bid side, each constant time.

Prices and quantities are integers, as a floating-point price is a poor map key. The tests run 500 random operations at a time against a brute-force model in Python, including repeated IDs and unknown cancels, and also under AddressSanitizer.

**Classic wrong answer.** A priority queue of prices. Best price is fast, but a cancel needs to remove from the middle, which a heap cannot do without lazy deletion. Lazy deletion also leaves stale levels to skip, each time the best is read.

**Follow-up.** *What would you change for a hot path?* Real books have most activity near the top. So a flat sorted array of levels, or an array indexed by ticks around the current price, beats a node-based tree, because it touches fewer cache lines, and the cost is copying on an insert or re-centring on a big move.

**Follow-up.** *What must change for matching?* Each level needs its orders in arrival order, usually an intrusive doubly linked list, so that a fill takes the oldest and a cancel unlinks in $O(1)$.

**Question 1.50 ★★★ QD, Dev, QR, QT • bank, crypto, market maker • junior, experienced.**

You are given a table of exchange rates: for some ordered pairs of currencies $(a, b)$, one unit of $a$ buys $r_{ab}$ units of $b$. An arbitrage is a sequence of conversions that starts and ends in the same currency with more than you began with, and it may take any number of hops. Write a function that returns such a sequence if one exists, and report what it costs for $n$ currencies. Why is checking every triangle not enough?

**Answer to Question 1.50.**

Take the graph with an edge $a \to b$ of weight $-\log r_{ab}$, and find a negative cycle with Bellman–Ford, as in [Listing 1.50](#lst-iv3-al-fx). A product of rates above 1 is a sum of $-\log$ below 0. It costs $O(n \cdot E)$, at most $O(n^3)$ for a full table. Checking triangles is not enough, because a profitable loop may need more hops.

```python
def find_arbitrage(rates, eps=1e-9):
    """rates: {(a, b): units of b for one unit of a}. A cycle [c0, c1, ..., c0] or None."""
    nodes = sorted({c for pair in rates for c in pair})
    edges = [(a, b, -log(r)) for (a, b), r in rates.items()]
    dist = dict.fromkeys(nodes, 0.0)      # as if a hidden source reached every node at cost 0
    prev = {}
    changed = None
    for _ in nodes:                       # a change in round n can only come from a cycle
        changed = None
        for a, b, w in edges:
            if dist[a] + w < dist[b] - eps:
                dist[b] = dist[a] + w
                prev[b] = a
                changed = b
        if changed is None:
            break
    if changed is None:
        return None
    c = changed
    for _ in nodes:                       # n steps back must land on the cycle itself
        c = prev[c]
    cycle, x = [c], prev[c]
    while x != c:
        cycle.append(x)
        x = prev[x]
    cycle.append(c)
    return cycle[::-1]
```

***Listing 1.50.** Bellman–Ford on minus log rates. code/interviews-3/01-algorithms/python/iv_fx_cycle.py*

Starting every distance at 0 acts like a hidden source joined to every node, so a cycle is found wherever it lies. After $n - 1$ rounds, all shortest paths without a negative cycle are settled, so a change in round $n$ can only come from one. Walking back $n$ steps from the changed node is the step people forget: that node may only hang off the cycle, whereas $n$ steps back must be on it. From there you walk until you return.

Take $A \to B$ at 2, $B \to C$ at 2, $C \to D$ at $\tfrac{1}{2}$, $D \to A$ at $\tfrac{3}{5}$, and the diagonals $A \to C$ at 3, $C \to A$ at $\tfrac{1}{5}$, $B \to D$ and $D \to B$ at $\tfrac{4}{5}$. This table has four triangles, whose products are 0.8, 0.9, 0.8 and 0.96, while $A \to B \to C \to D \to A$ multiplies to $2 \times 2 \times \tfrac{1}{2} \times \tfrac{3}{5} = 1.2$. On 600 random tables with up to five currencies, the result agrees with listing every cycle exactly in fractions, and each cycle returned has a product above 1.

The tolerance `eps` matters. Rates of $1/4$, $4/9$ and $9$ multiply to exactly 1, but their floating-point logs add up to about $-4 \times 10^{-16}$, and with no tolerance this function reports that loop as a profit. The price is that a gain below about $10^{-9}$ per hop is ignored. A proportional fee $f$ per conversion adds $-\log(1 - f)$ to each edge: a 10% fee kills this 1.2, since $1.2 \times 0.9^4 < 1$.

**Classic wrong answer.** Dijkstra. Its proof needs non-negative edges, so it neither finds shortest paths here nor detects a cycle.

**Follow-up.** *Does a real desk trade every cycle found?* No. Rates are only indicative for a size, each leg takes time and can move, and a stale quote looks like a profit. So a cycle is a candidate, to be checked against executable prices and sizes.

**Question 1.51 ★★★ QD, Dev, QR • any • junior, experienced.**

Return a longest strictly increasing subsequence of a list of $n$ numbers: not just its length, but the elements themselves, in $O(n \log n)$ time. The elements need not be adjacent. Try your method on `[3, 4, 1]`.

**Answer to Question 1.51.**

Keep `tails[n]`, the smallest value that can end an increasing run of length $n + 1$, and for each element remember its predecessor, as in [Listing 1.51](#lst-iv3-al-lis). It takes $O(n \log n)$ time and $O(n)$ memory. On `[3, 4, 1]`, the answer is `[3, 4]`.

```python
def longest_increasing(xs):
    tails = []                    # tails[n]: smallest last value of a run of length n + 1
    tail_at = []                  # the position of that value
    prev = [-1] * len(xs)         # the element before xs[i] in the best run ending at i
    for i, x in enumerate(xs):
        n = bisect_left(tails, x)
        if n:
            prev[i] = tail_at[n - 1]
        if n == len(tails):
            tails.append(x)
            tail_at.append(i)
        else:
            tails[n] = x
            tail_at[n] = i
    out = []
    i = tail_at[-1] if tail_at else -1
    while i != -1:
        out.append(xs[i])
        i = prev[i]
    return out[::-1]
```

***Listing 1.51.** Smallest tails, with predecessors. code/interviews-3/01-algorithms/python/iv_lis.py*

A smaller tail is never worse, as anything that extends a run ending in 5 also extends one of the same length ending in 3. `tails` is always strictly increasing, so binary search finds where `x` belongs: `x` extends the longest run whose tail is below it. That position gives the length of the best run ending at `x`, and `tail_at[n - 1]` is the element before it, at that moment. So `prev` records a true chain of positions in the original order, and walking it from the last tail gives the answer backwards.

The tests compare length and validity with a search over all subsequences, on 400 random lists.

**Classic wrong answer.** Returning `tails`. On `[3, 4, 1]` it ends as `[1, 4]`, which has the right length but is not a subsequence: the 1 comes after the 4. Overwriting a tail records a better option for later, not the answer so far. That is why you need `prev`.

**Follow-up.** *And for a non-decreasing run?* Use `bisect_right`, so that an equal value extends a run rather than replacing its tail.

**Follow-up.** *Boxes $(w, h)$ that nest only when both are strictly larger?* Sort by $w$ upward, and on equal $w$ by $h$ downward. Then run the same scan on the $h$ values. The downward tie-break stops two boxes of equal width from chaining.

**Follow-up.** *Why not plain dynamic programming?* $O(n^2)$ is simpler, and fine up to a few thousand elements.

**Question 1.52 ★★★ QR, QD, DS • hedge fund, bank • junior, experienced.**

You have two lists of $n$ numbers, paired by position, with all values in each list distinct. Two positions are concordant if the two lists order them the same way, and discordant otherwise. Kendall’s tau is the number of concordant pairs minus the number of discordant pairs, divided by the number of pairs. Compute it in $O(n \log n)$ time, for $n$ near a million. What do you do when values can tie?

**Answer to Question 1.52.**

Sort the positions by the first list. Then the discordant pairs are exactly the inversions of the second list in that order, which a merge sort counts in $O(n \log n)$, as in [Listing 1.52](#lst-iv3-al-kendall). With $P = n(n-1)/2$ pairs and $D$ inversions, $\tau = (P - 2D)/P$.

```python
def sort_count(a):
    """A sorted copy of a, and how many pairs were out of order."""
    if len(a) < 2:
        return a, 0
    mid = len(a) // 2
    left, inv_left = sort_count(a[:mid])
    right, inv_right = sort_count(a[mid:])
    merged, i, j = [], 0, 0
    inversions = inv_left + inv_right
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inversions += len(left) - i   # right[j] is below everything left in `left`
    return merged + left[i:] + right[j:], inversions


def kendall_tau(xs, ys):
    order = sorted(range(len(xs)), key=xs.__getitem__)
    _, discordant = sort_count([ys[i] for i in order])
    pairs = len(xs) * (len(xs) - 1) // 2
    return (pairs - 2 * discordant) / pairs
```

***Listing 1.52.** Counting inversions while merging. code/interviews-3/01-algorithms/python/iv_kendall.py*

With the first list sorted, a pair is discordant exactly when the second list is out of order at those two positions. During the merge, when an element of `right` is taken ahead of the elements still in `left`, it forms an inversion with each of them, all at once, and this is why the count is not quadratic. For `[1, 2, 3, 4]` and `[1, 3, 2, 4]` there is 1 inversion among 6 pairs, so $\tau = 2/3$. The tests agree with an $O(n^2)$ count and with SciPy on 200 random cases.

With ties, sort by $(x, y)$, so a pair tied in $x$ is ordered by $y$ and is never counted as an inversion, and a pair tied in $y$ is not an inversion either, since the comparison is $\le$. Then count $t_x$, $t_y$ and $t_{xy}$, the pairs tied in $x$, in $y$ and in both, and use the tie-corrected form

$$
\tau_b = \frac{C - D}{\sqrt{(P - t_x)(P - t_y)}}, \qquad C = P - t_x - t_y + t_{xy} - D.
$$

The test’s version agrees with SciPy’s default on tied data as well.

**Classic wrong answer.** Using a 32-bit integer for the counts in C++. For $n = 100\,000$, there are already 4 999 950 000 pairs, more than $2^{31}$.

**Follow-up.** *Why not a Fenwick tree?* It works too: rank-compress the $y$ values, and for each one count how many earlier ones exceed it. It is also $O(n \log n)$, and it adapts to pairs arriving in $x$ order if the $y$ values are known in advance or lie in a small range. Otherwise use a balanced tree with subtree counts.

**Question 1.53 ★★★ QD, Dev, LLE, DS • market maker, crypto, hedge fund • experienced.**

A stream of $n$ symbols passes once, with $n$ not known in advance, and you may keep only $k - 1$ counters. Output a set of at most $k - 1$ symbols that is sure to contain every symbol occurring more than $n / k$ times. Write it, say what it costs per item, and prove the guarantee. How wrong can your counters be? For $k = 2$, what well-known problem is this?

**Answer to Question 1.53.**

Keep up to $k - 1$ counters. A known symbol adds one, a new symbol takes a free counter, and if none is free, decrement every counter and drop any at zero, as in [Listing 1.53](#lst-iv3-al-heavy). This is the Misra–Gries summary. It costs $O(1)$ per item amortised. Each counter undercounts its symbol by at most $n/k$. For $k = 2$ it is majority vote.

```python
def heavy_hitters(stream, k):
    """At most k - 1 counters. Every item seen more than n / k times is among the keys."""
    counts = {}
    for x in stream:
        if x in counts:
            counts[x] += 1
        elif len(counts) < k - 1:
            counts[x] = 1
        else:                     # x and k - 1 others each lose one: k units cancel
            for y in list(counts):
                counts[y] -= 1
                if counts[y] == 0:
                    del counts[y]
    return counts
```

***Listing 1.53.** Cancelling different symbols together. code/interviews-3/01-algorithms/python/iv_heavy.py*

The proof counts cancellations. Each decrement round removes one unit from each of $k - 1$ counters, and throws away one unit for the arriving symbol. That is $k$ units gone, all of different symbols, so there are at most $n / k$ such rounds. A symbol loses at most one unit per round, so its true count is at most its counter plus $n / k$. A symbol occurring more than $n/k$ times therefore still has a counter above zero, and is in the output.

The per-item cost: a decrement round walks $k - 1$ counters, but rounds are at most $n / k$, so all of them together cost $O(n)$. The tests check the bound on 500 random streams.

The output can contain false positives. With $k = 2$ the stream `a, b, c` ends with `c` as the candidate, which occurs once in three. If the stream can be replayed, a second pass counts the candidates exactly and removes the false ones.

**Classic wrong answer.** Sampling. It gives an estimate with an error probability, not a guarantee: a heavy symbol can be missed. Keeping one counter per symbol is exact, but its memory grows with the number of symbols, not with $k$.

**Follow-up.** *How do you report the error on a count?* The true count lies between the counter and the counter plus $R$, the number of decrement rounds. You need no extra state to find $R$: each round removes $k$ units, so $R = (n - \sum \text{counters}) / k$, and it is often far below $n / k$.

**Question 1.54 ★★★ QD, Dev, QR, QT • any • junior, experienced.**

You have a list of $n$ daily prices and may make at most $k$ round trips, holding one share at a time. Return the largest total profit in $O(nk)$ time. What do you get for `[4, 2, 7, 6, 1, 5]` with $k = 1$ and with $k = 2$? What does it become when $k$ is very large, and when does a large $k$ let you skip the table altogether?

**Answer to Question 1.54.**

With $k = 1$ the answer is 5, from 2 to 7, and with $k = 2$ it is 9, adding 1 to 5. [Listing 1.54](#lst-iv3-al-ktrades) keeps two numbers for each count of round trips, in $O(nk)$ time and $O(k)$ memory. Once $k \ge n/2$, the answer is the sum of all the rises, which here is 9 too.

```python
def max_profit_k(prices, k):
    if k >= len(prices) // 2:         # enough round trips to take every rise
        return sum(max(0, b - a) for a, b in zip(prices, prices[1:], strict=False))
    flat = [0] * (k + 1)              # flat[j]: best wealth after j completed round trips
    long = [float("-inf")] * (k + 1)  # long[j]: holding, on the way to round trip j
    for p in prices:
        for j in range(1, k + 1):
            long[j] = max(long[j], flat[j - 1] - p)
            flat[j] = max(flat[j], long[j] + p)
    return flat[k]
```

***Listing 1.54.** States by round trips completed. code/interviews-3/01-algorithms/python/iv_k_trades.py*

After each day you are flat with $j$ trips done, or holding on trip $j$. To hold on trip $j$, you already held, or you buy with the wealth of $j - 1$ finished trips. To be flat after $j$ trips, you already were, or you sell today. The inner loop has no conflict: a same-day buy and sell at one price gains nothing.

When $k \ge n/2$, the limit cannot bind. A list of $n$ prices has at most $n/2$ separate rises, so you can take them all, one trip per run of rises. This shortcut matters: $k$ may be given as a billion, and a table with $k$ columns would then not fit in memory.

Limits to check: $k = 0$ gives 0, and so does a falling list, because `flat` starts at 0 and no trade is forced. Each extra trip can only help, so the answer never falls as $k$ grows.

**Classic wrong answer.** “Take the $k$ largest rises.” On `[1, 5, 4, 9]` with $k = 1$, the largest single rise between neighbours is 5, and the true answer is 8, by holding through the dip. Rises must be merged, as well as chosen.

**Follow-up.** *Is there something faster than $O(nk)$?* Yes: merging runs with a heap and a stack gives $O(n \log n)$ regardless of $k$. Say that it exists; few interviewers expect it in full.

**Question 1.55 ★★★ QD, Dev • any • junior, experienced.**

A histogram has bars of width 1 and given heights. Return the largest area of a rectangle lying inside it, in $O(n)$ time. What do you get for `[2, 1, 4, 5, 1, 3, 3]`? Say how equal heights are handled, and why that does not lose a rectangle.

**Answer to Question 1.55.**

The answer is 8, from the bars 4 and 5 at height 4. [Listing 1.55](#lst-iv3-al-histogram) is a monotone stack, in $O(n)$ time and $O(n)$ memory.

```python
def largest_rectangle(bars):
    best = 0
    stack = []                        # positions of rising bars still able to extend right
    for i, h in enumerate([*bars, 0]):
        while stack and bars[stack[-1]] >= h:
            height = bars[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best
```

***Listing 1.55.** A stack of rising bars, with a final 0. code/interviews-3/01-algorithms/python/iv_histogram.py*

The largest rectangle has the height of some bar, the lowest in its span, and it extends left and right until a lower bar stops it. So for each bar, you want the nearest lower bar on each side. The stack keeps positions with rising heights. When a new bar is no higher than the top, the top has met its right limit at $i$, and its left limit is the new top below it, so its full width is known at that moment. The final 0 flushes what is left.

Equal heights: the test is `>=`, so an equal bar pops the earlier one, and the earlier one’s width is then computed too short. That loses nothing: the later bar of that height stays on the stack, and its left limit reaches past the popped bar, so it gets the full width. For `[3, 3]` the first bar computes 3, then the second computes 6.

Every bar is pushed and popped exactly once, so the whole thing is linear even though one step can pop many.

**Classic wrong answer.** Trying every pair of ends and taking the lowest bar. It is correct, at $O(n^2)$, and a divide-and-conquer on the lowest bar is $O(n \log n)$ on average and $O(n^2)$ on a sorted list.

**Follow-up.** *The largest rectangle of ones in a matrix?* Treat each row as the base of a histogram, with heights counting ones upward: $O(rc)$ in all.

**Question 1.56 ★★★ QD, Dev, LLE • any • experienced.**

Write a least-frequently-used cache with a fixed capacity, whose `get` and `put` both take constant time on average. Each `get` or `put` of a key counts as a use. When it is full, a new key evicts the key with the fewest uses, and among those the one whose last use is oldest. With capacity 2, what is left after `put(a)`, `put(b)`, `get(a)`, `put(c)`? Why does a new key reset your record of the lowest count to 1?

**Answer to Question 1.56.**

After those four calls the cache holds a and c: b has one use and a has two, so b goes. [Listing 1.56](#lst-iv3-al-lfu) keeps a map from each frequency to an ordered list of keys, plus the lowest frequency in use, so that everything is $O(1)$ on average.

```python
class LFU:
    def __init__(self, capacity):
        self.cap, self.lowest = capacity, 0
        self.value, self.freq = {}, {}
        self.by_freq = defaultdict(OrderedDict)    # frequency -> keys, oldest use first

    def _leave(self, key):            # an emptied group goes too, or by_freq grows for ever
        f = self.freq[key]
        del self.by_freq[f][key]
        if not self.by_freq[f]:
            del self.by_freq[f]
            if self.lowest == f:
                self.lowest = f + 1
        return f

    def _touch(self, key):
        f = self._leave(key)
        self.freq[key] = f + 1
        self.by_freq[f + 1][key] = True

    def get(self, key):
        if key not in self.value:
            return None
        self._touch(key)
        return self.value[key]

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.value:
            self.value[key] = value
            self._touch(key)
            return
        if len(self.value) == self.cap:
            old = next(iter(self.by_freq[self.lowest]))
            self._leave(old)
            del self.value[old], self.freq[old]
        self.value[key], self.freq[key], self.lowest = value, 1, 1
        self.by_freq[1][key] = True
```

***Listing 1.56.** Keys grouped by use count. code/interviews-3/01-algorithms/python/iv_lfu.py*

A `get` moves its key from the group at $f$ to the group at $f + 1$. An `OrderedDict` removes a known key in $O(1)$ and keeps insertion order, so the front of a group is the oldest use within that count. That is the tie-break the stem asks for.

Why not search for the lowest count? Because of how it can change. It rises only by one at a time, when a touch empties its group: the key moved up to $f + 1$, so that group is non-empty and is the new lowest. A brand new key has count 1, and nothing can be below 1, so it sets `lowest` to 1 whatever it was. These are the only two cases, and no search is ever needed, which is what keeps it constant.

Eviction must come before the new key goes in, or the new key could evict itself, as it has the lowest count of all. An emptied group is deleted at once. Otherwise each new use count leaves an empty one behind, and one key read 100 000 times would leave 100 000 of them, in a cache of fixed capacity.

**Classic wrong answer.** A heap on (count, last use). It costs $O(\log n)$ per operation, which the stem rules out. It also needs lazy deletion, as each touch changes the entry’s key.

**Follow-up.** *What is LFU’s weakness?* A key that was hot long ago keeps a high count and stays forever, while newer ones get evicted. Real caches age or decay the counts, or use a sampled approximation.

**Question 1.57 ★★★ QD, Dev, LLE, QT • market maker, crypto, hedge fund • junior, experienced.**

In Python, write a limit-order matching engine with price-time priority: `submit(id, side, price, quantity)` trades against the opposite side at the resting order’s price, best price first and oldest first within a price, and any remainder rests. `cancel(id)` removes a resting order. IDs are unique. Two sells rest at price 10, first 100 shares and then 50 shares, and a buy for 120 at 11 comes in. What trades print, and what is left? What do the two calls cost?

**Answer to Question 1.57.**

Two trades print at 10: 100 from the first sell and 20 from the second. The second sell keeps 30 resting, and the buy is done. Listings [1.57](#lst-iv3-al-matching) and [1.58](#lst-iv3-al-matchcancel) keep a dictionary from price to a queue on each side, a heap of prices for the best one, and a map from ID to order. A submit costs $O(t + (1 + l) \log L)$, for $t$ trades, $l$ levels touched and $L$ levels in all, and a cancel costs $O(1)$.

```python
class Engine:
    def __init__(self):
        self.levels = {"B": {}, "S": {}}  # side -> price -> queue of [id, remaining]
        self.heaps = {"B": [], "S": []}   # best price first; levels leave lazily
        self.live = {}                    # id -> its [id, remaining]

    def submit(self, oid, side, price, qty):
        other, sign = ("S", 1) if side == "B" else ("B", -1)
        trades = []
        while qty and self.heaps[other]:
            best = sign * self.heaps[other][0]
            queue = self.levels[other].get(best)
            if not queue:                 # an emptied level
                heapq.heappop(self.heaps[other])
                self.levels[other].pop(best, None)
            elif sign * (best - price) > 0:
                break
            elif queue[0][1] == 0:        # cancelled while queued
                queue.popleft()
            else:
                order = queue[0]
                done = min(qty, order[1])
                trades.append((order[0], oid, best, done))
                qty -= done
                order[1] -= done
                if order[1] == 0:
                    queue.popleft()
                    del self.live[order[0]]
        if qty:
            if price not in self.levels[side]:
                self.levels[side][price] = deque()
                heapq.heappush(self.heaps[side], -sign * price)
            self.live[oid] = [oid, qty]
            self.levels[side][price].append(self.live[oid])
        return trades
```

***Listing 1.57.** Price-time priority with lazy cancels. code/interviews-3/01-algorithms/python/iv_matching.py*

```python
    def cancel(self, oid):
        order = self.live.pop(oid, None)
        if order:
            order[1] = 0
        return order is not None
```

***Listing 1.58.** The cancel itself. code/interviews-3/01-algorithms/python/iv_matching.py*

The trade prices at the resting order’s price, 10, and not at the buy’s limit of 11, since the resting order was there first and offered 10. The buy gets the benefit of the better price.

A cancel only marks the order with a remaining quantity of 0 and drops it from the map. The queue skips such entries when they reach the front. Each entry is removed once, so this costs nothing extra, amortised, and it avoids finding the entry inside a list. An emptied level stays in the heap in the same way until it reaches the top, and it goes from the dictionary at that moment, so a price is never in the heap twice.

The stem’s unique IDs matter. A repeated ID would overwrite its entry in the map, and a later fill would raise `KeyError`, so a real engine refuses it at the door.

**Classic wrong answer.** “Keep one sorted list of all orders.” Each insert is then $O(n)$ for the shift, and a book near the touch is exactly where inserts happen.

**Follow-up.** *And a modify that lowers the quantity?* Exchanges usually keep the queue position when the quantity falls, and lose it when the quantity rises or the price changes. A rule like that is a venue’s own, so read its specification.

**Question 1.58 ★★★ QD, Dev, QR • any • junior, experienced.**

Each job has a start, an end and a profit, and two jobs may be taken together only if they do not overlap, with one allowed to start exactly when another ends. Return the largest total profit in $O(n \log n)$ time. What do you get for $(0, 3, 4)$, $(2, 5, 7)$, $(4, 7, 3)$ and $(6, 9, 5)$? Why does taking the most profitable job first fail?

**Answer to Question 1.58.**

The answer is 12, from $(2, 5, 7)$ and $(6, 9, 5)$. [Listing 1.59](#lst-iv3-al-weighted) sorts by end time and uses dynamic programming with binary search, in $O(n \log n)$ time and $O(n)$ memory.

```python
from bisect import bisect_right


def best_total(jobs):
    """jobs: (start, end, profit); a job may start when another ends."""
    jobs = sorted(jobs, key=lambda j: j[1])
    ends = [j[1] for j in jobs]
    best = [0] * (len(jobs) + 1)      # best[i]: using the first i jobs by end time
    for i, (start, _, profit) in enumerate(jobs):
        compatible = bisect_right(ends, start, 0, i)
        best[i + 1] = max(best[i], best[compatible] + profit)
    return best[-1]
```

***Listing 1.59.** Skip the job, or take it. code/interviews-3/01-algorithms/python/iv_weighted_jobs.py*

With jobs sorted by end time, let `best[i]` be the best total using the first $i$ jobs. For job $i$ there are two cases. Skip it, for `best[i]`. Or take it, and then only jobs ending at or before its start can stay. Those are a prefix of the sorted list, so binary search finds where that prefix ends. `bisect_right` is what lets one job start exactly when another ends.

Taking the most profitable first picks $(2, 5, 7)$ here and happens to be right. It fails on $(0, 10, 10)$, $(0, 4, 6)$ and $(5, 9, 6)$: it takes the 10, and the two sixes together earn 12.

Taking the earliest finishers first is the greedy that works when all profits are equal, by an exchange argument, and it is wrong here as well, since on this list it takes $(0, 3, 4)$ then $(4, 7, 3)$, for 7.

**Classic wrong answer.** “Sort by start and recurse on the next job.” It is correct if memoised, but without memoisation it is exponential: each job branches into taking or skipping it.

**Follow-up.** *How would you recover the jobs?* Walk back from the end: if `best[i + 1]` differs from `best[i]`, job $i$ was taken, so jump to its compatible prefix.

**Question 1.59 ★★★ QD, Dev, LLE • market maker, crypto, hedge fund • junior, experienced.**

The bid side of a book is an array of $P$ integer price levels, with a size at each. You need `update(price, delta)`, and `depth(price)`, the total size at that price or better (at or above it), both in $O(\log P)$. Write it. Why does a plain array fail, and why does an array of running totals fail? How would you find the highest price at which depth reaches a given quantity?

**Answer to Question 1.59.**

[Listing 1.60](#lst-iv3-al-fenwick) is a Fenwick tree over the levels. Each update and each prefix sum touches at most about $\log_2 P$ entries, and the depth at a price is the total minus the sum below it. A plain array gives $O(1)$ updates and $O(P)$ queries, and an array of running totals gives the reverse.

```python
class Ladder:
    """Sizes at integer price levels 0..n-1, with sums over the top of the book."""

    def __init__(self, n):
        self.n, self.tree = n, [0] * (n + 1)

    def update(self, price, delta):
        i = price + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def below(self, price):           # total size at prices 0..price-1
        i, total = price, 0
        while i:
            total += self.tree[i]
            i -= i & -i
        return total

    def depth(self, price):           # total size at or above price
        return self.below(self.n) - self.below(price)
```

***Listing 1.60.** A Fenwick tree over price levels. code/interviews-3/01-algorithms/python/iv_fenwick_depth.py*

Entry $i$ of the tree holds the sum of a block of levels whose length is the lowest set bit of $i$. To sum a prefix, start at $i$ and strip that bit: each step takes off a block and moves left. To update, add that bit: each step goes to the next block that covers this level. In both cases $i$ has at most $\log_2 P$ bits to deal with.

With 3 at price 4, 5 at price 7 and 2 at price 9, `depth(7)` is 7, and `depth(5)` is 7 as well, as no size sits at 5 or 6, and `depth(0)` is 10.

To find the highest price at which depth reaches $Q$, the highest-priced side is awkward for a tree that sums from the bottom. So search for the largest $p$ with `below(p)` at most the total minus $Q$, descending by bits over the tree: $O(\log P)$, with no extra binary search on top, as long as no size is negative.

**Classic wrong answer.** “Use a segment tree.” It works, with the same cost and more memory. It wins only if you also need things a Fenwick tree cannot do, such as a range minimum.

**Follow-up.** *And when prices do not fit a small array?* Collect the prices first and compress them to ranks, if you can see them ahead of time. If not, use a balanced tree with subtree sums.

**Question 1.60 ★★★ QD, Dev, LLE • any • experienced.**

Items of a stream arrive one at a time. Given a pattern of $m$ items, report each moment when the last $m$ items equal the pattern, with $O(m)$ memory and amortised constant time per item. On the pattern A, B, A, B and the stream A, B, A, B, A, B, at which positions, counted from 1, do you report? Show why going back to the start of the pattern after each mismatch is wrong, and not merely slow.

**Answer to Question 1.60.**

It reports at positions 4 and 6. [Listing 1.61](#lst-iv3-al-kmp) is Knuth–Morris–Pratt, in streaming form. It uses $O(m)$ memory and amortised $O(1)$ per item, and it reads each item once.

```python
class Watcher:
    """Reports each position in a stream where the last m items equal the pattern."""

    def __init__(self, pattern):
        self.p = pattern
        self.fail = [0] * len(pattern)    # longest proper prefix that is also a suffix
        k = 0
        for i in range(1, len(pattern)):
            while k and pattern[i] != pattern[k]:
                k = self.fail[k - 1]
            k += pattern[i] == pattern[k]
            self.fail[i] = k
        self.k = 0                        # how much of the pattern the stream now ends with

    def push(self, x):
        while self.k and x != self.p[self.k]:
            self.k = self.fail[self.k - 1]
        self.k += x == self.p[self.k]
        if self.k == len(self.p):
            self.k = self.fail[-1]
            return True
        return False
```

***Listing 1.61.** The failure table lets the stream continue. code/interviews-3/01-algorithms/python/iv_kmp.py*

`k` says how many items of the pattern the stream now ends with. On a match, `k` goes up. On a mismatch, the items just read are themselves a prefix of the pattern, so a shorter prefix may still be in play. `fail[k - 1]` is the longest such one, and the code tries again from there.

After a full match, `k` falls back to the longest overlap. That is what finds position 6: A, B at positions 3 and 4 are already the start of the next match. Going back to 0 misses it. So going back to the start is wrong and not merely slow: on the pattern A, A, B and the stream A, A, A, B, restarting after the mismatch at the third A gives no report at all, because by then it holds only one A from the third item, and it misses the true match at positions 2 to 4.

For the cost: `k` rises by at most 1 per item and each fall lowers it by at least 1, and it cannot go below 0, so the falls total at most the rises.

**Classic wrong answer.** “Keep the last $m$ items and compare on each item.” It is correct, at $O(m)$ per item.

**Follow-up.** *And Rabin–Karp?* Keep a rolling hash of the last $m$ items: $O(1)$ per item, on average. It is simpler to write, and needs a comparison on a hit, because hashes can collide. It also handles several patterns of one length with a set.

**Question 1.61 ★★★ QD, Dev, DS • any • junior, experienced.**

A tape is a list of symbols. Given a multiset of required symbols, which may repeat, return the shortest contiguous stretch that contains them all, in $O(n)$ time. For the tape X, A, Y, B, Z, A, C, B and required A, B, C, what is it? What changes if A is required twice? Which count tells you that the window has become valid?

**Answer to Question 1.61.**

The shortest stretch is A, C, B, at positions 5 to 7. If A is required twice, it grows to A, Y, B, Z, A, C, at positions 1 to 6. [Listing 1.62](#lst-iv3-al-minwindow) is a sliding window, in $O(n + r)$ time for $r$ required items.

```python
from collections import Counter


def smallest_window(tape, need):
    """(start, end) of the shortest stretch covering the multiset need, or None."""
    missing = Counter(need)
    short = len(need)                 # how many required items are still uncovered
    best, left = None, 0
    for right, s in enumerate(tape):
        if missing[s] > 0:
            short -= 1
        missing[s] -= 1
        while short == 0:
            if best is None or right - left < best[1] - best[0]:
                best = (left, right)
            missing[tape[left]] += 1
            if missing[tape[left]] > 0:
                short += 1
            left += 1
    return best
```

***Listing 1.62.** Grow to valid, shrink while valid. code/interviews-3/01-algorithms/python/iv_min_window.py*

`missing[s]` is how many more of $s$ the window still needs. It goes negative when the window holds spare ones, and symbols never required start at 0 and go straight below it. `short` counts required items not yet covered, and the window is valid exactly when it reaches 0. It changes only when a `missing` entry crosses zero, which is what handles repeats: the second A lowers `short` only if a second was asked for. The listing assumes at least one required symbol: with none, `short` starts at 0 and the shrinking runs off the end of the tape.

For each right end, the code shrinks from the left while the window stays valid, and records the best. Each position enters and leaves once, so the total is linear. The right end moves on only once the window has gone invalid, and for that end the left pointer has already passed every start that could work, as validity for a longer stretch follows from validity for a shorter one.

**Classic wrong answer.** “Track the set of symbols still missing.” A set cannot tell one A from two, and the stem says the required symbols may repeat. On the second variant it stops at the first valid-looking window, which holds only one A.

**Follow-up.** *And if each symbol has a price and you want the cheapest valid stretch, not the shortest?* If prices are positive, the same window works with a running cost instead of a length, because shrinking still lowers the cost.

**Question 1.62 ★★★ LLE, QD, Dev, DS • market maker, crypto, hedge fund • experienced.**

You want to know whether an order ID has been seen, among 100 million, with less memory than a hash set. Design a Bloom filter: an array of $m$ bits, where each key sets $h$ bits chosen by hashing, and a lookup checks those bits. How many bits and how many hash functions do you need for a 1% false-positive rate? Derive the formula. What kind of error is impossible, and why can you not delete?

**Answer to Question 1.62.**

For 100 million keys at 1%, use about 9.6 bits per key: 958.5 million bits, or about 120 MB, with 7 hash functions. [Listing 1.63](#lst-iv3-al-bloom) is a small version. A false negative is impossible, since adding a key sets all its bits, and bits never clear.

```python
import hashlib
import math


def bloom_size(n, p):
    bits = -n * math.log(p) / math.log(2) ** 2
    hashes = round(bits / n * math.log(2))
    return math.ceil(bits), hashes


class Bloom:
    def __init__(self, n, p):
        self.m, self.k = bloom_size(n, p)
        self.bits = bytearray(self.m // 8 + 1)

    def _slots(self, key):
        h = hashlib.blake2b(str(key).encode(), digest_size=16).digest()
        a, b = int.from_bytes(h[:8], "little"), int.from_bytes(h[8:], "little")
        return ((a + i * b) % self.m for i in range(self.k))

    def add(self, key):
        for s in self._slots(key):
            self.bits[s // 8] |= 1 << (s % 8)

    def might_contain(self, key):
        return all(self.bits[s // 8] >> (s % 8) & 1 for s in self._slots(key))
```

***Listing 1.63.** A Bloom filter from one 128-bit hash. code/interviews-3/01-algorithms/python/iv_bloom.py*

A given bit stays 0 after $n$ insertions with probability $(1 - 1/m)^{hn} \approx e^{-hn/m}$. A false positive needs all $h$ bits set: $p \approx (1 - e^{-hn/m})^h$. Minimising over $h$ gives $h = (m/n)\ln 2$, where half the bits are set. Substituting gives $p = 2^{-h}$, so $m = -n \ln p / (\ln 2)^2$. For $p = 0.01$ that is $9.585\,n$, and $h = 6.64$, rounded to 7.

The test measures it: 20 000 keys in such a filter give a false-positive rate near 1% on 200 000 fresh keys, and halving the bits raises it to about 16%, which fits the formula.

You cannot delete, because a bit may be shared with another key, and clearing it would create false negatives. A counting filter holds a small counter per slot in place of a bit, at about four times the memory.

The two 64-bit hashes in the listing give all seven slots by $a + ib$, a standard way to avoid computing seven hashes.

**Classic wrong answer.** “A false positive means you drop a real order.” Only if you use it that way. Use the filter to skip work on a surely-new ID, and confirm a “maybe” against the store of record.

**Follow-up.** *Compared with a hash set?* A set of 8-byte IDs at load 0.5 takes about 16 bytes per key, or 1.6 GB here, more than ten times as much, with no errors.

**Question 1.63 ★★★ QD, Dev, LLE • market maker, crypto, hedge fund • junior, experienced.**

There are $V$ venues, each with its own best bid, which can move up or down at any time. Write `update(venue, price)` in $O(\log V)$, and `best()`, returning the highest bid and its venue, in $O(1)$. Why does the standard library’s heap not give you this directly? When $V = 8$, would you really use it?

**Answer to Question 1.63.**

[Listing 1.64](#lst-iv3-al-bestvenue) is an indexed heap: an ordinary array heap of venues, plus an array saying where each venue sits. `update` moves its entry up or down in $O(\log V)$, and `best` reads the root in $O(1)$.

```python
class BestBid:
    """An indexed max-heap of venues: pos[v] says where venue v sits in the heap."""

    def __init__(self, n):
        self.bid = [0] * n
        self.heap = list(range(n))
        self.pos = list(range(n))

    def _swap(self, i, j):
        h = self.heap
        h[i], h[j] = h[j], h[i]
        self.pos[h[i]], self.pos[h[j]] = i, j

    def update(self, venue, price):
        self.bid[venue] = price
        i = self.pos[venue]
        while i and self.bid[self.heap[i]] > self.bid[self.heap[(i - 1) // 2]]:
            self._swap(i, (i - 1) // 2)
            i = (i - 1) // 2
        while (c := 2 * i + 1) < len(self.heap):
            if c + 1 < len(self.heap) and self.bid[self.heap[c + 1]] > self.bid[self.heap[c]]:
                c += 1
            if self.bid[self.heap[c]] <= self.bid[self.heap[i]]:
                break
            self._swap(i, c)
            i = c

    def best(self):
        return self.bid[self.heap[0]], self.heap[0]
```

***Listing 1.64.** A heap that knows where each venue sits. code/interviews-3/01-algorithms/python/iv_best_venue.py*

A library heap (`heapq`, `std::priority_queue`) offers `push` and `pop` and nothing else, because it cannot find an entry. Changing a venue’s price needs to start at that venue’s position, and the `pos` array supplies it. Every swap must update it, so all swaps go through one function. A bid can move in either direction, so one loop sifts up and the next sifts down, and at most one of them does anything.

There is also a lazy version: push (price, venue) at each update, and when reading the root, pop any entry whose price is no longer that venue’s current one. It is simple, but the heap grows with updates between reads, and the cost of `best` becomes amortised.

With $V = 8$, I would not use a heap at all. A linear scan of eight numbers in one cache line takes a handful of compares, with no pointer-chasing, and can be vectorised. Or keep the best venue, and rescan only when that venue’s bid falls. The $\log$ only helps once $V$ is large; say what you would measure before choosing.

**Classic wrong answer.** “Sort the venues on each update.” That is $O(V \log V)$ per tick. Moving one out-of-place element costs only $O(V)$ even with a plain insertion.

**Follow-up.** *What about ties?* Say which rule you need. Equal bids at two venues may need venue priority by fees, and then the comparison uses (price, priority).

**Question 1.64 ★★★ QD, Dev, DS • any • experienced.**

You must sort a file of 10 TB of fixed-size records on a machine with 32 GB of memory and one disk that reads or writes 500 MB per second, in sequence. Describe the method. How many sorted runs do you make in the first phase, how many passes does the merge need, and how long does the whole job take if nothing else limits it? Write a small version in Python.

**Answer to Question 1.64.**

Use an external merge sort: make sorted runs that fit in memory, then merge them. With 30 GB of working memory, that gives 334 runs. A single merge pass is enough, and the whole job takes about 22 hours of disk time.

```python
import heapq
import itertools
import pickle
import tempfile


def external_sort(records, memory_items):
    """Sort an iterable holding at most memory_items at a time; yields records in order."""
    runs = []
    it = iter(records)
    while chunk := list(itertools.islice(it, memory_items)):
        chunk.sort()
        run = tempfile.TemporaryFile()
        for r in chunk:
            pickle.dump(r, run)
        run.seek(0)
        runs.append(run)

    def read(f):
        while True:
            try:
                yield pickle.load(f)
            except EOFError:
                return

    yield from heapq.merge(*(read(f) for f in runs))
```

***Listing 1.65.** Runs, then one k-way merge. code/interviews-3/01-algorithms/python/iv_external_sort.py*

*Phase one.* Read 30 GB, sort, write a run. So $10\,000 / 30$ rounds up to 334 runs, and the phase reads and writes 10 TB each.

*Phase two.* Merge with one input buffer per run and one output buffer: a heap on the runs’ heads. With, say, 64 MB per buffer, 334 runs take about 21 GB, which fits. So one pass suffices, and it reads and writes 10 TB again. A second pass would be needed only if the runs outnumbered the buffers.

*Time.* The total is 4 passes of 10 TB, at 500 MB/s. Each takes $10^{13} / (5 \times 10^8) = 20\,000$ seconds, so the total is $80\,000$ seconds, or about 22.2 hours. The sort in memory also takes time, but on this scale the disk dominates.

On a spinning disk, large buffers matter, as they turn a seek per record into a seek per buffer. A binary heap costs at most about $2 \log_2 334 \approx 17$ compares per record, and a loser tree about $8.4$.

**Classic wrong answer.** “Memory-map it and call sort.” A heapsort jumps around in the file, so each compare may be a page fault. Even a quicksort, whose scans are sequential, makes about 8 levels of full reads and writes before a part fits in memory, against the 2 of the merge.

**Follow-up.** *And with many machines?* Partition by key range, chosen from a sample so that the shares are even, send each record to its machine, and sort there. The result is sorted by machine and then within it.

**Question 1.65 ★★★ QD, Dev, QR • any • experienced.**

You must draw items from a fixed list of $n$ items with given weights, millions of times. Binary search on the running total costs $O(\log n)$ a draw. Show a method that costs $O(n)$ to set up and $O(1)$ per draw, using one uniform position and one coin flip. Build its table for weights $\frac{1}{2}$, $\frac{1}{3}$ and $\frac{1}{6}$, and show that it gives the right probabilities.

**Answer to Question 1.65.**

[Listing 1.66](#lst-iv3-al-alias) is the alias method. It splits the probability into $n$ slots of equal total weight, each holding at most two items. A draw picks a slot uniformly, then flips a coin between the two items. For the given weights, slot 0 holds item 0 only, slot 1 holds item 1 only, and slot 2 holds item 2 with probability $\frac{1}{2}$ and item 0 otherwise.

```python
import random


def build(weights):
    n, total = len(weights), sum(weights)
    scaled = [w * n / total for w in weights]
    prob, other = [1] * n, list(range(n))
    small = [i for i, s in enumerate(scaled) if s < 1]
    large = [i for i, s in enumerate(scaled) if s > 1]
    while small and large:
        a, b = small.pop(), large.pop()
        prob[a], other[a] = scaled[a], b     # slot a: item a with prob[a], else item b
        scaled[b] -= 1 - scaled[a]
        (small if scaled[b] < 1 else large if scaled[b] > 1 else []).append(b)
    return prob, other


def draw(prob, other, rng=random):
    i = rng.randrange(len(prob))
    return i if rng.random() < prob[i] else other[i]
```

***Listing 1.66.** Building the table and drawing. code/interviews-3/01-algorithms/python/iv_alias.py*

Scale the weights by $n$, so that the average is 1: here $\frac{3}{2}$, 1 and $\frac{1}{2}$. Any item under 1 fills its own slot partly and takes the remainder from an item above 1, which then loses that amount. This always ends: each step finishes one slot, and if some item is under 1 then another must be above 1, since the average is exactly 1.

So item 2 (scaled $\frac{1}{2}$) fills half of slot 2, and item 0 fills the rest, falling to scaled 1, which completes its own slot.

Check the result. Item 0 is drawn with probability $\frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{1}{2}$. Item 1 gets $\frac{1}{3}$. Item 2 gets $\frac{1}{3} \times \frac{1}{2} = \frac{1}{6}$. All are right, and in the test both an exact sum and a simulation agree. That table comes from exact fractions, as in the test. With floats, $\frac{1}{3} \times 3$ over the total can land just above 1, and the listing then builds another valid table, with the same probabilities.

**Classic wrong answer.** “Build an array of a million entries in proportion to the weights.” It is $O(1)$ per draw, and rounding then distorts small weights, and its memory depends on the precision you want.

**Follow-up.** *And if the weights change?* Setup costs $O(n)$ again. If they change often, use a tree of partial sums, at $O(\log n)$ for both.

**Question 1.66 ★★★ QD, Dev, LLE, QT • market maker, crypto, hedge fund • experienced.**

One price level holds a first-in, first-out queue of orders. Orders join at the back, cancel from anywhere, and trades take shares from the front. You must also say, for any order, how many shares are ahead of it. Give a structure doing all four in $O(\log n)$. After orders of 100, 200 and 300 join, the second cancels, and a trade of 150 occurs, how many shares are ahead of the third? Why not keep a running total on each order?

**Answer to Question 1.66.**

No shares are ahead of the third order, which has 250 left: the trade takes all 100 of the first order and then, since the second has gone, 50 from the third itself. [Listing 1.67](#lst-iv3-al-queuepos) keeps a Fenwick tree over arrival numbers, holding shares resting.

```python
class Level:
    """One first-in, first-out level: a Fenwick tree of shares, by arrival number."""

    def __init__(self, max_orders):
        self.tree = [0] * (max_orders + 1)
        self.slot, self.size = {}, []        # id -> arrival number; arrival number -> shares
        self.front = 0

    def _add(self, i, delta):
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def add(self, oid, qty):
        self.slot[oid] = len(self.size)
        self.size.append(qty)
        self._add(self.slot[oid], qty)

    def cancel(self, oid):
        i = self.slot.pop(oid)
        self._add(i, -self.size[i])
        self.size[i] = 0

    def execute(self, qty):                  # the front of the queue trades first
        while qty and self.front < len(self.size):
            done = min(qty, self.size[self.front])
            self.size[self.front] -= done
            self._add(self.front, -done)
            qty -= done
            if self.size[self.front] == 0:
                self.front += 1

    def ahead(self, oid):                    # shares ahead of this order in the queue
        i, total = self.slot[oid], 0
        while i:
            total += self.tree[i]
            i -= i & -i
        return total
```

***Listing 1.67.** A Fenwick tree over arrival order. code/interviews-3/01-algorithms/python/iv_queue_position.py*

Give each order the next arrival number. The tree stores the shares still resting at each number. A cancel subtracts them, and shares ahead of an order is a prefix sum over earlier numbers. Each costs $O(\log n)$.

A trade walks the queue from the front, reducing each order in turn. It may touch many orders, but each order is emptied at most once, so the cost is amortised $O(\log n)$ per order consumed, plus one for the partial fill.

A running total on each order fails on cancels. If an order ahead of yours leaves, every order behind it must change, and that costs $O(n)$. The tree delays that sum until someone asks.

Arrival numbers grow forever, so a long day needs a bound or a periodic rebuild, which compacts the numbers. The array limit here is `max_orders`, and the test checks it against a plain list on random events.

**Classic wrong answer.** “Shares ahead equals the sum of the orders before it, so walk the list.” That is right, at $O(n)$ per question, and the question usually arrives on every update.

**Follow-up.** *Why would anyone want this number?* A market maker’s estimate of its chance of being filled before the price moves depends on it. It is computed on nearly every update for each resting order.

**Question 1.67 ★★★ QD, Dev, LLE • market maker, crypto, hedge fund • experienced.**

A feed sends book updates over an unreliable channel, each with a sequence number and each setting one price’s size. A second channel sends a snapshot of the whole book from time to time, tagged with the last sequence number it includes. Write the logic that keeps a correct book: joining late, detecting a gap, and recovering. What exactly do you do with an update that arrives while you wait for a snapshot? Which updates must be dropped, and which applied?

**Answer to Question 1.67.**

[Listing 1.68](#lst-iv3-al-snapshot) has two states. While not live, it buffers updates. When a snapshot arrives, it drops buffered updates at or below the snapshot’s sequence number and applies the rest in sequence order, then goes live. While live, it applies the next number and treats anything else as a duplicate or a gap, and it ignores snapshots, which could only rewind the book.

```python
class Recovering:
    """Deltas are (seq, price, new_size); a snapshot is (last_seq, {price: size})."""

    def __init__(self):
        self.book, self.seq, self.buffer = None, None, []

    def on_delta(self, seq, price, size):
        if self.book is None:                    # not live yet: hold until a snapshot arrives
            self.buffer.append((seq, price, size))
            return "buffering"
        if seq <= self.seq:
            return "duplicate"
        if seq != self.seq + 1:                  # a gap: this book can no longer be trusted
            self.book, self.buffer = None, [(seq, price, size)]
            return "gap"
        self._apply(seq, price, size)
        return "ok"

    def on_snapshot(self, last_seq, levels):
        if self.book is not None:                # live: a snapshot could only rewind it
            return True
        book, seq = dict(levels), last_seq
        for s, price, size in sorted(self.buffer, key=lambda u: u[0]):
            if s <= seq:
                continue
            if s != seq + 1:                     # snapshot too old, or a hole in the buffer
                return False
            seq = s
            book[price] = size
            if size == 0:
                del book[price]
        self.book, self.seq, self.buffer = book, seq, []
        return True

    def _apply(self, seq, price, size):
        self.seq = seq
        self.book[price] = size
        if size == 0:
            del self.book[price]
```

***Listing 1.68.** Buffer, apply a snapshot, replay. code/interviews-3/01-algorithms/python/iv_snapshot.py*

The update that arrives while waiting is kept, as the snapshot may be older than it. Dropping it and starting from the snapshot would lose every change between the two. An update at or below the snapshot’s number is already included in the snapshot, so applying it would replay old state: since each update sets a size, applying it could restore a stale size.

The snapshot must also connect: the buffered updates above it must be contiguous from its number plus one. If it is older than the first buffered update, there is a hole, and `on_snapshot` returns false and keeps waiting for the next one. This is why the buffer is kept across failed attempts, and it needs a bound in real code.

On a gap while live, the book is thrown away at once, so that nobody trades on it, and the arriving update starts the buffer. A duplicate from redundant channels, which often arrive as a pair of feeds, is ignored.

A check at the extreme: with no loss, the book never leaves the live state and every update applies in turn. In the test, random loss and reordering against a model always end in the model’s book, or in a declared not-live state, and never in a wrong book.

**Classic wrong answer.** “Apply the snapshot, then apply everything in the buffer.” Stale updates overwrite newer state, and the book looks plausible, with no error, until it trades.

**Follow-up.** *What if a price’s size is sent as a change and not as a new value?* The same logic holds, and any update applied twice is now a wrong size, so a duplicate is more dangerous.

**Question 1.68 ★★★ QD, Dev, DS • any • junior, experienced.**

You have sorted runs of sizes 2, 3, 4 and 10. Merging two runs costs the sum of their sizes, and the merged run takes their place. What is the smallest total cost of merging everything into one run, and what does merging from the largest down cost? Write the method and prove it. What must you add if you merge three runs at a time?

**Answer to Question 1.68.**

The smallest cost is 33, by merging 2 and 3 for 5, then 4 and 5 for 9, and then 9 and 10 for 19. From the largest down, the cost is 50: 14, then 17, then 19. [Listing 1.69](#lst-iv3-al-mergeruns) always merges the two smallest, which is Huffman’s rule, in $O(n \log n)$ time.

```python
import heapq


def merge_cost(sizes):
    heap = list(sizes)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = heapq.heappop(heap) + heapq.heappop(heap)
        total += merged
        heapq.heappush(heap, merged)
    return total


def merge_cost_k(sizes, k):
    heap = list(sizes)
    while (len(heap) - 1) % (k - 1):
        heap.append(0)                # empty runs, so that the last merge is a full one
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = sum(heapq.heappop(heap) for _ in range(k))
        total += merged
        heapq.heappush(heap, merged)
    return total
```

***Listing 1.69.** Always merge the two smallest. code/interviews-3/01-algorithms/python/iv_merge_runs.py*

The merges form a binary tree with the runs at the leaves, and each run’s size is counted once for each merge above it. So the total is the sum of size times depth, and the aim is to put large runs near the root.

The proof is an exchange argument. In an optimal tree, some two leaves at the deepest level are siblings. If the two smallest runs were not at the deepest level, swapping them with what is there could not raise the cost, as the larger size moves up. So some optimal tree has the two smallest as deepest siblings. Merging them gives a smaller problem with one fewer run, whose cost differs by a fixed amount, so induct on the number of runs.

For a merge of three at a time, each merge removes two runs. So you end with one run only if $n - 1$ is even. Otherwise add runs of size 0 first. For the same runs, $n - 1 = 3$ is odd, so add one 0 and take the three smallest each time: $0 + 2 + 3 = 5$, then $4 + 5 + 10 = 19$, for a total of 24. Without the 0, the first merge would have to be a merge of larger runs.

**Classic wrong answer.** “Merging in any order costs the same, since all the data gets merged anyway.” It holds for the bytes in the final run, but not for the work: 33 against 50.

**Question 1.69 ★★★★ QD, Dev, QR • market maker, hedge fund • experienced.**

Given $n$ numbers and a window size $k$, return the median of each run of $k$ consecutive numbers, as the middle value or as the mean of the two middle values. Numbers may repeat. Do better than sorting each window, and code it. What are the time and the memory of your solution? Do they depend on $k$ or on $n$?

**Answer to Question 1.69.**

Use two heaps with lazy deletion, tagging each entry with its position, as in [Listing 1.70](#lst-iv3-al-winmed). It takes $O(n \log n)$ time in the worst case. The memory is $O(n)$ in the worst case, not $O(k)$, because entries that have left the window stay in the heap until they reach its root.

```python
def window_medians(xs, k):
    low, high = [], []            # (-value, i) and (value, i): a max-heap and a min-heap
    in_low = [False] * len(xs)
    live = 0                      # entries of low still inside the window
    out = []

    def top(heap, i):             # drop entries that have left the window, lazily
        while heap and heap[0][1] <= i - k:
            heapq.heappop(heap)
        return heap[0]

    for i, x in enumerate(xs):
        if i >= k and in_low[i - k]:
            live -= 1
        if live and x <= -top(low, i)[0]:
            heapq.heappush(low, (-x, i))
            in_low[i], live = True, live + 1
        else:
            heapq.heappush(high, (x, i))
        want = (min(i + 1, k) + 1) // 2
        while live != want:
            a, b, step = (high, low, 1) if live < want else (low, high, -1)
            v, j = top(a, i)
            heapq.heappop(a)
            heapq.heappush(b, (-v, j))
            in_low[j], live = step > 0, live + step
        if i >= k - 1:
            m = -top(low, i)[0]
            out.append(m if k % 2 else (m + top(high, i)[0]) / 2)
    return out
```

***Listing 1.70.** Two heaps with positions in their entries. code/interviews-3/01-algorithms/python/iv_window_median.py*

The structure is the running median’s: `low` holds the smaller half, and the median is read from the roots. A heap cannot remove from the middle, so an old value is left in place and discarded when it reaches a root. Tagging entries with positions is what makes that safe: the test for staleness is `pos <= i - k`, so duplicates need no special case, whereas a shared count of values to delete must decide which heap’s copy it meant. The counter `live` says how many entries of `low` are really in the window, because `len(low)` no longer does, and `in_low` says which side an expiring value sat on. After each step at most two entries change sides, so the moves per step are bounded.

The heaps can hold nearly all of what has been seen. On a rising series, old values are small, and they sink to the bottom of the max-heap and never surface: the test’s run with $n = 10\,000$ and $k = 5$ held nearly all $10\,000$ entries at its peak. So each heap operation costs $O(\log n)$, not $O(\log k)$, and on an endless stream the memory grows without limit. To cure that, rebuild the heaps from the window when the stale entries outnumber the live ones, which keeps memory at $O(k)$ and the time per step at amortised $O(\log k)$.

**Classic wrong answer.** Claiming $O(n \log k)$ with no rebuild. The tempting bound assumes the heaps hold only the window.

**Follow-up.** *What else would give $O(\log k)$ directly?* A balanced tree with real deletion, or two sorted sets. Or a Fenwick tree over rank-compressed values, with a search for the middle rank: that is $O(n \log n)$ with no stale entries, but offline.

**Follow-up.** *What is simplest in practice?* A sorted array with binary search and a memory move, costing $O(k)$ per step, with a small constant. Measure before you dismiss it for small $k$.

**Question 1.70 ★★★★ QD, Dev, QR • any • experienced.**

A list holds $n$ integers, which may be negative, and $T$ is a positive integer. Return the length of the shortest contiguous stretch whose sum is at least $T$, or report that none exists, in $O(n)$ time. For `[84, -37, 32, 40, 95]` and $T = 167$, what is the answer? Show why your method never discards the right start of a stretch.

**Answer to Question 1.70.**

Take prefix sums $S_0, \dots, S_n$, and scan the ends $j$ with a deque of candidate starts whose $S$ values strictly increase, as in [Listing 1.71](#lst-iv3-al-shortest). Each index goes in and out at most once, so the time is $O(n)$. The example answers 3: the stretch `32, 40, 95` sums to 167.

```python
def shortest_at_least(xs, target):
    """Length of the shortest contiguous span with sum >= target > 0, or None."""
    prefix = [0]
    for x in xs:
        prefix.append(prefix[-1] + x)
    best = None
    q = deque()                       # candidate starts, prefix values strictly increasing
    for j, s in enumerate(prefix):
        while q and s - prefix[q[0]] >= target:
            i = q.popleft()           # no later end can beat this start's shortest span
            if best is None or j - i < best:
                best = j - i
        while q and prefix[q[-1]] >= s:
            q.pop()                   # j is later and no higher: it dominates this start
        q.append(j)
    return best
```

***Listing 1.71.** A monotone deque on prefix sums. code/interviews-3/01-algorithms/python/iv_shortest_sum.py*

We want $j - i$ as small as possible with $S_j - S_i \ge T$. Two rules prune the starts, and each is safe for its own reason.

The first rule drops from the back. If $i < i'$ and $S_i \ge S_{i'}$, then $i$ can never be the best start again: for any later $j$, $i'$ gives a sum at least as large and a shorter stretch. So when $j$ arrives, it removes every candidate with a prefix at least as high.

The second rule drops from the front. If $S_j - S_i \ge T$, then $i$ has found its best end, since any later end makes a longer stretch from the same start. So record $j - i$ and remove $i$. Because $T$ is positive, a start is only ever paired with a later end.

Together these keep the deque increasing, so if the front does not qualify, nothing behind it does, and the `while` loop can stop at the first failure. The tests compare with a full search on 800 random lists with negative values.

**Classic wrong answer.** The sliding window that shrinks from the left while the sum is at least $T$. It is right only when no value is negative. On this example it never reaches the answer 3, because a negative value breaks the rule that shrinking lowers the sum.

**Follow-up.** *And if a heap of prefix sums is all you can recall?* Pop every start satisfying the inequality at each $j$: that costs $O(n \log n)$, and it is correct. Say so, and that the deque improves on it.

**Question 1.71 ★★★★ QD, Dev, QR • any • experienced.**

You are given two sorted lists of lengths $m$ and $n$, not both empty, which may be of very different lengths and may share values. Return the median of all their values together in $O(\log \min(m, n))$ time, as the middle value or as the mean of the two middle values. Now suppose there are many sorted lists, on different machines, and a trillion integers between 0 and $10^9$: how do you find the median?

**Answer to Question 1.71.**

Binary-search the shorter list for how many of its values go on the left of the median split, as in [Listing 1.72](#lst-iv3-al-twomed). That is $O(\log \min(m, n))$ time and $O(1)$ memory. With a trillion integers on many machines, bisect on the value instead, asking each machine how many of its values are at most the candidate.

```python
def median_two(a, b):
    if len(a) > len(b):
        a, b = b, a                   # search the shorter list
    m, n = len(a), len(b)
    half = (m + n + 1) // 2           # how many values the left side must hold
    lo, hi = 0, m
    while True:
        i = (lo + hi) // 2            # i values from a, j from b, on the left side
        j = half - i
        left_a = a[i - 1] if i else -inf
        right_a = a[i] if i < m else inf
        left_b = b[j - 1] if j else -inf
        right_b = b[j] if j < n else inf
        if left_a > right_b:
            hi = i - 1                # took too many from a
        elif left_b > right_a:
            lo = i + 1                # took too few from a
        elif (m + n) % 2:
            return max(left_a, left_b)
        else:
            return (max(left_a, left_b) + min(right_a, right_b)) / 2
```

***Listing 1.72.** Binary search on the split. code/interviews-3/01-algorithms/python/iv_two_medians.py*

Split all the values into a left side of size $\lceil (m + n)/2 \rceil$ and a right side. If $i$ come from $a$, then $j = \text{half} - i$ come from $b$. Each list is sorted, so the split is right exactly when $a_{i-1} \le b_j$ and $b_{j-1} \le a_i$. If $a_{i-1} > b_j$, you took too many from $a$, and the other failure means too few, so the condition tells you which way to move, and the median sits at the boundary. The infinities handle a split at the very end of a list, and searching the shorter list guarantees that $j$ stays in range. The test runs 1000 random pairs, with empty lists and duplicates, against the sorted answer.

For many machines, the two-list trick does not extend neatly. But a median has a simpler characterisation: it is the smallest value $v$ such that at least half of all items are at most $v$. So bisect on $v$ between 0 and $10^9$. Each probe asks each machine for a count, by binary search on its sorted data. That takes about 30 rounds of messages, one per bit of the range, and each round moves a single number per machine, not the data.

**Classic wrong answer.** Averaging the two lists’ medians. For `[1, 2, 3, 4, 5, 6, 7]` and `[100]`, that gives 52, and the true median is 4.5. The classic version, which compares medians and discards halves, works only with equal lengths and careful edges.

**Follow-up.** *The $k$-th smallest of the two lists?* Compare the elements about $k/2$ into each list and discard the prefix ending in the smaller one, since all of it lies below the $k$-th. That takes about $\log k$ steps.

**Question 1.72 ★★★★ QD, Dev, LLE • market maker, crypto, hedge fund • experienced.**

Each bid has an open time, a later close time and a price, and it is in the book on the half-open span from open to close. Given $n$ bids in any order, output the history of the best bid: each time it changes, and its new value, or nothing if the book is empty. It must run in $O(n \log n)$. What do you output for $(0, 5, 10)$, $(1, 3, 12)$, $(2, 4, 11)$ and $(6, 7, 9)$?

**Answer to Question 1.72.**

It returns: at time 0 the price 10, at 1 the price 12, at 3 the price 11, at 4 the price 10, at 5 nothing, at 6 the price 9, and at 7 nothing. [Listing 1.73](#lst-iv3-al-bidhistory) sweeps the event times with a heap of live bids, removing dead ones only when they reach the top, in $O(n \log n)$ time.

```python
import heapq


def best_bid_changes(bids):
    """bids: (open, close, price). Returns (time, best price or None) at each change."""
    events = sorted({t for o, c, _ in bids for t in (o, c)})
    bids = sorted(bids)
    alive, out, i = [], [], 0         # alive: a heap of (-price, close)
    for t in events:
        while i < len(bids) and bids[i][0] == t:
            heapq.heappush(alive, (-bids[i][2], bids[i][1]))
            i += 1
        while alive and alive[0][1] <= t:
            heapq.heappop(alive)      # gone
        best = -alive[0][0] if alive else None
        if not out or out[-1][1] != best:
            out.append((t, best))
    return out
```

***Listing 1.73.** A sweep with a lazy heap. code/interviews-3/01-algorithms/python/iv_best_bid_history.py*

The best bid can only change at an open or a close, so the event times are all that need visiting. At each time, first add the bids that open then, then pop from the top while the top has closed. A dead bid lower down can stay, as it cannot affect the answer until it reaches the top. So each bid is pushed once and popped at most once, and the total is $O(n \log n)$.

The order within a time matters. On a half-open span, a bid closing at $t$ is gone at $t$, and one opening at $t$ is there, and the code achieves this by testing `close <= t`. If a bid closes at 5 and another opens at 5 at the same price, no change is printed, as the comparison with the last value removes it. That’s why you compare before you append: the history would otherwise hold a false change.

This is the skyline problem, in the dress of a book, and the same method solves it. A test against the plain definition, by checking each integer time, runs on random bids.

**Classic wrong answer.** “Sort by price, and paint each bid over time.” Painting is $O(n \cdot \text{span})$, and it is only linear in the span if the times are small integers.

**Follow-up.** *Bids can be cancelled on a live stream, without a known close time?* The same lazy heap works, with a set of cancelled IDs, and with each cancel marking its entry. At any moment the live best is the first top that is not cancelled.

**Question 1.73 ★★★★ QD, Dev, QR • any • experienced.**

A list of $n$ integers may contain negatives. Count the contiguous non-empty stretches whose sum lies between $L$ and $U$ inclusive, in $O(n \log n)$ time. What do you get for `[3, -2, 1, 4]` with $L = 1$ and $U = 3$? Why does a hash map of earlier prefix sums not do it, and why do the pointers in your counting step only move forward?

**Answer to Question 1.73.**

The count is 5. [Listing 1.74](#lst-iv3-al-rangesums) applies merge sort to prefix sums, in $O(n \log n)$ time and $O(n)$ memory: a stretch from $i$ to $j$ has a sum in range exactly when $\text{prefix}_j - \text{prefix}_i$ is, for $i < j$.

```python
def count_in_range(xs, low, high):
    """Stretches of xs whose sum lies in [low, high], by merge sort over prefix sums."""
    prefix = [0]
    for x in xs:
        prefix.append(prefix[-1] + x)

    def go(a):                        # returns a sorted, and the count across its pairs
        if len(a) < 2:
            return a, 0
        left, c1 = go(a[: len(a) // 2])
        right, c2 = go(a[len(a) // 2 :])
        count, i, j = c1 + c2, 0, 0
        for p in left:                # right ends with sums in range, for this left end
            while i < len(right) and right[i] - p < low:
                i += 1
            while j < len(right) and right[j] - p <= high:
                j += 1
            count += j - i
        return sorted(left + right), count

    return go(prefix)[1]
```

***Listing 1.74.** Counting across the two halves of a merge sort. code/interviews-3/01-algorithms/python/iv_range_sums.py*

The prefixes are 0, 3, 1, 2, 6. The stretches with sums from 1 to 3 are `[3]`, `[3, -2]`, `[3, -2, 1]`, `[-2, 1, 4]` and `[1]`, and the other five fall outside.

A hash map answers “how many earlier prefixes equal this value?”, which is the exact-sum question. Here you need how many fall in a range, and a hash map has no order, so each query would scan the range of possible values.

Split the prefixes into a left and a right half. Pairs inside a half are counted by the recursion. For a pair across, both halves are sorted. As `p` grows through the left half, the window of right values with $\text{right} - p \in [L, U]$ moves up, so both pointers only move forward: a total of $O(n)$ per level. The `sorted` on the return is a merge in disguise: Python’s sort finds the two ascending runs and merges them, so it makes $O(n)$ comparisons per level. In another language, write the merge.

**Classic wrong answer.** A sliding window. It relies on sums growing with the window, and negative values break that.

**Follow-up.** *Another route?* Compress the prefix values to ranks, and sweep with a Fenwick tree of the ones seen, counting those in $[\text{prefix} - U, \text{prefix} - L]$. It costs the same, and it needs all the prefixes in advance. On a true stream use a balanced tree with subtree counts.

**Question 1.74 ★★★★ QR, QD, QT • hedge fund, market maker, bank • experienced.**

You must buy $X$ shares over $T$ periods. Buying $q$ shares in period $t$ costs $a_t q + b_t q^2$, with $b_t \ge 0$, and $q$ is a whole number. Find the cheapest split, in $O(X \log T)$. For $X = 5$, $a = (1, 3)$ and $b = (1, 1)$, what is the split and its cost? Prove the method is right, and say where it breaks if each period also has a fixed fee for trading at all.

**Answer to Question 1.74.**

Split it as 3 and 2 shares, for a cost of 22: the first period costs $1 \times 3 + 3^2 = 12$ and the second $3 \times 2 + 2^2 = 10$. [Listing 1.75](#lst-iv3-al-slicing) buys one share at a time, always in the period where the next share is cheapest.

```python
import heapq


def cheapest_slicing(total, a, b):
    """Send total shares over len(a) periods; q shares in period t cost a[t]*q + b[t]*q*q."""
    def marginal(t, q):           # the cost of the q+1-th share in period t
        return a[t] + b[t] * (2 * q + 1)

    sent = [0] * len(a)
    heap = [(marginal(t, 0), t) for t in range(len(a))]
    heapq.heapify(heap)
    cost = 0
    for _ in range(total):
        m, t = heap[0]
        cost += m
        sent[t] += 1
        heapq.heapreplace(heap, (marginal(t, sent[t]), t))
    return cost, sent
```

***Listing 1.75.** The cheapest next share, by a heap. code/interviews-3/01-algorithms/python/iv_slicing.py*

The cost of the $(q + 1)$-th share in period $t$ is the marginal cost $a_t + b_t(2q + 1)$. It never falls as $q$ grows, because $b_t \ge 0$. So in each period the cheapest shares are the first ones, and a set of $X$ shares has a cost that is simply the sum of its marginal costs. That is exactly the problem of choosing the $X$ cheapest entries from $T$ rising lists, which the heap merge does in $O(X \log T)$.

Any split corresponds to some prefix of each list, and the $X$ smallest entries overall always form prefixes, because each list rises. So no split can beat them.

Limit checks: with $b = 0$, each marginal is constant, and all shares go to the cheapest period. As $b_t$ grows large in one period, it gets almost nothing. With a large $X$, the shares tilt towards equalising marginal costs, which is the continuous first-order condition.

A fixed fee breaks it. The cost is now no longer convex in $q$: the first share carries the fee, and later ones do not, so the marginals fall and the prefix argument fails. With a fee of 100 in each period, the method above spreads shares, and it pays 200, while buying everything in one period pays 100 once. Use dynamic programming over (period, shares left), at $O(TX^2)$, or try each set of active periods.

**Classic wrong answer.** “Split equally.” That ignores the differences between the periods, and it is right only when they happen to balance.

**Question 1.75 ★★★★ QD, Dev, QR • any • experienced.**

There are buy orders and sell orders, and a table says which pairs may trade, say because of credit limits. Each order trades with at most one partner. Find the most pairs in polynomial time. Buyer 1 can trade with sellers A and B, and buyer 2 only with A. What does matching buyer 1 to A first do, and how does your method repair it? What does it cost?

**Answer to Question 1.75.**

Matching buyer 1 to A first leaves buyer 2 with nobody, for one pair, while two are possible: buyer 1 with B and buyer 2 with A. [Listing 1.76](#lst-iv3-al-pairing) is Kuhn’s augmenting path method: when buyer 2 finds A taken, it asks whether A’s partner, buyer 1, can move to someone else. It costs $O(VE)$.

```python
def max_pairs(buyers, compatible):
    """compatible[b]: the sellers buyer b may trade with. Each order trades at most once."""
    partner = {}                      # seller -> buyer

    def try_buyer(b, seen):           # find b a seller, moving other buyers if need be
        for s in compatible[b]:
            if s not in seen:
                seen.add(s)
                if s not in partner or try_buyer(partner[s], seen):
                    partner[s] = b
                    return True
        return False

    return sum(try_buyer(b, set()) for b in buyers), partner
```

***Listing 1.76.** Moving partners along an augmenting path. code/interviews-3/01-algorithms/python/iv_pairing.py*

An augmenting path runs from an unmatched buyer to an unmatched seller, alternating between edges not in the matching and edges in it. Flipping all its edges adds one pair and drops none. Berge’s theorem says a matching is largest exactly when no such path exists, so trying each buyer in turn is enough. The set `seen` keeps each search to $O(E)$, and there are at most $V$ searches.

A buyer that fails once need not be retried, since later augmentations never open a path that wasn’t there. That’s why a single pass over the buyers is enough.

The search recurses once per link of the path, so in Python a path longer than about 1000 links raises `RecursionError`. On such data, write it with an explicit stack, or raise the limit.

**Classic wrong answer.** “Greedy: match each buyer to its first free partner.” The example shows that it can stop at half of what is possible. It always reaches at least half, since each pair it makes can block at most two pairs of the best matching.

**Follow-up.** *Can you do better than $O(VE)$?* Hopcroft–Karp finds many shortest augmenting paths in each phase, for $O(E\sqrt{V})$. It is also a maximum flow problem, with unit capacities: add a source to the buyers and a sink to the sellers.

**Follow-up.** *And if each pair also has a value?* That is the assignment problem, which the Hungarian method solves in $O(V^3)$.

**Follow-up.** *The most trades are not the most volume, are they?* Right: with sizes, it becomes a flow problem with capacities, and the unit-capacity argument gives way to a max-flow algorithm.

**Question 1.76 ★★★★ QD, Dev • any • experienced.**

Write a matcher for patterns in which a dot matches any one character and a star after a character (or a dot) matches zero or more of it, where the whole string must match. Do it in $O(mn)$ time for text and pattern lengths $n$ and $m$. Does `a*b*` match the text `ba`? What does plain backtracking cost on `a*a*a*a*b` against a long run of `a`?

**Answer to Question 1.76.**

[Listing 1.77](#lst-iv3-al-regex) fills a table over positions in the text and pattern, in $O(mn)$ time and memory. `a*b*` does not match `ba`: the `b` comes before the `a`, and the pattern allows only the other order. Plain backtracking on `a*a*a*a*b` tries every way of dividing a run of $n$ letters among the four stars, about $\binom{n + 4}{4}$ of them, and $s$ stars give a power of $n$ near $s$: it is exponential in the length of the pattern.

```python
def matches(text, pattern):
    """. matches any character, x* zero or more of x; the whole text must match."""
    n, m = len(text), len(pattern)
    ok = [[False] * (m + 1) for _ in range(n + 1)]
    ok[n][m] = True                   # ok[i][j]: text[i:] matches pattern[j:]
    for i in range(n, -1, -1):
        for j in range(m - 1, -1, -1):
            first = i < n and pattern[j] in (text[i], ".")
            if j + 1 < m and pattern[j + 1] == "*":
                ok[i][j] = ok[i][j + 2] or (first and ok[i + 1][j])
            else:
                ok[i][j] = first and ok[i + 1][j + 1]
    return ok[0][0]
```

***Listing 1.77.** A table over text and pattern positions. code/interviews-3/01-algorithms/python/iv_regex.py*

Let `ok[i][j]` say whether the text from $i$ matches the pattern from $j$. If the next pattern item is starred, there are two choices: use it zero times, moving past it in the pattern; or, if the current character matches, use it once more and stay on it. Otherwise the characters must match, and both move on. The only base case is that the empty text matches the empty pattern; a pattern like `a*` matching the empty text is found by the zero-times rule.

There are only $(n + 1)(m + 1)$ states, and each is computed once from its neighbours, which is the whole gain over backtracking: the many ways to divide the run of `a` all pass through the same states.

In the test, the table is checked against Python’s own `re.fullmatch` on random patterns and texts, and against a counting version of plain backtracking. On `a*a*a*a*b` and 20 letters `a`, the backtracker makes more than 10 626 calls before it fails, and the table has only $21 \times 10 = 210$ cells.

**Classic wrong answer.** “Greedy: let each star take as much as it can.” On `a*a` against the text `a`, the star takes the `a`, then nothing is left for the second `a`, so it wrongly says no.

**Follow-up.** *Why does this matter outside an interview?* Backtracking regex engines take exponential time on such patterns. Patterns on untrusted text can stall a service, which is why linear-time engines exist.

**Question 1.77 ★★★★ QD, Dev, QR • bank, hedge fund • experienced.**

Counterparties have net balances that add up to zero, positive meaning they are owed. A transfer moves any amount between any two of them. Find the fewest transfers that bring all balances to zero, for at most about 20 counterparties. What is the answer for `[5, -5, 3, -1, -2]`? Why does repeatedly matching the largest creditor to the largest debtor not always work?

**Answer to Question 1.77.**

The answer is 3: one transfer settles the pair $5, -5$, and two settle the group $3, -1, -2$. [Listing 1.78](#lst-iv3-al-settle) is a bitmask dynamic programme, in $O(2^n n)$ time and $O(2^n)$ memory, on the $n$ non-zero balances.

```python
def fewest_transfers(balances):
    """balances sum to 0. The answer is the non-zero count minus the most zero-sum groups."""
    xs = [b for b in balances if b]
    n = len(xs)
    total = [0] * (1 << n)
    for mask in range(1, 1 << n):
        low = mask & -mask
        total[mask] = total[mask ^ low] + xs[low.bit_length() - 1]
    groups = [0] * (1 << n)           # groups[mask]: most zero-sum groups inside mask
    for mask in range(1, 1 << n):
        best = max(groups[mask ^ (1 << i)] for i in range(n) if mask >> i & 1)
        groups[mask] = best + (total[mask] == 0)
    return n - groups[-1]
```

***Listing 1.78.** Most zero-sum groups, over all subsets. code/interviews-3/01-algorithms/python/iv_settle.py*

Any set of transfers links the counterparties into connected groups, and each group’s balances add to zero. A group of size $g$ needs at least $g - 1$ transfers, because it must be connected, and $g - 1$ is enough: chain them, passing the running balance on. So the total is $n$ minus the number of groups, and the aim is to split the non-zero balances into as many zero-sum groups as possible.

For each subset, `groups[mask]` is the largest number of zero-sum groups inside it. Take out any one element and add 1 if the whole subset sums to zero. Order within the subset is free, so this DP is the standard one for ordered partition: walking a good order, the running sum returns to 0 once per group, and each return counts one group.

With 20 counterparties that is about 20 million steps, feasible. Above that, the problem contains subset sum, since asking whether two groups exist is exactly that, so it is NP-hard, and you need heuristics.

**Classic wrong answer.** “Match the largest creditor with the largest debtor.” On `[8, 7, 2, -8, -9]` it matches 8 with $-9$, leaving $-1$, then 7 with $-8$, leaving $-1$, and then 2 must pay both: four transfers. Settling 8 with $-8$ and letting 7 and 2 pay the $-9$ takes three. The rule never looks for groups that add up to zero, and on a list with no such group, such as `[6, 5, -4, -4, -3]`, it does find the best answer of 4.

**Question 1.78 ★★★★ QD, Dev, QR • any • experienced.**

You choose a non-empty subset of positions from a list of $n$ integers, in increasing order, so that neighbouring chosen positions are at most $k$ apart. Maximise the sum of the chosen values in $O(n)$ time. What do you get for `[7, -2, -9, 4, 15]` with $k = 2$? What is the recurrence, and which data structure removes its factor of $k$?

**Answer to Question 1.78.**

The answer is 24, from the values 7, $-2$, 4 and 15. [Listing 1.79](#lst-iv3-al-gapped) is dynamic programming with a monotone deque, in $O(n)$ time and $O(n)$ memory.

```python
from collections import deque


def best_gapped(xs, k):
    """Largest sum of a non-empty subsequence whose neighbouring picks are at most k apart."""
    dp = [0] * len(xs)                # dp[i]: the best sum of picks ending at i
    q = deque()                       # positions with dp strictly decreasing
    for i, x in enumerate(xs):
        if q and q[0] < i - k:
            q.popleft()
        dp[i] = x + max(0, dp[q[0]] if q else 0)
        while q and dp[q[-1]] <= dp[i]:
            q.pop()
        q.append(i)
    return max(dp)
```

***Listing 1.79.** The window maximum, inside a DP. code/interviews-3/01-algorithms/python/iv_gapped.py*

Let $d_i$ be the best sum of a choice ending at $i$. Then $d_i = x_i + \max(0, d_{i-1}, \dots, d_{i-k})$: either it starts the choice or it follows one of the last $k$ positions. The $\max$ over a sliding window is what would cost $O(k)$ per step, for $O(nk)$ in all.

That window maximum is exactly what a monotone deque gives in amortised $O(1)$: positions with falling $d$, the front being the largest. So the factor of $k$ goes away.

In the example, $d_0 = 7$, $d_1 = 5$, $d_2 = -2$, as $-9$ follows 7 at gap 2. Then $d_3 = 4 + \max(0, 5, -2) = 9$, and $d_4 = 15 + \max(0, -2, 9) = 24$. The answer is the largest $d$. Note that it must be non-empty, so on an all-negative list the answer is the largest single value: the zero in the recurrence lets a choice start anywhere, and yet each $d_i$ includes $x_i$.

Limits: with $k = 1$, the choice must be contiguous, so this is the largest stretch sum. With $k \ge n$, gaps stop mattering, so it is the sum of the positive values, or the largest single one if none is positive.

**Classic wrong answer.** “Take every positive value.” That ignores the gap rule, and here gives 26 from 7, 4 and 15, whose gap of 3 between 7 and 4 is not allowed.

**Follow-up.** *What if you may hold only $O(k)$ memory?* The deque holds at most $k$ positions, and the $d$ values only need to be kept for those, so yes: store them in the deque, with a running best.

**Question 1.79 ★★★★ QD, Dev • any • experienced.**

Given a list of $n$ integers, return the sum, over all contiguous non-empty stretches, of each stretch’s minimum, in $O(n)$ time. What do you get for `[2, 4, 1, 3]`? What goes wrong with repeated values, and how do you count each stretch exactly once? Try `[2, 2]`.

**Answer to Question 1.79.**

The sum for `[2, 4, 1, 3]` is 17, and for `[2, 2]` it is 6. [Listing 1.80](#lst-iv3-al-summins) counts, for each value, how many stretches have it as their minimum, using a monotone stack, in $O(n)$ time and memory.

```python
def sum_of_minimums(xs):
    total = 0
    stack = []                        # positions with strictly rising values
    for i, x in enumerate([*xs, float("-inf")]):
        while stack and xs[stack[-1]] >= x:
            j = stack.pop()
            left = stack[-1] if stack else -1
            total += xs[j] * (j - left) * (i - j)   # stretches where xs[j] is the minimum
        stack.append(i)
    return total
```

***Listing 1.80.** Each value times the stretches it is the minimum of. code/interviews-3/01-algorithms/python/iv_sum_mins.py*

Look at a position $j$. It is the minimum of a stretch if the stretch contains $j$ and nothing lower. If the nearest lower value to the left is at position $\ell$, and the nearest to the right at $r$, then there are $(j - \ell)$ choices for the start and $(r - j)$ for the end, so the value counts $(j - \ell)(r - j)$ times. For `[2, 4, 1, 3]`, the value 2 is the minimum of 2 stretches, 4 of one, 1 of six and 3 of one: $2 \times 2 + 4 \times 1 + 1 \times 6 + 3 \times 1 = 17$.

Repeated values are the trap. In `[2, 2]` the stretch of both has two positions tied for the minimum. If both sides stop only at a strictly lower value, each 2 claims it, and the total is $2 \times 2 + 2 \times 2 = 8$, counting that stretch twice. If both stop at a lower or equal value, nobody claims it, and the total is 4.

So break ties one way: stop at a strictly lower value on the left, and at a lower-or-equal on the right, or the reverse. Then a tied stretch belongs to exactly one position: the last of the ties. The stack here pops on `>=`, so the popped entry’s right limit is the first value at or below it, and its left limit is strictly below it. Each position is pushed and popped once, hence $O(n)$.

The extra sentinel flushes the stack at the end, and in the test the method agrees with a brute force over all stretches on lists with many ties.

**Classic wrong answer.** “Sum over pairs of ends with a running minimum.” It is correct, at $O(n^2)$.

**Question 1.80 ★★★★ QR, QD • hedge fund, market maker • experienced.**

A list of $n$ daily returns is given, along with a minimum length $k$. Find the largest average over contiguous stretches of at least $k$ days, in $O(n \log(R/\epsilon))$ time, where $R$ is the range of the values and $\epsilon$ your tolerance. What is the answer for `[2, 10, -6, -5, 40, 4]` with $k = 4$? Why is it not enough to look only at stretches of exactly $k$ days?

**Answer to Question 1.80.**

The answer is 9.75, from `[10, -6, -5, 40]`. [Listing 1.81](#lst-iv3-al-bestmean) is binary search on the answer, in $O(n \log(R/\epsilon))$ time and $O(1)$ memory.

```python
def best_mean(xs, k, tol=1e-9):
    """The largest mean over stretches of length at least k, to within tol; None if k > n."""
    if k > len(xs):
        return None

    def reachable(m):             # is some stretch of length >= k at a mean of at least m?
        total, low, before = 0.0, 0.0, 0.0
        for i, x in enumerate(xs):
            total += x - m
            if i >= k:
                before += xs[i - k] - m
                low = min(low, before)
            if i >= k - 1 and total >= low:
                return True
        return False

    lo, hi = min(xs), max(xs)
    while hi - lo > tol:
        mid = (lo + hi) / 2
        if reachable(mid):
            lo = mid
        else:
            hi = mid
    return lo
```

***Listing 1.81.** Is a mean of m reachable? code/interviews-3/01-algorithms/python/iv_best_mean.py*

A mean of at least $m$ is reachable exactly when some stretch of length at least $k$ has $\sum (x_i - m) \ge 0$. Subtract $m$, take prefix sums, and at each end $j$ you want the smallest prefix at least $k$ earlier: if the current prefix is at or above that, the answer is yes. That is a single pass. And reachability is monotone in $m$, which is what lets the outer search work.

A stretch of exactly $k$ days is not enough, as a longer one can have a higher mean. On `[9, 1, 9]` with $k = 2$, every pair has mean 5, and all three have $19/3$, about 6.33. It is true, though, that lengths from $k$ to $2k - 1$ are enough: a longer stretch splits into two pieces of at least $k$, and one of those has a mean at least as high as the whole.

So a simple exact route is to try lengths from $k$ to $2k - 1$ with sliding sums, at $O(nk)$, which is what the test uses as a second route, with fractions, and it finds the exact value.

Limits: with $k = 1$ the answer is the largest single value, and with $k = n$ it is the mean of everything. The search range is sound, as a mean cannot leave the range of the values. With $k > n$ no stretch exists, and the function returns `None` rather than a number.

**Classic wrong answer.** “Kadane’s algorithm on the values.” That finds the largest sum, and a long stretch with a large sum can have a low mean, as with the whole list here: sum 45, mean 7.5.

**Follow-up.** *And exactly?* Means of two stretches differ by at least $1/n^2$ for integer values, so stop at that tolerance and recover the fraction from the best stretch. There is also a linear method using a convex hull of the prefix points.