Mutable Data Structure Design

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 via id -> 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; trade O(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.