In-Memory Stateful Data Modeling

What's being tested

These problems test stateful in-memory modeling: maintaining mutable domain objects, applying commands in order, and returning correct query results after many updates. Interviewers are probing for clean data-structure design, deterministic tie-breaking, predicate evaluation, and careful handling of partial state changes.

Patterns & templates

• Command dispatcher — parse tokens once, route via execute(command), keep validation separate from mutation to avoid half-applied operations.

• Hash-indexed state — use dict/HashMap for tables, rows, orders, and IDs; target O(1) lookup and update.

• Predicate evaluator — represent filters as small AST nodes or closures; support AND/OR, comparison operators, and type-aware comparisons.

• Priority queues by side — buy book orders by max price then earliest time; sell book by min price then earliest time.

• FIFO queues per price level — use Deque for price-time priority; matching is O(fills) after O(log P) price-level lookup.

• Mutation ordering — compute match/fill/delete steps explicitly; update quantities before removing empty orders or price levels.

• Stable tie-breaking — maintain monotonically increasing timestamp/sequence number; never rely on unordered map iteration for deterministic output.

Common pitfalls

Pitfall: Treating an in-memory database like string filtering only; rows need schemas, typed values, missing-column behavior, and compound predicates.

Pitfall: Using one global heap for an order book without lazy deletion or ID tracking; canceled or partially filled orders can reappear incorrectly.

Pitfall: Forgetting partial fills; matching must handle buyer quantity, seller quantity, residual insertion, and exact exhaustion symmetrically.

Practice these

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