Mutable Data Structures And O(1) Design

What's being tested

You’re being tested on mutable data structure invariants: how to update pointers, indices, maps, queues, and tree links without breaking correctness. The strongest answers combine the right structure pairings—hash map + list, array + index set, deque + window—with clear O(1) or O(n) complexity arguments.

Patterns & templates

• Hash map + doubly linked list for LRUCache — get/put in O(1); always move touched nodes to head.

• Array + hash map of index sets for randomized multiset — insert, remove, getRandom average O(1); swap-delete from array tail.

• Monotonic deque for sliding maximum — keep indices in decreasing value order; pop expired indices before reading window max.

• Pointer rewiring for linked-list deletion — use dummy head, track prev/curr; handle deleting head, tail, and repeated values.

• Binary tree deletion via replacement — for BSTs, replace with inorder successor/predecessor; for general trees, define deletion semantics first.

• Shape normalization for distinct islands — DFS/BFS record relative offsets or path signatures; avoid absolute coordinates and traversal-order ambiguity.

• Frequency aggregation with heaps or maps — use Counter/hash map first, then heap/bucket depending on required ordering and complexity.

Common pitfalls

Pitfall: Claiming O(1) deletion from an array-backed randomized set without explaining the swap-with-last index update.

Pitfall: Forgetting stale indices in a sliding-window deque, causing maxima from outside the current window.

Pitfall: Mutating linked lists or trees without covering root/head deletion, single-node structures, duplicates, and null children.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.