Six Optiver-Style C++ Problems: Order Books, Dijkstra, DP, and an AoS→SoA Rewrite

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 six 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, a modified Dijkstra, and a price-alert router that I wrote twice — once with std::map-of-tuples (array-of-structs), once with parallel std::vectors (structure-of-arrays). 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

Problem 6: Price Alert Router (AoS → SoA Rewrite)

A market-data service publishes price alerts tagged with timestamp, volatility, and a set of tickers. Brokers subscribe with a minimum volatility threshold and a max alerts per second rate limit, also scoped to a ticker list. On each publish(), match every alert to every interested broker while respecting volatility filtering, per-second rate limits, and not dispatching the same alert twice to a broker that subscribes to multiple overlapping tickers.

The instructive part of this problem isn’t the matching — it’s the storage. The obvious version uses std::map<BrokerId, tuple<...>> keyed by id. The senior version notices that publish()’s inner loop only ever reads one field at a time per broker — threshold, then rate limit — and that std::tuple packs everything into a single cache line that’s mostly useless on each access. Rewriting with parallel std::vectors (structure-of-arrays) changes the access pattern to column-major, makes the hot fields sequentially streamed, and turns remove into swap-and-pop.

The AoS Version

Array-of-structs — one std::map entry per broker holding a tuple of fields. I’ll lean on C++20/23 algorithms and views so the intent is readable without nested raw loops:

using Brokers         = std::map<BrokerId, std::tuple<VolatilityThreshold, AlertsPerSec>>;
using BrokersByTicker = std::map<Ticker, std::set<BrokerId>>;
using Alerts          = std::map<AlertId, std::tuple<Timestamp_ms, VolatilityThreshold>>;
using AlertsByTicker  = std::map<Ticker, std::set<AlertId>>;

void PriceAlertRouter::add_broker(BrokerId id,
                                  VolatilityThreshold min_volatility,
                                  AlertsPerSec max_alerts,
                                  Tickers const& tickers)
{
    if (!brokers_.try_emplace(id, min_volatility, max_alerts).second) return;
    std::ranges::for_each(tickers, [&](Ticker const& t) {
        brokers_by_ticker_[t].insert(id);
    });
}

void PriceAlertRouter::remove_broker(BrokerId id)
{
    brokers_.erase(id);
    std::ranges::for_each(brokers_by_ticker_, [&](auto& kv) { kv.second.erase(id); });
    std::erase_if(brokers_by_ticker_, [](auto const& kv) { return kv.second.empty(); });
}

DispatchPlan PriceAlertRouter::publish() const
{
    DispatchPlan plan;
    for (auto const& [ticker, broker_id_set] : brokers_by_ticker_)
    {
        auto alerts_it = alerts_by_ticker_.find(ticker);
        if (alerts_it == alerts_by_ticker_.end()) continue;

        // One cartesian_product over (alerts x brokers) replaces two nested for-loops.
        for (auto const [alert_id, broker_id] :
             std::views::cartesian_product(alerts_it->second, broker_id_set))
        {
            auto const [alert_ts, alert_vol] = alerts_.at(alert_id);
            auto const [min_vol, max_per_sec] = brokers_.at(broker_id);
            if (alert_vol < min_vol) continue;

            auto& plan_alerts = plan[broker_id];
            auto const a_sec = static_cast<std::uint32_t>(alert_ts) / 1000;
            auto const same_sec = std::ranges::count_if(plan_alerts,
                [&](AlertId other) {
                    auto const [other_ts, _] = alerts_.at(other);
                    return static_cast<std::uint32_t>(other_ts) / 1000 == a_sec;
                });
            if (same_sec >= max_per_sec) continue;
            plan_alerts.insert(alert_id);
        }
    }
    return plan;
}

The algorithm library in use here:

• std::map::try_emplace and std::ranges::for_each for insertion — the try_emplace guards against double-adding and the ranges version of for_each replaces the for (auto const& t : tickers) boilerplate with a named lambda that states what happens per ticker.
• std::erase_if for dropping empty ticker buckets — the manual itr = map.erase(itr) dance is gone.
• std::views::cartesian_product (C++23) over the ticker’s alert set and broker set — one loop replaces the nested for (alert) for (broker). Bonus: rewriting forced me to notice the original code’s subtle bug — a break where continue was correct. break bailed out of the entire broker loop when one broker hit its rate limit, skipping other brokers who would still have accepted the alert. The cartesian iteration makes continue the only natural choice.
• std::ranges::count_if instead of the iterator-pair std::count_if — reads cleaner and infers the sentinel.

Every inner iteration still does a brokers_.at(broker_id) — a red-black tree traversal that loads the whole tuple into L1, then discards most of it. The count_if over plan_alerts is also O(|set|) per check, calling alerts_.at(other) again each time. This is the cost AoS pays.

Try the AoS version: godbolt.org/z/17vxWhzMj

The SoA Rewrite

Each field becomes a dense column. An unordered_map<Id, size_t> translates external ids to row indices; the ticker indices store row indices directly, so the inner loop reads from the vectors without another hashmap hop.

class PriceAlertRouter
{
public:
    void add_broker(BrokerId, VolatilityThreshold, AlertsPerSec, Tickers const&);
    void remove_broker(BrokerId);
    void add_alert(AlertId, Timestamp_ms, VolatilityThreshold, Tickers const&);
    DispatchPlan publish() const;

private:
    // Broker SoA — each field is a dense column.
    std::vector<BrokerId>            broker_id_;
    std::vector<VolatilityThreshold> broker_min_vol_;
    std::vector<AlertsPerSec>        broker_max_alerts_;
    std::unordered_map<BrokerId, std::size_t> broker_index_;

    // Alert SoA.
    std::vector<AlertId>             alert_id_;
    std::vector<Timestamp_ms>        alert_ts_;
    std::vector<VolatilityThreshold> alert_vol_;
    std::unordered_map<AlertId, std::size_t> alert_index_;

    // Ticker indices hold dense row indices, not ids.
    std::unordered_map<Ticker, std::vector<std::size_t>> broker_rows_by_ticker_;
    std::unordered_map<Ticker, std::vector<std::size_t>> alert_rows_by_ticker_;
};

The matching loop now reads only the columns it needs and uses std::views::cartesian_product to pair alerts × brokers in one sweep. No associative lookups inside the inner loop:

DispatchPlan PriceAlertRouter::publish() const
{
    DispatchPlan plan;
    std::unordered_map<std::uint64_t, int> same_sec_count;
    std::unordered_set<std::uint64_t> already_sent;
    constexpr auto pack = [](std::size_t a, std::size_t b) {
        return (std::uint64_t(a) << 32) | std::uint32_t(b);
    };

    for (auto const& [ticker, broker_rows] : broker_rows_by_ticker_) {
        auto ait = alert_rows_by_ticker_.find(ticker);
        if (ait == alert_rows_by_ticker_.end()) continue;

        for (auto const [a_row, b_row] :
             std::views::cartesian_product(ait->second, broker_rows))
        {
            if (alert_vol_[a_row] < broker_min_vol_[b_row]) continue;         // column read
            if (!already_sent.insert(pack(b_row, a_row)).second) continue;

            const auto a_sec = static_cast<std::uint32_t>(alert_ts_[a_row]) / 1000;
            auto& count = same_sec_count[pack(b_row, a_sec)];
            if (count >= broker_max_alerts_[b_row]) continue;                 // column read
            ++count;
            plan[broker_id_[b_row]].push_back(alert_id_[a_row]);
        }
    }
    std::ranges::for_each(plan, [](auto& kv) { std::ranges::sort(kv.second); });
    return plan;
}

Three wins over the AoS version:

1. Rate limiting is O(1) per insert, not O(|plan[broker]|). The (broker_row, second) → count hashmap replaces the count_if over the growing result set. On the AoS version, a broker receiving N alerts in the same second does O(N²) work; the SoA version stays O(N).
2. Dedup is explicit. The AoS version used std::set insertion to deduplicate when a broker and alert overlap on multiple tickers. The SoA version uses an already_sent hashset keyed by (broker_row, alert_row) — same effect, but decoupled from result storage.
3. Removal stays contiguous. remove_broker does swap-and-pop across the three column vectors, fixes the index map, and patches the ticker index. The arrays never develop holes, so cache prefetch stays useful.

void PriceAlertRouter::remove_broker(BrokerId id)
{
    auto it = broker_index_.find(id);
    if (it == broker_index_.end()) return;

    const std::size_t row = it->second;
    const std::size_t last = broker_id_.size() - 1;

    if (row != last) {
        broker_id_[row]         = broker_id_[last];
        broker_min_vol_[row]    = broker_min_vol_[last];
        broker_max_alerts_[row] = broker_max_alerts_[last];
        broker_index_[broker_id_[row]] = row;
    }
    broker_id_.pop_back();
    broker_min_vol_.pop_back();
    broker_max_alerts_.pop_back();
    broker_index_.erase(it);

    // Per-bucket: drop `row`, rename `last` → `row`.
    std::ranges::for_each(broker_rows_by_ticker_, [&](auto& kv) {
        std::erase(kv.second, row);
        std::ranges::replace(kv.second, last, row);
    });
    std::erase_if(broker_rows_by_ticker_,
                  [](auto const& kv) { return kv.second.empty(); });
}

The bucket fixup uses three algorithms in sequence: std::erase (C++20 free function — no more v.erase(std::remove(...), v.end())), std::ranges::replace to rename the tail row’s index, and std::erase_if to prune buckets whose last broker we just removed.

Try the SoA version: godbolt.org/z/EhK5KndxM

Bugs and Subtleties

break where continue should be. The original AoS version broke out of the broker loop the moment one broker hit its rate limit, skipping every broker after it for that alert. None of the single-broker test cases triggered the bug, so the tests passed. Swapping the nested for loops for std::views::cartesian_product made the fix unambiguous — there’s no longer an “inner loop” to break out of, only a continue that moves to the next (alert, broker) pair. A case for letting the algorithm library push you toward the less-bug-prone control flow.

Rate-limit counting against dispatched set. The AoS code’s std::count_if over the already-dispatched alerts works but is subtly quadratic in the number of dispatches per second. At interview pace, this is the kind of thing an interviewer nods at — “what’s the complexity of that inner check?” — and a solid senior answer switches to per-bucket counting without rewriting the whole data model. The SoA version makes it trivial because the storage is already relational.

Multi-ticker dedup. If broker B subscribes to {AAPL, NVDA} and alert A is tagged {AAPL, NVDA}, the outer loop visits the pair twice (once per ticker). Both versions need explicit dedup: AoS gets it for free via std::set insertion into the per-broker result; SoA needs the already_sent hashset because the result is a vector. Pick your poison — set’s O(log N) insert vs vector + hashset’s amortised O(1).

Timestamp → second bucketing. static_cast<uint32_t>(alert_ts) / 1000 treats the timestamp as milliseconds. With float timestamps, rounding can put alerts near a second boundary into the wrong bucket. For an assessment, mention the issue and move on. In production, use integer ms.

Swap-and-pop invalidates cached row indices. Anything holding a row index across a remove_broker call is looking at the wrong broker now. Both the ticker index and broker_index_ need fixups. Get either wrong and the next publish() dispatches to the swapped-in neighbor instead.

Duplicate add_broker. Both versions guard against re-adding. AoS relies on std::map::insert returning false; SoA checks broker_index_.contains(id) explicitly. The AoS one is quieter but easier to miss in review.

When SoA Wins

The real argument for SoA isn’t abstract “cache locality.” It’s two concrete structural properties:

• Hot-path field access is narrow. publish()’s inner loop reads two ints per broker and two per alert. Packing them into separate vectors means each read streams a cache line of 16 threshold values, not 16 broker-id/threshold/rate-limit triples.
• Field widths differ. BrokerId is 4 bytes, VolatilityThreshold is 4, AlertsPerSec is 4, but add std::string tickers in the same struct and you’ve exploded the row size. SoA lets the cold fields (ticker lists, names, metadata) live elsewhere without bloating the hot columns.

For this problem at interview scale (≤1000 brokers, ≤1000 alerts), both versions run in microseconds. The point isn’t to measure the difference — it’s to articulate why you’d choose one over the other. “I’d pick AoS for write-heavy workloads with few fields read per access, SoA when the publish-side read pattern is narrow and hot” is the senior answer.

Try both on Compiler Explorer: AoS godbolt.org/z/17vxWhzMj · SoA godbolt.org/z/EhK5KndxM

Recurring Bug Patterns

Six 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.