Composite Data Structures and O(1) Operations

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, getRandom average O(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.