Stateful In-Memory Data Structures

What's being tested

These problems test stateful in-memory API design: choosing maps, heaps, sets, queues, and counters that preserve invariants across calls. Interviewers look for deterministic updates, clear edge-case semantics, and complexity awareness under repeated operations, often with light concurrency constraints.

Patterns & templates

• Primary index map — use `dict[id] -> state` for O(1) lookup/update; keep all derived structures synchronized on mutation.

• Bounded recency tracking — use `deque(maxlen=3)` or ring buffer for last-N events; define whether failed/no-op events count.

• Fixed-capacity policy — combine `set` membership with ordered structure like `deque`, `OrderedDict`, or heap; specify eviction rule deterministically.

• Aggregation by composite key — use `dict[(person, trip, category)] += amount`; store money as integer cents, not floating-point.

• Vote-change semantics — track previous user vote in `dict[(article, user)]`; update score by new_vote - old_vote, not by blindly incrementing.

• Thread-safe mutation — wrap compound read-modify-write paths with `Lock`; single dictionary operations are not enough for invariant safety.

• Ranking and tie-breakers — normalize inputs, compute comparable tuples, then sort(key=...); explicitly encode tie rules and invalid-card handling.

Common pitfalls

Pitfall: Maintaining only aggregate totals loses information needed for updates, removals, or vote flips; keep per-entity state plus derived counters.

Pitfall: Using `float` for currency aggregation can introduce rounding bugs; use cents, `Decimal`, or minor currency units.

Pitfall: Hand-waving concurrency with “use a map” misses race conditions between membership checks, evictions, and counter updates.

Practice these

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