Stateful In-Memory Data Structures
Asked of: Software Engineer
Last updated

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`forO(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 bynew_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.
Featured in interview prep guides
Practice questions
- Implement logger and card rankingRippling · Software Engineer · Onsite · medium
- Implement a balance tracker and interval mergerRippling · Software Engineer · Technical Screen · medium
- Implement an article voting trackerRippling · Software Engineer · Technical Screen · easy
- Aggregate expenses by person, trip, and categoryRippling · Software Engineer · Onsite · medium
- Track article votes and last three flipsRippling · Software Engineer · Onsite · medium
- Design a music player with favorites capRippling · Software Engineer · Onsite · Medium
- Design a delivery cost aggregatorRippling · Software Engineer · Technical Screen · medium
Related concepts
- In-Memory Stateful Data ModelingCoding & Algorithms
- In-Memory Stateful API DesignCoding & Algorithms
- Stateful Data Structures And OOP API DesignCoding & Algorithms
- Caching And Stateful Data Structure DesignCoding & Algorithms
- Mutable Data Structure DesignCoding & Algorithms
- In-Memory Databases And Query ProcessingSystem Design