The Interview Book · Careers

21Algorithms and Data Structures

“Given a stream of trades, report after each one the median size of the last thousand.” The candidate sorts the window every time. It works, and the interviewer asks what happens at a million trades a second. Two heaps, an order-statistic tree, and a counting array for bounded sizes are the three answers that score, each for a different reason, and the candidate who names the families before choosing has already done half the work. Coding interviews at trading firms ask the standard families of algorithm questions, often dressed in market data: order books, tapes, windows of prices, halts and intervals. This chapter lists the families, the method, and the trading-flavoured variants.

21.1 The families and how to recognise them

Family	The clue in the question	Typical cost
Hashing	“have we seen”, pairs summing to a target, counts	$O(n)$
Two pointers	two sorted sequences, or a condition on pairs	$O(n)$
Sliding window	“the last $k$ ”, a window moving over a stream	$O(n)$ or $O(n \log k)$
Heaps	top $k$ , a running median, the next event	$O(n \log k)$
Sweep line	intervals, “at the same time”, overlaps	$O(n \log n)$
Binary search	a sorted array, a monotone predicate	$O(\log n)$ per query
Graphs	conversions, dependencies, shortest paths, cycles	$O(V E)$ or $O(E \log V)$
Dynamic programming	optimal choices with overlapping subproblems	states $\times$ transitions

Definition 21.1 (Two-pointer technique, monotonic deque, sweep line)

The two-pointer technique walks two indices through one or two sorted sequences, advancing whichever the condition dictates, so that each element is visited once. A monotonic deque is a double-ended queue of indices whose values are kept in decreasing (or increasing) order, so that the maximum (or minimum) of a sliding window is at its front at every step. A sweep line solves interval problems by sorting the intervals’ endpoints as events and processing them in order while maintaining a running state.

def sliding_max(prices, k):
    """Maximum of each window of k consecutive prices, with a monotonic deque of indices. O(n)."""
    dq, out = deque(), []
    for i, p in enumerate(prices):
        while dq and prices[dq[-1]] <= p:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(prices[dq[0]])
    return out

Listing 21.1. The sliding-window maximum with a monotonic deque: every index enters and leaves the deque once, so the whole pass is linear. code/interviews/21-algorithms-and-data-structures/python/iv_algos.py

21.2 Trading-flavoured variants

Market data turns the families into familiar questions. A tape is a sorted sequence (two pointers, binary search by time); a book side is a set of price levels with add, cancel and best-price queries (a balanced tree or a heap with lazy deletion); open orders, halts and sessions are intervals (a sweep line); rolling statistics are windows (a deque, two heaps, or Welford-style updates, One Quant Book 4, chapter 25); currencies and conversion rates are a graph whose cycles with a product above one are arbitrages (Bellman–Ford on $-\log$ of the rates).

def max_open(orders):
    """Most orders open at once; an order (start, end) is open on [start, end)."""
    events = sorted([(s, 1) for s, _ in orders] + [(e, -1) for _, e in orders])
    best = cur = 0
    for _, d in events:  # at equal times the end (-1) sorts first
        cur += d
        best = max(best, cur)
    return best

Listing 21.2. A sweep line: the maximum number of orders open at once. Sorting puts an end before a start at the same time, so an order ending when another begins does not overlap it. code/interviews/21-algorithms-and-data-structures/python/iv_algos.py

The book side is the one data structure every trading interview asks about, because every trading system has one (One Quant Book 10, chapter 1, and Book 13, chapter 19). In an interview the price-level structure below is enough; the design questions of Chapter 26 ask what a production book adds.

// One side of a book aggregated by price: O(log n) add, cancel and best.
class PriceLevels {
public:
    explicit PriceLevels(bool bid) : bid_(bid) {}
    void add(std::int64_t price, std::int64_t qty) { levels_[price] += qty; }
    void cancel(std::int64_t price, std::int64_t qty) {
        auto it = levels_.find(price);
        if (it == levels_.end()) return;
        if ((it->second -= qty) <= 0) levels_.erase(it);
    }
    std::optional<std::int64_t> best() const {
        if (levels_.empty()) return std::nullopt;
        return bid_ ? levels_.rbegin()->first : levels_.begin()->first;
    }

private:
    bool bid_;
    std::map<std::int64_t, std::int64_t> levels_;
};

Listing 21.3. One side of a book aggregated by price in C++20: an ordered map gives logarithmic add, cancel and best price. code/interviews/21-algorithms-and-data-structures/cpp/iv_algos.hpp

21.3 The method: clarify, brute force, improve, test

Method 21.2 (Solving a coding question)

Clarify: input sizes and ranges, duplicates, ties, empty input, what to return when there is no answer.
Brute force: say the obvious algorithm and its cost; it is the baseline and, later, the oracle.
Improve: name the family, derive the better complexity, and say the lower bound (every element must be read).
Code: clean names, no premature cleverness, edge cases handled.
Test: run a small case by hand, then the edge cases; say how you would test at scale (next section).

21.4 Tutorial: testing an answer against a brute-force oracle

Goal. Test the sliding-window maximum of Listing 21.1 against an answer that is obviously right, on hundreds of random inputs. End state: a green test that would have caught every bug tried while writing this chapter.

The oracle. Write the slowest correct answer: the maximum of every window by slicing.
```
def sliding_max(prices, k):
    return [max(prices[i : i + k]) for i in range(len(prices) - k + 1)]
```
Listing 21.4. The oracle: quadratic and obviously correct. code/interviews/21-algorithms-and-data-structures/python/iv_oracles.py

Random small inputs. Draw lengths from 1 to 30 and values from a small range, so that ties and repeats are common, with a fixed seed per case.

def test_q6_sliding_max():
    assert sliding_max([4, 2, 12, 3, 8, 1], 3) == [12, 12, 12, 8]
    for s in SEEDS:
        r = random.Random(s)
        xs = [r.randint(0, 9) for _ in range(r.randint(1, 30))]
        k = r.randint(1, len(xs))
        assert sliding_max(xs, k) == oracle.sliding_max(xs, k)

Listing 21.5. Three hundred seeded cases, compared element by element. code/interviews/21-algorithms-and-data-structures/tests/test_solutions.py

When it fails, shrink the failing case by hand: remove elements while it still fails; the smallest failing input usually names the bug.

The same pattern tests every answer in the chapter’s code, in Python and in the C++20 twins of five of them.

21.5 Worked answers

Example 21.3 (A window with at most two venues)

“A parent order’s fills are listed in time order with the venue of each. Find the longest run of consecutive fills that touches at most two venues.” Clarify: runs are contiguous; venues are labels. Brute force checks every window, $O(n^2)$ with a set per start. Improve with the two-pointer technique (Definition 21.1): extend the right end one fill at a time, keep a count per venue in the window, and while more than two venues have a positive count, advance the left end and decrement. Each fill enters and leaves the window once: $O(n)$ time, $O(1)$ extra space for a fixed bound on venues. Trace on the fills A, B, A, C, C, C, B, A: after three fills the window is A, B, A; the C makes three venues, so the left end drops the first A (still three) and the B, leaving A, C; two more C’s give A, C, C, C, length 4; the B drops the A, leaving C, C, C, B, length 4; the last A drops the three C’s, leaving B, A. The answer is 4, which the brute force confirms here and the chapter’s test confirms against it on random inputs.

21.6 Question bank

Interview question 21.1 ★ developer • market maker

Given a list of order sizes and a target, return two orders whose sizes sum to the target, in linear time.

Solution

Solution of Interview question 21.1.

One pass with a hash map from size to index: for each size $x$ , look up $t - x$ among the sizes already seen; if present, return the pair, else record $x$ . $O(n)$ time and memory. The brute force is $O(n^2)$ ; sorting with two pointers is $O(n\log n)$ and loses the original indices unless they are carried.

What the interviewer is looking for: the hash-map complement and the comparison with the alternatives.

Interview question 21.2 ★ developer • proprietary firm

Return the first client order identifier that appears twice in a stream. What if the stream does not fit in memory?

Solution

Solution of Interview question 21.2.

A hash set of identifiers seen; return the first one already present. $O(n)$ time, $O(n)$ memory. If the stream does not fit: partition identifiers by a hash into files that do, then check each partition (two passes); or use a Bloom filter as a first filter and verify its positives exactly, accepting a small false-positive rate on the first pass.

What the interviewer is looking for: the set solution and an external-memory plan.

Interview question 21.3 ★ developer, researcher • any

Merge two trade tapes, each sorted by timestamp, into one sorted tape. What do you do with equal timestamps?

Solution

Solution of Interview question 21.3.

Two pointers, taking the earlier head each time: $O(n + m)$ . For ties, decide and state a rule that makes the merge stable and deterministic, such as tape A before tape B, or a secondary key (sequence number, venue); the chapter’s code keeps A first and is checked against sorting on 300 random cases.

What the interviewer is looking for: the linear merge and an explicit, deterministic tie rule.

Interview question 21.4 ★ developer, trader • market maker

Given a day’s prices, find the largest profit from one purchase followed by one sale.

Solution

Solution of Interview question 21.4.

Track the lowest price so far and the best difference: $O(n)$ , $O(1)$ memory. The answer is 0 if prices only fall (no trade). Example: $7, 1, 5, 3, 6, 4$ gives 5.

What the interviewer is looking for: the running-minimum scan and the no-trade case.

Interview question 21.5 ★ developer, mle • systematic fund

In a sorted array of trade timestamps, find the first trade at or after a given time. What does the standard library offer?

Solution

Solution of Interview question 21.5.

Binary search for the first element not less than $t$ : bisect_left in Python, std::lower_bound in C++; $O(\log n)$ . It returns the length of the array when every timestamp is earlier, which the caller must handle.

What the interviewer is looking for: lower bound, its return value at the end, and the library call.

Interview question 21.6 ★★ developer • proprietary firm

Report the maximum price of every window of the last $k$ trades in $O(n)$ time overall.

Solution

Solution of Interview question 21.6.

A monotonic deque of indices with decreasing prices (Listing 21.1): pop smaller prices from the back before pushing, pop the front when it leaves the window, and read the maximum at the front. Each index enters and leaves once: $O(n)$ overall, $O(k)$ memory. Tested against the quadratic oracle.

What the interviewer is looking for: the deque invariant and the amortised argument.

Interview question 21.7 ★★ developer, researcher • market maker

Report, after each trade, the median size of the last $k$ trades, faster than sorting the window each time. What if sizes are integers below 1 000?

Solution

Solution of Interview question 21.7.

Two heaps: a max-heap for the lower half and a min-heap for the upper half, balanced to within one element; the median is at the top. Removing the value that leaves the window is done lazily: record it and discard it when it reaches a top. $O(\log k)$ per trade. With integer sizes below 1 000, keep a count per size and walk to the middle, or keep a Fenwick tree over sizes to find the median in $O(\log 1000)$ : bounded values beat comparisons.

What the interviewer is looking for: the two-heap median with deletion, and exploiting a bounded domain.

Interview question 21.8 ★★ developer, mle • crypto firm

From a stream of (symbol, volume) trades, return the $k$ symbols with the largest total volume. What changes if the stream is unbounded and memory is not?

Solution

Solution of Interview question 21.8.

Sum volume per symbol in a hash map, then keep a min-heap of size $k$ over the totals: $O(n + s\log k)$ for $s$ symbols. With an unbounded stream and bounded memory, use a heavy-hitters sketch (Space-Saving or a Count-Min sketch with a heap), which guarantees the frequent symbols with bounded error.

What the interviewer is looking for: counting plus a bounded heap, and a streaming sketch when memory binds.

Interview question 21.9 ★★ developer • market maker

Given each order’s start and end time, find the largest number of orders open at the same moment.

Solution

Solution of Interview question 21.9.

Sweep over the sorted endpoints, $+1$ at a start and $-1$ at an end, with ends before starts at equal times if orders are open on $[s, e)$ ; the largest running total is the answer (Listing 21.2). $O(n\log n)$ . For $(0,5), (1,3), (3,6), (5,7)$ the answer is 2.

What the interviewer is looking for: the event sweep and the tie convention that encodes the interval’s openness.

Interview question 21.10 ★★ developer, researcher • any

Merge a list of trading halts, given as time intervals, into disjoint intervals.

Solution

Solution of Interview question 21.10.

Sort by start; extend the last merged interval while the next one starts before or at its end, otherwise open a new one. $O(n\log n)$ . Say whether touching intervals merge (the chapter’s code merges them).

What the interviewer is looking for: sort and merge, with the touching-interval convention stated.

Interview question 21.11 ★★★ developer, trader • crypto firm

Given a matrix of conversion rates between currencies, decide whether some cycle of conversions ends with more money than it started with.

Solution

Solution of Interview question 21.11.

A cycle multiplies money when the product of its rates exceeds one, that is when the sum of $-\log(\text{rate})$ along it is negative. Run Bellman–Ford from a virtual source (all distances 0) for $n - 1$ rounds and check whether any edge can still be relaxed: $O(n^3)$ for $n$ currencies. In practice add a tolerance for fees and floating point, and recover the cycle from the predecessor pointers to trade it. The chapter’s example turns 1 into about 1.064.

What the interviewer is looking for: the log transformation, negative-cycle detection and the practical caveats.

Interview question 21.12 ★★★ developer, researcher • proprietary firm

Given a day’s prices, find the largest profit with at most $k$ non-overlapping round trips, each paying a fixed fee.

Solution

Solution of Interview question 21.12.

Dynamic programming over (day, trades used, holding or not): $\text{hold}_j = \max(\text{hold}_j, \text{free}_{j-1} - p)$ and $\text{free}_j = \max(\text{free}_j, \text{hold}_j + p - \text{fee})$ , $O(nk)$ time and $O(k)$ memory. On $3, 2, 6, 5, 0, 3$ with $k = 2$ and no fee the answer is 7; the chapter’s code checks the recursion against exhaustive search on small inputs.

What the interviewer is looking for: the state definition and the recursion.

Interview question 21.13 ★★★ developer • market maker

Design the data structure for one side of an order book aggregated by price, with add, cancel and best-price queries. Give the complexities, and say what changes if prices are integers in a known narrow range.

Solution

Solution of Interview question 21.13.

An ordered map from price to quantity (Listing 21.3): add and cancel in $O(\log n)$ , best price in $O(1)$ at the map’s end. With integer ticks in a known narrow band, an array indexed by tick offset gives $O(1)$ add and cancel, and a bitmap of non-empty levels finds the best price with a few word scans; the array must be recentred when prices drift. Real books also keep orders within a level in time priority (a linked list per level) and an index from order identifier to order (One Quant Book 13, chapter 19).

What the interviewer is looking for: the tree solution, the array-of-ticks alternative, and what a production book adds.

Interview question 21.14 ★★★ developer, mle • systematic fund

Maintain the mean and variance of the last $k$ values of a stream in $O(1)$ per update, numerically stably.

Solution

Solution of Interview question 21.14.

Welford’s update adds a value: $n \mathrel{+}= 1$ , $\delta = x - \bar x$ , $\bar x \mathrel{+}= \delta/n$ , $M_2 \mathrel{+}= \delta(x - \bar x)$ ; removing a value reverses it: $n \mathrel{-}= 1$ , $\delta = y - \bar x$ , $\bar x \mathrel{-}= \delta/n$ , $M_2 \mathrel{-}= \delta(y - \bar x)$ ; the variance is $M_2/(n - 1)$ . $O(1)$ per update and far more stable than keeping $\sum x$ and $\sum x^2$ , which cancel catastrophically when the mean is large. Over very long streams, recompute the window exactly now and then to stop rounding errors accumulating.

What the interviewer is looking for: Welford with removal, and the reason naive sums fail.

Sources and further reading

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022.
B. P. Welford, “Note on a method for calculating corrected sums of squares and products”, Technometrics 4(3), 1962, 419–420.
One Quant Book 4, chapter 25; One Quant Book 10, chapter 1; One Quant Book 13, chapter 19.

Terms defined in this chapter

Two-pointer technique, monotonic deque, sweep line

See all 2333 terms in the glossary