Optiver Software Engineer Interview Prep Guide

Focus most on DP refreshers, system design fundamentals, concurrency/low-level design, and C++ implementation details because you called these out directly and your System Design self-rating is 1/5. You're comfortable with graph algorithms, so graph coverage is brief while the saved time goes toward Optiver-style simulation and matching-engine problems. The Optiver-specific emphasis is on deterministic event-driven simulations, order book/matching data structures, low-latency C++ service design, and fast probability/numerical reasoning. With 1–3 months available, this plan assumes repeated weekly cycles: implement under time pressure, review edge cases, then explain complexity and failure modes out loud.

Technical Screen — 47 min

Coding & Algorithms

• Dynamic Programming Patterns For Coding Interviews (Focus) — covered in depth under Take-home Project below.

• Stateful Event-Driven Simulation And Allocation (Focus) — covered in depth under Take-home Project below.

• Order Book And Matching Engine Data Structures (Focus) — covered in depth under Take-home Project below.

System Design

Focus area — Your System Design self-rating is 1/5; use this to practice queues, backpressure, delivery guarantees, and API trade-offs.

What's being tested

Candidates must design a scalable, robust topic subscription push system that maps publishers to subscribers while meeting latency, ordering, and delivery guarantees. Interviewers probe tradeoff reasoning: throughput vs consistency, fan-out strategies, backpressure, and failure/retry semantics — all skills central to backend systems engineering at low-latency firms.

Core knowledge

• Push vs pull: Push actively delivers to subscribers (lower latency) but requires backpressure handling; pull gives subscriber-controlled pacing at the cost of higher tail latency and more load on brokers.

• Fan-out math: If publishers emit rate $R$ and average fan-out is $f$, delivery rate ≈ $R\times f$. Use this to size brokers, network, and persistence layers.

• Partitioning & sharding: Partition by topic or subscriber; per-partition ordering needs sticky-key assignment. Partition count should match consumer parallelism; oversharding increases coordination cost.

• Broker choices: Kafka suits high-throughput durable logs with consumer pull semantics; NATS/Redis/RabbitMQ can do lower-latency push or lightweight pub/sub with different persistence and delivery semantics.

• Delivery semantics: Understand at-most-once, at-least-once, and exactly-once; exactly-once requires idempotency + transactional sinks or deduplication tokens, expensive at scale.

• Ack & retry model: Use explicit acks with exponential backoff and capped retries; store dead-letter messages after retry budget exhaustion to preserve observability.

• Ordering guarantees: Strict per-subscriber ordering ≈ single-threaded delivery per partition; parallelism trades throughput for ordering complexity and requires sequence numbers and reordering buffers.

• Backpressure & buffering: Implement per-subscriber queues with bounded buffers and policies: drop-oldest, drop-new, or slow-consumer splintering (move to offline store). Monitor p99 queue sizes and delivery latency.

• Rate limiting: Enforce per-subscriber sliding-window limits using token buckets or leaky buckets; implement on edge servers to avoid broker overload.

• Deduplication: Use message IDs and a sliding-time hash (bounded by retention) or stable offsets; memory/time bounds determine dedup window and false-positive risk.

• State & persistence: Use durable storage (Kafka, Postgres) for retention; ephemeral in-memory queues for low-latency delivery with checkpointing for recovery.

• Security & auth: Use mutual TLS or token-based auth, and topic ACLs for publisher/subscriber authorization; enforce quotas to prevent noisy-neighbor effects.

Worked example — Design a subscription push service

Start by clarifying SLAs: expected message rate, average fan-out, delivery latency SLO and ordering requirements. Declare assumptions: durable storage required, subscribers reachable over HTTP/2 gRPC, and per-subscriber delivery limit of X messages/sec. Organize the solution into three pillars: ingest & persistence, fan-out & delivery, and reliability/observability. For ingest, propose a front-end API that writes to a durable append-only log (Kafka) partitioned by topic; this decouples producers and delivery. For fan-out, use worker pools that read partitions, expand messages to subscriber lists via a subscription index (stored in Redis or Postgres), and push asynchronously over connection pools with per-subscriber rate limiting. For reliability, implement ack/retry with per-delivery state, a deduplication cache (bounded TTL), and a dead-letter store for permanent failures. Flag the tradeoff: synchronous push to live subscribers gives low latency but requires expensive connection management and complex backpressure; an alternative is hybrid push/pull where offline or slow subscribers pull from a retained queue. Close by saying: if I had more time I'd prototype end-to-end failure scenarios, quantify latencies at target load, and sketch monitoring dashboards for p99 delivery times and retry rates.

A second angle — Design a topic-based news subscription system

This framing emphasizes relevance filtering, per-subscriber delivery limits, and de-duplication for similar news items. Keep the same pipelines but add a pre-fan-out filtering stage that evaluates user preferences and dynamic relevance scores (stateless worker or cacheable rules). Implement sliding-window rate limits per subscriber using token buckets and de-duplication across near-duplicate headlines using content hashes and short retention. The ordering requirement may be relaxed (news are often independent), allowing more aggressive parallel fan-out and partitioning by topic for throughput. Here, storage retention may be shorter and deduplication accuracy matters more than strict exactly-once delivery.

Common pitfalls

Pitfall: Assuming push means you can ignore backpressure. Without bounded per-subscriber queues and drop/retry policies, a few slow subscribers can exhaust memory or block delivery workers system-wide.

Pitfall: Designing for average fan-out, not tail. Systems sized to average load collapse under bursts; always plan capacity for $p95$–$p99$ spikes and use admission control or throttling.

Pitfall: Chasing exactly-once by default. Exactly-once semantics add coordination and latency; prefer idempotent delivery and deduplication unless business correctness mandates stronger guarantees.

Connections

Interviewers may pivot to adjacent topics: stream processing (windowing, stateful operators, Flink/Kafka Streams) for in-pipeline filtering and aggregation, or load testing & benchmarking to validate throughput/latency claims. They might also ask about client-side designs (reconnect/backoff, exponential jitter) and deployment strategies (blue/green, canary).

Further reading

• [Designing Data-Intensive Applications — Martin Kleppmann] — deep treatment of messaging, logs, and replication tradeoffs, useful for consistency/ordering reasoning.

• Kafka documentation — foundational for append-only log semantics, partitioning, retention, and consumer-group delivery models.

Practice questions

Focus area — You called out low-level system design gaps; focus on latency, queues, batching, memory layout, threading, and failure modes.

What's being tested

Interviewers probe your ability to design and reason about low-latency, high-throughput C++ services: efficient use of CPU, memory, and networking; concurrency models that avoid contention; and pragmatic tradeoffs between latency, throughput, and correctness. They want to see that you can turn SLOs (throughput, p99/p999 latency) into concrete architecture, pick appropriate data structures and synchronization, and identify hot-path optimizations and observability hooks.

Core knowledge

• Latency vs throughput tradeoff: know that batching increases throughput but raises latency; quantify with Little's Law $L = \lambda W$ and relate queue depth to tail latency.

• CPU cost budgeting: a 3GHz core ~3e9 cycles/s; if hot-path needs 300 cycles, max throughput/core ≈ 10M ops/s; use this to dimension cores and sharding.

• Cache and false sharing: align hot objects to cache-line boundaries (typically 64B); pad per-thread counters to avoid cross-core invalidations.

• Lock-free / wait-free primitives: use std::atomic with appropriate memory_order_* semantics; prefer SPSC/SPSC ring buffers (Disruptor-style) for handoff to avoid blocking syscall overhead.

• Work partitioning: prefer sharding by key (affinity) to make processors own state exclusively, eliminating cross-shard locks and enabling linear scalability.

• Network I/O patterns: for high rate use recvmmsg/sendmmsg batching or kernel-bypass DPDK/PF_RING; fallback is io_uring for async I/O on modern Linux, epoll for scalable event demux.

• Memory allocation: avoid per-message new/delete; use object pools, per-thread arenas, or jemalloc/tcmalloc with per-thread caches to avoid contention and fragmentation.

• Polling vs interrupt: busy-polling reduces latency jitter; use adaptive busy-polling only where SLOs demand it, because it consumes CPU.

• I/O zero-copy: use scatter/gather syscalls and pinned mmap/huge pages where copying dominates CPU; for NIC-level zero-copy consider DPDK/RDMA when required.

• NUMA and thread affinity: bind threads and memory to CPU sockets to avoid remote memory access; measure with numactl and pin via sched_setaffinity.

• Profiling toolchain: use perf, bpftools, VTune, gdb, heaptrack, and flamegraphs; measure p50/p95/p99 across end-to-end path, not only function-level.

• Failure and correctness: design for graceful degradation (backpressure, drop-in favor of tail control), idempotency for retries, and audit logs for post-mortem. Persist critical events asynchronously with strict ordering if required.

Worked example — "Design a low-latency order ingestion and matching service in C++"

First 30s clarifying questions: target throughput (orders/sec, messages/sec), latency SLOs (p50/p99), loss tolerance, protocol (UDP/TCP), persistence durability (sync/async), and deployment topology (single machine or cluster). Skeleton of a strong answer:

1. Ingress: high-performance packet reader (recvmmsg/DPDK) with minimal parsing, deserialize in-place.

2. Demux & validation: per-instrument shard mapping to a single core/thread to avoid locking.

3. Matching core: in-memory order book per shard, implemented with cache-friendly data structures (arrays + index maps), and risk checks inline.

4. Acks/persistence: ack to client immediately; persist trades/events asynchronously via batching to disk or append-only log.

5. Observability and backpressure: track queue depths, latencies, and apply backpressure (reject or throttle) when queues exceed thresholds.

Key tradeoff to flag: synchronous persistence increases durability but multiplies latency—use batched fsync with bounded queueing to keep p99 within SLO. Close by saying: "If more time, I'd prototype the hot-path with microbenchmarks, run perf to find mem-copy hotspots, and present measured CPU/latency envelopes."

A second angle — "Scale a C++ market-data consumer to 1M messages/sec with p99 < 200µs"

Here the workload is read-only and multicast-heavy. Design pivots:

• Use recvmsg/recvmmsg with large batch sizes or DPDK to avoid kernel overhead.

• Decode messages in-place; employ a preallocated object pool and per-thread caches to avoid allocations.

• Maintain per-subscription state on the consuming thread; push updates to consumers via lock-free ring buffers.

• Optimize for memory layout (struct-of-arrays vs array-of-structs) depending on access pattern to improve SIMD/prefetch.

Constraints change tradeoffs: since no persistence and fewer consistency needs, accept looser ordering for performance, but implement sequence-number checks and small reassembly buffers to detect and heal gaps.

Common pitfalls

Pitfall: Confusing average latency with tail latency. Averaging hides jitter; designing for p50 but not p99/p999 will fail real workloads. Always instrument and budget for tails.

Pitfall: Reaching for locks first. Saying "we'll lock a shared map" in a high-throughput hot path is tempting but unacceptable; instead show partitioning, lock-striping, or lock-free alternatives and measure their costs.

Pitfall: Omitting observability and test harness. A design that lacks microbenchmarks, synthetic-load tests, and perf-driven measurement is speculation. Propose specific metrics and how you'd load-test the service.

Connections

Interviewers may pivot to distributed consistency (e.g., ordering across shards) or to hardware acceleration (FPGA/NIC offload) once low-level design is solid. They might also ask about fault tolerance patterns (replication, consensus) if the role intersects reliability.

Further reading

• [LMAX Disruptor paper/blog] — seminal design pattern for low-latency ring buffers and SPSC/SPSC handoff.

• Brendan Gregg, Systems Performance — deep systems profiling and performance analysis techniques.

• [Intel/DPDK documentation] — when you need kernel-bypass networking, this is the canonical source.

Practice questions

Software Engineering Fundamentals

Focus area — You explicitly noted limited concurrency and low-level experience, so focus on races, locks, atomics, scheduling, and determinism.

What's being tested

Interviewers probe your ability to reason about concurrency primitives, OS threads, and memory model interactions to build correct, low-latency, deterministic software. They expect clear tradeoffs between user-space and kernel mechanisms, measurable costs (context-switch, cache effects, page faults), and practical synchronization choices. Optiver values predictable latency and correctness under load, so show how your design guarantees ordering, atomicity, and recoverability.

Core knowledge

• Process vs thread: a process is an isolated address space; a thread shares that space and file descriptors. On Linux use `fork`/`exec` and `pthread` APIs to illustrate differences.

• Virtual memory and page fault handling: kernel resolves faults, possibly loading pages via `mmap`; page faults cost micro- to milliseconds depending on IO. Expect copy-on-write semantics after `fork`.

• TLB, CPU caches, and cache coherence: TLB misses and cache line invalidation dominate latency; false sharing (adjacent fields on same cache line) kills throughput on multicore.

• Memory ordering and memory barrier: languages expose weaker models; use `std::atomic` with acquire-release semantics or full fences (`atomic_thread_fence`) to enforce ordering, not just volatile.

• Atomic operations and lock-free: `compare_exchange_strong` and `fetch_add` are cheap on a single core but cost cache-coherence traffic cross-core; use only when correctness and progress are proven.

• Locks tradeoffs: mutex (blocking, uses `futex` on Linux) reduces CPU spin but causes context switches; spinlock wastes cycles but is preferable for very short critical sections on same NUMA node.

• Context switch and syscall costs: a context switch can cost thousands of cycles; a syscall (user→kernel→user) adds overhead—batch small operations or use shared-memory/eventfd to avoid frequent syscalls.

• Scheduler & preemption: kernel scheduler decisions (timeslices, priority) affect latency and fairness; be aware of priority inversion and mitigation (priority inheritance, `SCHED_FIFO` tweaks).

• Heap vs stack: per-thread stack is fixed and cheap; dynamic allocations (`malloc`, `mmap`) have fragmentation and locking costs; use per-thread caches (arenas) for high throughput.

• NUMA and locality: memory access latency depends on node affinity; pin threads (`pthread_setaffinity_np`) and allocate (`numa_alloc_onnode`) to reduce remote memory penalties.

• Amdahl's law quantifies parallel speedup: $S(N)=\frac{1}{(1-p)+p/N}$ — optimize the parallel fraction p and minimize serial bottlenecks for low-latency systems.

Worked example — Design an Event-Driven CPU Overheat Controller

Frame: ask for simulation granularity, number of cores, deterministic ordering, whether events can be simultaneous, and cooling-actuator latency. Key pillars: (1) represent each core as a finite-state machine (per-core state) with temperature and cooling mode, (2) use an ordered event stream (monotonic timestamps + tie-breaker) to drive deterministic transitions, (3) a scheduling model for actuators (shared vs per-core cooling) and atomic updates, (4) safe shutdown and idempotent transition logging. Implementation sketch: choose a single-threaded event loop for determinism or a multi-threaded worker pool with a global sequencer (sequence numbers) to preserve ordering; use a deterministic priority queue for pending events and versioned state to detect out-of-order processing. Tradeoff: a single-threaded loop is simple and deterministic but may not meet wall-clock throughput; a multi-threaded design gains parallelism at the cost of complexity (synchronization, replay). Close by proposing test harnesses (fuzzed timestamped traces), deterministic replay logs, and monitoring hooks; say "if more time, I'd add persisted event logs and state checkpoints for crash recovery."

A second angle — Explain OS processes, threads, and memory

When asked to explain core OS abstractions, start by differentiating user-space and kernel-space responsibilities: address spaces, descriptors, and process isolation live in kernel-managed structures. Emphasize threading models: kernel threads vs user-level threads, and consequences for blocking syscalls. Discuss memory mapping (`mmap`) versus anonymous heap, and the role of page tables and TLBs. Show how scheduling and preemption interact with synchronization primitives (e.g., why a blocking mutex can hide latency but introduces context-switch cost). Finish by describing common developer APIs (`pthread_create`, `std::thread`, `madvise`) and when you'd prefer each.

Common pitfalls

Pitfall: Equating threads with processes.
Many candidates answer interchangeably; explicitly state differences in address space, descriptor sharing, and copy-on-write behavior to avoid missing isolation and performance implications.

Pitfall: Optimizing for assumed contention without measurement.
Jumping to lock-free data structures is tempting; explain why you'd instrument (`perf`, `latency histograms`) first and prefer per-thread batching or fine-grained locking unless hot-path contention is proven.

Pitfall: Not calling out non-functional requirements.
Failing to state determinism, failure modes, or test plans costs points; always describe how you'd validate ordering, recover from crashes, and measure `p99` latency.

Connections

Interviewers may pivot to I/O multiplexing (`epoll`/`kqueue`), low-latency memory allocators and garbage collection impact, or distributed synchronization (consensus, clock sync) when the scope grows beyond a single host. Be ready to discuss profiling tools (`perf`, `eBPF`) and kernel tuning knobs.

Further reading

• Operating Systems: Three Easy Pieces — practical chapters on virtual memory, concurrency, and scheduling.

• The Art of Multiprocessor Programming — deep coverage of lock-free algorithms and memory models; good for proofs and concurrent data structures.

Practice questions

Focus area — You will interview in C++; emphasize STL choice, iterator safety, ownership, const correctness, and predictable performance.

What's being tested

Interviewers probe practical mastery of the C++ Standard Library: picking the right container/algorithm, understanding performance costs (time, memory, cache behavior), and exposing tradeoffs under real constraints. Optiver cares because low-latency, high-throughput systems require predictable resource use and micro-optimizations that change real P&L risk. Expect questions that validate you can measure, reason about, and communicate those tradeoffs clearly.

Core knowledge

• std::vector: amortized O(1) push_back, contiguous storage, cheap random access O(1), reallocation invalidates pointers/iterators; use reserve() to eliminate reallocations and control growth costs.

• std::deque: segmented contiguous blocks; constant-time push_front/push_back, non-contiguous memory so pointers may be stable across some ops but not guaranteed; index access is O(1) with slightly worse locality than vector.

• std::list / std::forward_list: node-based linked lists; constant-time splice/erase given iterator, poor cache locality; avoid for large-scale numeric data or frequent random access.

• std::map vs std::unordered_map: ordered tree O(log n) vs hash O(1) average; unordered_map pays hashing cost and cache-randomness; use reserve()/max_load_factor() to avoid rehash thrash on hot paths.

• Iterator invalidation rules: each container has precise rules — vector and string invalidate on reallocation, deque invalidates on insert/erase at ends for iterators to affected blocks, associative containers keep iterators stable except for erased elements.

• Erase-remove idiom: use v.erase(std::remove_if(...), v.end()) for predicate removals in vector; erase in the middle is O(n) because elements shift — account for that cost.

• emplace vs insert/push_back: prefer emplace_back() for in-place construction to avoid copies/moves, especially for heavy types; but measure: modern compilers optimize many cases.

• std::sort complexity: typically introsort O(n log n) average and worst-case, stable sort is std::stable_sort (O(n log n) with extra memory); avoid repeatedly sorting when incremental updates suffice.

• Move semantics and swap: std::move enables cheap transfers of resources; swapping containers is O(1) for most standard containers — use swap instead of element-wise moves when you can.

• Cache locality and profiling: contiguous containers (vector) have superior cache behavior; hash tables and linked structures scatter memory; profile with realistic workloads (perf, callgrind) rather than microbenchmarks.

Worked example — "Optimize in-place removal of duplicates from a large unsorted std::vector<T>"

Start by clarifying constraints: must preserve relative order? Is extra memory allowed? Is T hashable or only comparable? A strong candidate states assumptions and two main approaches: (1) preserve order using a hash-set scan and in-place compaction, (2) drop order and sort+unique. Skeleton: choose algorithm based on memory/time tradeoff; implement carefully to avoid unnecessary allocations. For preserve-order: create a std::unordered_set<T> with reserve(v.size()*1.3) to avoid rehashes, iterate vector writing unseen elements to write-index (index overwrite pattern), then resize(write_index). For unordered approach: sorting uses O(n log n) time, less extra memory, but destroys order. Tradeoff to flag: unordered_set uses more memory and random-memory accesses hurting cache; sort is CPU-bound but benefits from contiguous memory. Close by saying: if more time, I'd benchmark realistic input distributions, consider a robin-hood hash or parallelize with partitioned hashing, and measure allocator behavior.

A second angle — "Choose between std::vector and std::deque for a high-throughput queue"

Frame the need: do you need frequent push_front and push_back, stable pointers to elements, or contiguous memory for memcpy/SIMD? If the priority is raw throughput with mostly tail operations, std::vector with a circular-index ring buffer (manual head/tail indices and reserve) often outperforms std::deque because of better locality. If you need guaranteed cheap front insertions with unpredictable size and don't need contiguous blocks, std::deque fits. Mention iterator invalidation: vector reallocation invalidates pointers; deque can keep element references valid across some operations. Close by recommending microbenchmarks for your typical element size and access patterns.

Common pitfalls

Pitfall: assuming erase from the middle of a std::vector is cheap — it’s O(n) due to element shifting; for repeated deletions prefer compaction or a different data structure.

Pitfall: using std::unordered_map without reserve() and expecting stable performance — growing and rehashing will spike latency; pre-reserve based on expected cardinality.

Pitfall: optimizing micro-level operations without profiling — changing from vector to deque or swapping algorithms can worsen overall throughput because of cache effects; always validate with representative workloads.

Connections

Interviewers may pivot to concurrency (thread-safety of containers, lock-free structures) or custom allocators (pooling to reduce allocation overhead). They might also connect to profiling/benchmarking practices and memory-leak/UB diagnostics.

Further reading

• [Effective Modern C++ — Scott Meyers] — guidance on move semantics, emplace, and modern idioms.

• [C++ Standard Library: A Tutorial and Reference — Nicolai Josuttis] — deep reference for container guarantees and complexity.

• cppreference.com — authoritative, up-to-date reference for iterator invalidation and function semantics.

Practice questions

Take-home Project — 34 min

Coding & Algorithms

Focus area — You said DP has never been a strength; rebuild core patterns from first principles and practice recurrence design.

What's being tested

Demonstrates ability to convert a problem into a Dynamic Programming state and derive correct transitions, trading time for reuse. Interviewers probe precise state definition, boundary/base cases, complexity reasoning, and when to switch to greedy/graph search. They expect clear memoization/tabulation choices and space/time optimizations.

Patterns & templates

• Top‑down memoization — define recursive dp(state), cache results in a map/array; often easiest to get correctness first.

• Bottom‑up tabulation — build dp[] or dp[][] iteratively; good for guaranteeing O(n)/O(n^2) time and predictable memory.

• Knapsack / subset DP — 0/1 or unbounded variants using dp[w] or dp[i][w]; convert choices into weight/value transitions.

• Sequence DP (LIS/LCS) — use dp[i] or dp[i][j] with clear meaning (best ending at i / best using prefixes i,j); common O(n^2) baseline.

• Bitmask DP — represent subsets as bitmasks for N ≤ ~20, use dp[mask] with O(N*2^N) transitions.

• State compression & rolling arrays — drop a dimension when dp[i] depends only on i-1; convert dp[i][j] to prev[j] to save memory.

Common pitfalls

Pitfall: Defining a state that omits needed context (e.g., forgetting "last taken index") leads to incorrect transitions and overcounting.

Pitfall: Not proving or checking base cases; off‑by‑one in base leads to wrong answers or crashes.

Pitfall: Using naive DP with unnecessary dimensions — causes TLE or MLE when O(n^3) can be reduced to O(n^2) or O(n).

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions

Focus area — Core Optiver pattern and your coding rating is 3/5 with little solved signal, so spend extra implementation time here.

What's being tested

These questions test deterministic event-driven simulation and time-ordered state management: advancing a timeline, processing timestamped events, and maintaining mutable resource state (capacities, temperatures, positions). Interviewers expect correct event ordering, efficient data structures for time/priority queries, and clear tradeoffs between greedy, exact, and approximate allocation algorithms.

Patterns & templates

• Discrete-event simulation: keep an event queue sorted by timestamp, process events in non-decreasing order; use stable ordering for simultaneous events.

• Sweep-line / sort-by-time: sort arrivals/departures O(n log n) then scan, updating state incrementally to avoid per-timestep loops.

• Priority queue / heap for allocation: push candidate resources, pop best-fit in O(log n) per allocation; maintain lazy deletions when state changes.

• Greedy allocation by earliest-departure or best-fit: simple, fast, O(n log n), often optimal for interval-capacity problems.

• Knapsack / DP for exact selection: use capacity-indexed DP when capacities × items reasonable; memory O(capacity) or O(n·capacity).

• Approximation / heuristics: sort by value density or use FPTAS when exact DP is too slow; quantify error guarantees.

• State snapshots & rollbacks: snapshot only mutable fields you need; for rollback use copy-on-write or version timestamps to keep O(1) revert where possible.

Tip: prefer lazy updates (mark stale entries) over eager deletions in heaps to simplify concurrency and state changes.

Common pitfalls

Pitfall: mishandling simultaneous events — failing to define and implement a stable tie-breaker leads to non-deterministic behavior.

Pitfall: forgetting to decrement capacity or marking resources stale in the heap, causing over-allocation or duplicated assignments.

Pitfall: using per-timestep simulation for long intervals — O(time_span) loops blow up; prefer event-driven advances based on event timestamps.

Practice these

the practice cards below cover the canonical variants — solve all of them and time yourself

Practice questions

Focus area — This is the most Optiver-specific data-structure topic; prioritize price-time priority, cancellation, and deterministic matching behavior.

What's being tested

These problems test building an efficient, order book and matching engine for a single symbol: maintaining side-specific best prices, aggregating quantities, and deterministic tie-breaking. Interviewers probe algorithmic choices, data-structure invariants, and correctness under inserts, cancels, modifies, and matches.

Patterns & templates

• Use a price-level map implemented with a balanced tree (std::map) for best-price lookup — best bid/ask in O(log P) where P is active price levels.
• Maintain a per-price FIFO queue (e.g., deque or linked list) to enforce price-time priority and O(1) head pops for fills.
• Keep an unordered_map<orderId, Node*> for direct cancel/modify in O(1) to the order's node and price-level.
• Store aggregated volume per price-level and update on every insert/modify/cancel to answer quantity-at-price in O(1).
• Matching loop: while best-opposite-price exists and top-order.qty > 0, consume min(taker.qty, maker.qty); operations are O(matches * 1) amortized.
• For order modification, treat as cancel+reinsert if price changes to preserve time priority; otherwise update quantity in-place.
• Memory is linear: orders -> O(N); price-levels typically << N; consider node pooling to avoid GC/allocator overhead.

Common pitfalls

Pitfall: Forgetting to decrement the price-level aggregated quantity on cancel leads to incorrect depth and stale best-price decisions.

Pitfall: Using a binary heap for best-price with mutable orders complicates modify/cancel operations and makes O(n) removal common.

Pitfall: Re-inserting a modified order without clarifying whether it should preserve original time priority — always state the assumption and implement accordingly.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions

Statistics & Math

Optiver often values fast quantitative reasoning; keep a steady cadence on expectation, counting, independence, and conditional probability.

What's being tested

Candidates must demonstrate precise probabilistic reasoning and combinatorial counting under constraints, plus the ability to translate those analyses into numerically robust algorithms. Interviewers probe whether you can model discrete stochastic processes (binomial/random walk), apply counting identities (factorials, Catalan/Ballot), and pick pragmatic computation strategies (exact combinatorics vs. approximations). For a Software Engineer at a trading firm, this shows you can reason about discrete event outcomes, manage numeric limits, and clearly state assumptions under time pressure.

Core knowledge

• Linearity of expectation: $E[\sum_i X_i]=\sum_i E[X_i]$ regardless of independence; use to compute expected gains quickly without full distributional work.

• Variance basics: $\mathrm{Var}(X)=E[X^2]-E[X]^2$ and $\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)$ only when independent; flag dependence explicitly.

• Binomial distribution: $P(X=k)={n\choose k}p^k(1-p)^{n-k}$; sums of binomial tails give probabilities for counts of up/down steps. Use cumulative sums or log-sum-exp for numerical stability.

• Normal approximation: For large $n$, use $X\approx N(np,np(1-p))$ with continuity correction; quantify error (rule-of-thumb $np(1-p)\gtrsim 10$).

• Random-walk framing: Model price after $n$ steps as $S_n = S_0 + \sum_{i=1}^n X_i$ with $X_i\in\{\pm1\}$ or general increments; map event constraints to binomial inequalities.

• Permutations with repeats: Number of distinct orderings of multiset with counts $n_1,\dots,n_k$ is $\frac{N!}{\prod_i n_i!}$; compute with logs or big-integer factorial to avoid overflow.

• Nonnegative-paths / Catalan: Sequences that never drop below zero when steps are $\pm1$ map to Dyck paths; for equal up/down count $n$, count is $C_n=\frac{1}{n+1}{2n\choose n}$.

• Ballot theorem / reflection principle: For unequal counts, the count/probability that one side always leads can be computed via $\frac{a-b}{a+b}{a+b\choose a}$ or reflection arguments; useful for “never negative” constraints.

• Computation scale & precision: Factorials blow up; 64-bit safe roughly to $20!$; use BigInteger, prime-mod arithmetic, or log-gamma (lgamma) for larger $n$, and prefer exact combinatorics for $n\le 1000$ only with big-int or modular arithmetic.

• Dynamic programming: For constrained counts (e.g., prefix nonnegativity), use DP over steps and state (current height) in $O(n\cdot H)$ time and $O(H)$ space, where $H$ is max height (bounded by $n$).

• Conditional probability / Bayes: Use $P(A|B)=P(A\cap B)/P(B)$ when conditioning on path events; ensure denominators nonzero and state what information is observed.

• Numerical tactics: Use log-space for products of combinations, iterative multiplicative binomial coefficients to avoid computing full factorials, and precompute Pascal rows for repeated queries.

Worked example — Compute negative-price probability after n steps

First 30 seconds: ask whether steps are symmetric (±1) and independent, initial price $S_0$, and whether "negative" means strictly below zero at time $n$ or hitting negative at any time before $n$. Skeleton answer: (1) model $S_n=S_0+\sum X_i$ with $X_i\in\{\pm1\}$ and reduce to counting number of down steps, (2) express probability as binomial tail $\sum_{k: S_0+(n-2k)<0}{n\choose k}p^k(1-p)^{n-k}$, (3) choose computation: exact binomial sum for small $n$, or normal approximation with continuity correction for large $n$, (4) discuss edge cases like $p\neq 0.5$, non-integer thresholds, or absorbing boundaries. A tradeoff to call out: exact combinatorial sum is simple and correct but numerically unstable for large $n$ — prefer log-domain or use normal approx when $np(1-p)\gtrsim 10$. Close by saying: if I had more time I'd compute the hitting-time probability (ever negative before $n$) via the reflection principle or run Monte Carlo to validate approximation errors.

A second angle — Count nonnegative buy/sell sequences

Reframe: buys=+1, sells=−1; constraint that cumulative sum never negative maps to Dyck/ballot constraints. If buys and sells are equal, use Catalan numbers for exact count. If counts differ, apply the Ballot theorem to get the number or probability that buys always lead. Algorithmically, a strong answer presents a closed-form combinatorial identity, then a DP implementation for arbitrary counts or when you must return sequences themselves. Practical tradeoffs: closed-form is $O(1)$ arithmetic with big-int; DP is $O(n\cdot H)$ and easier to extend to extra constraints (e.g., limited capacity). Explain how to handle large outputs (return counts modulo a prime, or stream-generation of sequences).

Common pitfalls

Pitfall: Treating independence as given. Many candidates sum variances without asking whether increments are independent; explicitly state or test independence before using additivity.

Pitfall: Not stating model assumptions. Failing to ask whether steps are ±1, biased ($p\neq0.5$), or whether "negative" is transient vs. terminal will lead to wrong formulas; say your assumptions up front.

Pitfall: Overusing approximations without error checks. Quoting a normal approximation without continuity correction or bounds on approximation error is tempting but will anger an interviewer; quantify when approximation is acceptable or fallback to exact/log-space sums.

Connections

Interviewers may pivot to Markov chains and hitting-time distributions, generating functions for counting constrained sequences, or numeric topics like stable computation of large combinatorials using lgamma/Stirling approximations. These are natural next steps to extend a correct discrete analysis.

Further reading

• [Feller — An Introduction to Probability Theory and Its Applications (Vol. 1)](William Feller citation) — classic reference for random walks, reflection principle, and ballot results.

• [Graham, Knuth, Patashnik — Concrete Mathematics](book citation) — practical combinatorial identities and counting techniques useful for constrained sequence problems.

Practice questions

Important for Optiver-style timed assessments; practice speed, error recovery, and mental pattern recognition without overinvesting.

What's being tested

Candidates must demonstrate fast, reliable numerical pattern recognition under time pressure: reduce sequences or probability prompts to simple invariants, apply algorithmic templates, and communicate assumptions crisply. Interviewers probe working-memory strategies, choice of heuristics (speed vs. exactness), and ability to prioritize computations that maximize score or insight. For a Software Engineer, this maps to choosing the right algorithmic shortcut, bounding complexity, and signalling trade-offs clearly.

Core knowledge

• Finite differences: take successive differences to detect an arithmetic progression (constant first difference) or a degree‑d polynomial (first nonzero d-th differences constant); compute differences in O(n) time mentally or on paper.

• Ratio test / geometric progression: consecutive-term ratios identify geometric sequences; watch for zeros and sign flips (ratio undefined when preceding term is 0) and prefer integer-ratio rules when plausible.

• Recurrence relations: simple linear recurrences (e.g., Fibonacci) show constant-coefficient relation; test by checking small-order linear combinations of previous terms before assuming high-degree polynomials.

• Parity and modular arithmetic: check parity (odd/even), last-digit cycles, and small-modulus patterns (mod 2,3,5,9) to catch digit-based or cyclic rules quickly; use digit-sum divisibility tests where applicable.

• Occam’s razor for puzzles: prefer the lowest-complexity rule that fits all given terms—usually arithmetic, geometric, linear recurrence, or digit transformation—state this assumption explicitly when answering.

• Linearity of expectation: for timed probability tasks, use E[X]=np and variance Var(X)=np(1−p) for binomial setups; compute expectations directly without full distribution when scoring rewards linear gains.

• Binomial → Normal / Poisson approximations: for n≥30 and p not extreme, use normal approximation with continuity correction; for rare events (small p, large n with λ=np small), use Poisson(λ) as a fast estimate.

• Combinatorics tricks: compute nCk multiplicatively as n*(n−1)*.../(k!) to avoid large factorials; cancel terms early to keep numbers manageable and avoid overflow in mental math.

• Time-budget heuristic: set a per-question cutoff t* based on points-per-question and remaining time; spend rough time proportional to expected-score-per-second, and flag borderline problems to revisit.

• Working-memory tactics: chunking numbers into groups (e.g., 12345 → 12|345), use short scribbles for intermediate results, and verbalize key steps to the interviewer to lock assumptions and reduce rework.

Worked example — Plan for timed probability assessment

First 30 seconds: ask clarifying questions — exact scoring rules, whether guesses are penalized, calculator availability, independence assumptions, and sample-size ranges. Frame the approach into three pillars: (1) compute expected value per question quickly using linearity of expectation, (2) prioritize items by expected-value-to-time ratio, and (3) use fast approximations (Poisson or normal) when exact combinatorics are slow. For a multiple‑choice probability set with partial credit, calculate a quick upper/lower bound to eliminate dominated choices, then apply a multiplicative nCk shortcut only to borderline items. Flag any question needing more time and allocate re-check time at the end. Tradeoff to call out: spending extra time getting an exact combinatorial count might be wasted if a safe approximation secures the most probable answer; state the decision threshold you used. Close by saying: "If I had more time I'd compute exact probabilities for flagged items and cross-validate approximations with one exact case."

A second angle — Find patterns in numeric sequences quickly

The same toolkit applies but with different priorities: focus on rapid, deterministic checks (differences, ratios, parity) rather than probabilistic approximations. Begin by asking whether non-integer or multiple-next-term answers are allowed. Skeleton: (1) test arithmetic and geometric rules, (2) test first and second finite differences for polynomial fits, (3) test simple recurrences (add last two, multiply then add constant), and (4) consider digit transformations or concatenation rules. Where sequence length is short and ambiguous, explicitly state the simplicity criterion (prefer linear or low-degree polynomial) and offer alternate plausible continuations if time permits. Emphasize communicating the assumed rule rather than just giving a next number.

Common pitfalls

Pitfall: Assuming a high-degree polynomial rule too quickly.
Choosing a degree‑k polynomial will always fit k+1 points; prefer lower-complexity rules and state that assumption before presenting an answer.

Pitfall: Not clarifying constraints or scoring.
Failing to ask whether rounding/negative/non-integer values are allowed wastes time and can lead to technically correct but interview-irrelevant answers.

Pitfall: Overcomputing exact combinatorics when an approximation suffices.
Wasting time computing exact nCk by factorials instead of multiplicative cancellation or approximation costs points; use bounds or approximations when within acceptable error.

Connections

Interviewers can pivot to dynamic programming by asking you to generalize a recurrence-heavy sequence into an algorithm, or to complexity analysis by asking time/space trade-offs for computing exact distributions versus approximations. They may also transition to discrete probability puzzles requiring tighter bounds (Chernoff/Hoeffding) if you move toward concentration inequalities.

Further reading

• [Concrete Mathematics — Graham, Knuth, Patashnik] — concise techniques (finite differences, combinatorics) used in contest-style sequence problems and quick combinatorial manipulations.

Practice questions