Stateful In-Memory Data Structures And Temporal Semantics

What's being tested

These problems test managing stateful in-memory data structures with correct temporal semantics: point/interval updates, versioning/TTL, merge/re-creation rules, and low-latency incremental queries. Interviewers probe algorithmic choices (complexity, correctness on edge cases like duplicates/expiration) and clear reasoning about concurrency and idempotency for state mutations.

Patterns & templates

• Maintain incremental aggregates (counters/sums) by updating deltas on point writes — O(1) per update, O(1) query for tracked aggregates like diagonals.

• Two counters for diagonal sums: track main and anti-diagonal indices, update both on point change; store previous value to subtract before add.

• Hash-based existence / dedupe with hash set/map for detecting consecutive sequences; linear-time scan with O(1) amortized checks.

• Interval map (ordered map / TreeMap) to merge neighboring ranges on insert/delete for dynamic consecutive-range maintenance, O(log n) per op.

• Per-entity versioning: store (version, payload) per key; apply updates only if version newer to enforce re-creation semantics.

• TTL/expiration via min-heap (priority queue) + map for O(log n) eviction; lazily expire on access to avoid synchronous stalls.

• Idempotency keys / sequence numbers for transfers: dedupe by idempotency_id and apply funds movement once; snapshot balances or use compare-and-swap to avoid races.

Tip: prefer lazy eviction plus periodic sweeps for high-throughput in-memory services to avoid blocking writes.

Common pitfalls

Pitfall: forgetting to store the previous value when updating aggregates — leads to double-counting or incorrect totals on overwrites.

Pitfall: using unordered dedupe alone for consecutive-sequence problems — duplicates must be ignored but neighboring-range merges require interval logic.

Pitfall: treating TTL as exact-time removal; clock skew and lazy expiration mean state may persist slightly past TTL — document semantics.

Practice these

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