Composite Data Structures and O(1) Operations
Asked of: Software Engineer
Last updated
What's being tested
These problems test composite data structures: combining hashes, arrays, linked lists, heaps, trees, or queues so each API operation meets a strict complexity target. Interviewers are probing whether you can maintain invariants across mutations, justify average vs worst-case O(1), and handle edge cases like eviction, deletion, randomness, ordering, and concurrency.
Patterns & templates
-
Hash map + doubly linked list for
LRUCache.get/put:O(1)lookup, remove, insert-at-head; evict tail on capacity overflow. -
Hash map + dynamic array for randomized set:
insert,remove,getRandomaverageO(1); delete via swap-with-last. -
Indexed availability structures for allocation: map resource type to candidate pools; update all affected indexes atomically after allocation or release.
-
Sentinel nodes in mutable sequences: simplify insert/delete near marker or boundaries; preserve cursor/marker invariants after every mutation.
-
Min-heap or ordered map for timers: keep next expiry at top; reprogram the single underlying timer only when earliest deadline changes.
-
Invariant-first API design: define what each structure stores, how duplicates are represented, and exactly when stale entries are cleaned up.
-
Concurrency wrapper around composite mutations: one lock or carefully ordered fine-grained locks; avoid exposing half-updated map/list/array state.
Common pitfalls
Pitfall: Claiming
O(1)deletion from an array without explaining the swap-with-last trick and index-map update.
Pitfall: Forgetting to update both sides of the composite structure, e.g. moving an LRU node but not changing its hash entry or pointers.
Pitfall: Treating randomness, timers, or allocation as “just use a map”; interviewers expect uniform probability, deadline ordering, and fragmentation tradeoffs.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
- Design a restaurant waitlist systemGoogle · Software Engineer · Technical Screen · medium
- Implement an LRU cacheGoogle · Software Engineer · Onsite · medium
- Design an editable sequence with markerGoogle · Software Engineer · Onsite · 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 Structure DesignCoding & Algorithms
- Mutable Data Structures And O(1) DesignCoding & Algorithms
- Stateful Data Structures And OOP API DesignCoding & Algorithms
- Stateful In-Memory Data StructuresCoding & Algorithms
- Core Data Structures, Algorithms, And ComplexityCoding & Algorithms
- LRU Cache And O(1) Data StructuresCoding & Algorithms