Five Optiver-Style C++ Problems: Order Books, Dijkstra, and DP

Optiver’s Senior Software Engineer EU assessment is one coding problem in two hours. The problem is long, the spec is dense, and the code quality bar is high. They want clean OOP, correct complexity analysis, and evidence that you think about cache lines and allocator behavior — not just algorithmic correctness.

I spent a week working through five problems modeled on what shows up in public Optiver OA reports: supermarket checkout simulation, order book matching, stock dividend pricing, a lattice-path DP problem, and a modified Dijkstra. Each problem produced bugs worth documenting. The recurring pattern: architectural instincts were right, but operator typos (< vs =), container initialization (braces vs parentheses), and iterator invalidation burned real time.

This post is the full record. Every wrong output, every segfault, every fix.

Problem 1: Supermarket Checkout Simulation

This problem appears most frequently in Optiver OA reports. A supermarket has L checkout lines. Customers enter, join the shortest line, and exit when their item count reaches zero. Three event types drive the simulation: CustomerEnter, BasketChange, and LineService.

The rules that matter:

• Customers join the shortest line. Ties break by lowest index.
• LineService processes one item from the front customer of a line.
• BasketChange with a positive delta moves the customer to the back of their line — but only if they are at the front.
• Item count reaching zero means immediate exit. Print the customer ID.

The Data Structure Choice

The obvious structure for customer lookup is std::unordered_map<size_t, Customer>. O(1) lookup, O(1) insert. But I deliberately chose a std::vector<Customer> with linear scan and slot reuse for a reason: contiguous memory is cache-friendly, and for the expected customer counts in this problem (hundreds, not millions), the linear scan with good cache locality beats a hashmap with pointer chasing and hashing overhead.

The key is articulating the tradeoff. A comment like this makes the intent clear:

// Using contiguous storage for cache locality.
// Linear scan is acceptable for expected customer counts < ~1000.
// For larger N, consider unordered_map with pooled allocator.

If an interviewer asks “what if N is 100k?”, the answer is: switch to unordered_map with a custom allocator using a pre-allocated pool to keep allocation patterns predictable.

The Bugs

Four bugs showed up during implementation.

Off-by-one in the line bounds check. The guard if(lines_.size() >= line_number) return; rejects valid indices. With 2 lines (indices 0, 1), lines_.size() is 2, so line_number=0 triggers the early return. The fix: <=.

try_back_of_line checked the wrong position. The spec says move to back if the customer is at the front. The code checked if the customer was at the end:

BasketChange delta read as size_t. A negative delta read into size_t becomes a huge positive value, causing std::bad_alloc. The fix: read it as int.

Missing output on customer exit. Both line_service and basket_change had paths where customers exited without printing their ID.

The Final Structure

struct Customer
{
    size_t id;
    size_t items;
    ssize_t line_id = -1;
};

class CustomerLines
{
public:
    CustomerLines(size_t lines)
    : lines_(lines), storage_{}
    {
        storage_.reserve(PAGE_SIZE);
    }

    void enter(Customer && new_customer);
    void line_service(size_t line_number);
    void basket_change(size_t customer_id, int delta);

private:
    std::vector<Customer>::iterator get_customer_itr(size_t id);
    void leave(size_t customer_id, size_t line_id);
    void try_back_of_line(size_t customer_id, size_t line_id);

    std::vector<std::deque<size_t>> lines_{};
    std::vector<Customer> storage_{};
    size_t last_id_ = 0;
};

Try it on Compiler Explorer: godbolt.org/z/3Wxb5TbvG

Problem 2: Order Book Matching Engine

A simplified order book for a single stock. BUY orders match against the lowest-priced SELL. SELL orders match against the highest-priced BUY. Price-time priority: at the same price, the earliest order wins.

The Design

Two std::set containers with custom comparators — one for asks (ascending price, ascending time), one for bids (descending price, ascending time):

bool sell_order(Order const& me, Order const& other)
{
    return std::tie(me.price, me.id) < std::tie(other.price, other.id);
}

bool buy_order(Order const& me, Order const& other)
{
    if(me.price != other.price)
        return me.price > other.price;
    return me.id < other.id;
}

using Asks = std::set<Order, decltype(&sell_order)>;
using Bids = std::set<Order, decltype(&buy_order)>;

This gives O(log N) best-price lookup and correct time priority. The mutable qualifier on quantity allows updating a resting order’s quantity through a const iterator — necessary because std::set iterators are const.

The Bugs

Missing empty-book check. The matching loop dereferenced bids_.begin() and asks_.begin() without checking if either side was empty. Immediate crash on any order that doesn’t match.

if/if/else instead of if/else if/else. The remainder logic for partial fills had two consecutive if statements. When remainder < 0, the code fell through to the else branch and double-processed:

MATCH output placed after iterator erase. The print statement was after the erase calls, dereferencing invalidated iterators. Undefined behavior. The fix: compute match quantity and price before any modification, print, then erase.

Match price logic. The match price is the resting order’s price, not the aggressor’s. If the new order is a BUY, the match price is the ask price. If SELL, the bid price.

Try it on Compiler Explorer: godbolt.org/z/ePh9fPbE1

Problem 3: Stock Dividend Price Calculator

Given a stock price S and N dividends with amounts and days, answer Q queries: what is the stock price on day X?

The Approach

Rather than the straightforward sort-and-prefix-sum approach, I went with an online insertion model using std::set<PriceChange> ordered by day offset. Each insertion updates the cumulative stock prices for all subsequent entries. This supports interleaved insertions and queries — more general than the offline approach, at the cost of O(N) per insertion.

struct PriceChange
{
    size_t offset_days;
    size_t divident;
    mutable ssize_t stock_price = UNSET;
};

The Bug

The query function used lower_bound instead of upper_bound, returning the first dividend day >= query day instead of the last dividend day <= query day:

ssize_t get_price(PriceSet & price_set, size_t offset_days)
{
    auto it = price_set.upper_bound({offset_days, SIZE_MAX, 0});
    if(it == price_set.begin()) return price_set.begin()->stock_price;
    --it;
    return it->stock_price;
}

The symptom: day 3 returned 900 (next dividend’s price) instead of 1000 (no dividend yet). Day 60 returned 825 instead of 875. Both off by one lookup step.

Try it on Compiler Explorer: godbolt.org/z/4dvW51nbM

Problem 4: Trading Sequences (Lattice Path DP)

Given k initial shares, target n shares, and at most m buy/sell transactions (+1 or -1 each), count the distinct valid sequences. Constraint: shares cannot go negative at any point.

Why This Problem is Interesting

This is the Cox-Ross-Rubinstein binomial tree model. Stock price goes up or down by 1 unit each step, count paths to a target price. The non-negativity constraint maps to barrier options. Optiver trades options heavily — this tests whether you intuitively understand the pricing model structure.

The Recursive Version

int count_sub_paths(int pos, int target, int steps)
{
    if(pos < 0) return 0;
    if(!steps) return (pos == target) ? 1 : 0;
    return count_sub_paths(pos - 1, target, steps - 1)
         + count_sub_paths(pos + 1, target, steps - 1);
}

Clean recursion. The bug was in the wrapper:

int count_pathes(int start_p, int target_p, int steps_left)
{
    return count_sub_paths(start_p, target_p, steps_left)
         + count_sub_paths(start_p, target_p, steps_left - 1);
}

This only sums paths of exactly m and m-1 steps. The problem says “at most m.” For k=1, n=2, m=3: paths of length 1 (just BUY) are valid but missed. The code returned 3 instead of 4.

The Enumeration That Found It

All 3-step paths from position 1:

Three valid 3-step paths, plus one valid 1-step path (BUY). Total: 4.

The Bottom-Up DP

The recursive version is O(2^m). The bottom-up DP runs in O(m * max_pos):

long count_paths(int k, int n, int m)
{
    int max_pos = k + m;
    std::vector<long> dp(max_pos + 2, 0);
    dp[k] = 1;
    long total = 0;

    for(int step = 0; step <= m; ++step)
    {
        total += dp[n];
        std::vector<long> ndp(max_pos + 2, 0);
        for(int j = 0; j <= max_pos; ++j)
        {
            if(j > 0) ndp[j] += dp[j - 1];
            ndp[j] += dp[j + 1];
        }
        dp = ndp;
    }
    return total;
}

No parity logic needed. Unreachable states are naturally 0. Accumulate dp[n] at every step count.

Try it on Compiler Explorer: godbolt.org/z/aKo5zf3rG

Problem 5: Dijkstra with K Free Edges

Find the minimum cost path from S to T in a directed weighted graph, where at most K edges can be used for free (cost becomes 0).

Learning Dijkstra From Scratch

I had not implemented Dijkstra before this exercise. The mental model that clicked: BFS but ordered by cumulative cost instead of hop count. A priority queue ensures the cheapest frontier node is always processed next. Once a node is popped, its distance is final — no cheaper path can exist because all edge weights are non-negative.

The core algorithm:

1. dist[source] = 0, everything else INF.
2. Priority structure contains (cost, node), sorted by cost.
3. Pop the cheapest. For each neighbor, check if current_cost + edge_weight improves their best known cost. If yes, update and insert.
4. Stop when target is popped or structure is empty.

std::set vs std::priority_queue

I chose std::set<std::pair<NodeCost, NodeIndex>> over std::priority_queue. With a priority queue, you cannot remove stale entries — when a better path is found, the old entry stays in the heap. You push the new entry and skip the old one when popped (if(cost > dist[u]) continue). With std::set, you erase the old entry and insert the updated one. No stale entries, no skip logic.

The tradeoff: std::set uses tree nodes (cache-unfriendly), priority_queue uses a contiguous vector. For an assessment, clarity wins.

The Bugs on the Way to Working Dijkstra

operator<=> returning bool. Writing return cost < other.cost; inside operator<=> returns a bool, not std::strong_ordering. The map sorted incorrectly, producing wrong accumulated costs. The fix: = default or use <=> properly.

Braces vs parentheses in vector initialization. std::vector<NodeIndex>{graph.size(), MAX} creates a 2-element vector with values {6, MAX}. std::vector<NodeIndex>(graph.size(), MAX) creates a 6-element vector filled with MAX. This caused out-of-bounds access in path reconstruction.

< instead of = for assignment. peretns[next_id] < node_index; compiles silently as a comparison expression. The parent array was never populated. Path reconstruction walked to node -1UL and segfaulted. This bug appeared twice.

std::map sorts by key, not value. Using map<NodeIndex, NodeCost> processes nodes in index order, not cost order. Dijkstra requires cost ordering. The fix: std::set<std::pair<NodeCost, NodeIndex>> sorts by cost first via lexicographic pair comparison.

Updating the wrong accumulator. cost_accumilators[node_index] = next_acc_cost; updates the current node’s cost instead of the neighbor’s. Should be cost_accumilators[next_id].

The K Free Edges Extension

The state becomes (cost, node, frees_used). The dist array becomes 2D: dist[node][f]. At each edge, two choices:

// Option A: pay for the edge
if(node_cost + next_cost < cost_acc[next_id][f])
{
    frontier.erase({cost_acc[next_id][f], next_id, f});
    cost_acc[next_id][f] = node_cost + next_cost;
    frontier.insert({cost_acc[next_id][f], next_id, f});
    peretns[next_id][f] = {node_index, f};
}

// Option B: use a free edge (only if f < K)
if(f < free_nodes && node_cost < cost_acc[next_id][f + 1])
{
    frontier.erase({cost_acc[next_id][f + 1], next_id, f + 1});
    cost_acc[next_id][f + 1] = node_cost;
    frontier.insert({cost_acc[next_id][f + 1], next_id, f + 1});
    peretns[next_id][f + 1] = {node_index, f};
}

The f < free_nodes check is the entire constraint. Think of f as a fuel gauge — every free edge ticks it up by 1. When it hits K, only paid edges remain.

An alternative approach: run Dijkstra C(M, K) times, each time zeroing a different combination of K edges. For M=100 and K=3, that is 160,000 runs. For K=10, 17 trillion. The layered approach does it in one pass with O(NK * log(NK)) complexity.

Try it on Compiler Explorer: godbolt.org/z/GK4djdGW8

Recurring Bug Patterns

Five problems, and the same categories of bug appeared repeatedly.

The < vs = bug is the most dangerous. It compiles silently, produces no warnings, and the symptom (segfault in path reconstruction, infinite loop) is far from the cause (parent array never populated).

Takeaways

1. Articulate your data structure tradeoffs. Choosing vector over unordered_map is defensible when you can explain why. “Contiguous storage for cache locality at expected N < 1000” scores better than reaching for the textbook-optimal structure without comment. The senior-level answer bridges both: “I would switch to unordered_map with a pooled allocator at higher N.”

2. The = vs < typo is a class of bug worth a mental lint rule for. In C++, x < y; is a valid expression statement that discards the result. No compiler warning by default. Consider -Wunused-value or wrapping assignments in a helper that cannot be confused with comparison.

3. std::set over std::priority_queue for Dijkstra in assessment contexts. The priority queue approach requires stale-entry handling. The set approach is more code per update but eliminates an entire category of bugs. Under time pressure, fewer failure modes wins.

4. Bottom-up DP is safer than memoized recursion for assessments. The recursive lattice path solution invited a broken memo scheme (hash collisions, val != 0 as sentinel when 0 is valid). The bottom-up version is 15 lines, no memo, no collisions, no sentinel issues. When both approaches have the same complexity, prefer the one with fewer moving parts.