Stateful In-Memory Ledgers and Versioned Stores

What's being tested

These problems test implementing stateful in-memory ledgers and versioned stores: deterministic, time-ordered mutation application, per-key version history, and efficient historical reads. Interviewers probe correctness under ties/edge timestamps, read performance (historical snapshots), and simple concurrency/atomicity patterns a backend engineer should own.

Patterns & templates

• Event sourcing append-only log per-entity — store (timestamp, seq, op) and order by (ts, seq) for deterministic tie-breaking; append is O(1).

• Per-key history index: keep a vector or linked list per key and binary-search by timestamp for getBalanceAt(ts) in O(log m) where m is versions for that key.

• Tombstones & TTL: record delete markers with expiry metadata; treat tombstone as immutable state and purge lazily to avoid expensive synchronous GC.

• Atomic validation: implement applyEvent() as validate-then-commit using either per-key locks or optimistic CAS; ensure invariants (e.g., balance >= 0) hold before publishing.

• Prefix/range scans: keep keys in a sorted structure (std::map/B-tree) so prefix scans cost O(k + log n) and can iterate historical entries quickly.

• Scheduled jobs: schedule future payments in a time-priority queue (min-heap or calendar queue) and materialize them at execution time with idempotency keys.

• Merge/snapshot semantics: when merging accounts or applying promotions, snapshot rates/balances at effective timestamp to prevent retroactive changes to past reads.

Common pitfalls

Pitfall: assuming in-memory write order equals deterministic commit order — ties must be explicitly broken (timestamp+sequence).

Pitfall: scanning entire history per read — costly; use indexed per-key histories and binary search.

Pitfall: mutating past events (changing earlier ledger entries) instead of emitting compensating events or tombstones, which breaks reproducibility.

Practice these

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