Mutable Data Structure Design
Asked of: Software Engineer
Last updated

What's being tested
Mutable data structure design tests whether you can maintain changing state with clear invariants, efficient updates, and correct tie-breaking. Expect queues, heaps, linked lists, hash maps, ordered sets, and capacity accounting under operations like insert, delete, move, expire, and evict.
Patterns & templates
-
Hash map + doubly linked list for
O(1)insert/delete/move; use sentinels to simplify edge cases around head/tail updates. -
Heap-backed scheduler for timers or eviction —
O(log n)add/cancel/pop; handle stale heap entries with lazy deletion viaid -> active. -
Two queues simulation for turnstiles/waitlists — process time monotonically, preserve FIFO within classes, encode priority rules explicitly.
-
Ordered waitlist selection often needs
TreeMap/balanced BST by party size or timestamp; tradeO(log n)updates for fast capacity queries. -
Capacity accounting invariants — maintain global bytes/items and per-owner totals; every mutation must update all counters atomically.
-
Marker/cursor sequence design — use linked list, gap buffer, rope, or indexed tree depending on whether moves, inserts, deletes, or random access dominate.
-
API-first reasoning — define operation semantics, return values, duplicate handling, cancellation behavior, and tie-breaking before choosing data structures.
Common pitfalls
Pitfall: Picking an array/list first, then discovering middle deletion or cursor movement makes operations
O(n)under heavy mutation.
Pitfall: Forgetting stale heap entries after cancellation or priority changes; always validate popped entries against current authoritative state.
Pitfall: Leaving tie-breakers implicit, especially same timestamp, same priority, empty-state behavior, or simultaneous capacity constraints.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Compute Turnstile Crossing TimesGoogle · Software Engineer · Technical Screen · hard
- Design a restaurant waitlist systemGoogle · Software Engineer · Technical Screen · medium
- Design an editable sequence with markerGoogle · Software Engineer · Onsite · medium
- Implement an LRU cacheGoogle · Software Engineer · Onsite · medium
- Design Tic-Tac-Toe With K PlayersGoogle · Software Engineer · Technical Screen · medium
- Implement Batched Undo/Redo LayerGoogle · Software Engineer · Technical Screen · easy
- Design set with O(1) random accessGoogle · Software Engineer · Technical Screen · medium
- Design a multi-timer using single underlying timerGoogle · Software Engineer · Take-home Project · medium
- Design server allocation for multi-type nodesGoogle · Software Engineer · Technical Screen · Medium
- Design log management with auto-deletionGoogle · Software Engineer · Technical Screen · medium
- Design a prioritized log manager with evictionGoogle · Software Engineer · Technical Screen · hard
Related concepts
- Mutable Data Structures And O(1) DesignCoding & Algorithms
- Composite Data Structures and O(1) OperationsCoding & Algorithms
- Stateful Data Structures And OOP API DesignCoding & Algorithms
- Stateful In-Memory Data StructuresCoding & Algorithms
- Caching And Stateful Data Structure DesignCoding & Algorithms
- In-Memory Stateful Data ModelingCoding & Algorithms