Combine two or more data structures to satisfy specific operation-complexity requirements — a hash map plus a doubly linked list is the classic combo for O(1) cache operations.
Sub-patterns
- A — Cache Design (LRU/LFU). Hash map plus doubly linked list for O(1) get/put.
- B — Iterator Design. Custom iteration order or lazy evaluation over a nested structure.
- C — Hash Map + List for O(1) Random Ops. Insert, delete, and getRandom all in O(1).
Practice set (7)
- Easy — Design HashMap
- Medium — LRU Cache, Insert Delete GetRandom O(1), Design Twitter, Flatten Nested List Iterator
- Hard — LFU Cache, All O`one Data Structure
Pending
Cache Design (LRU/LFU)
Hash map plus doubly linked list, giving O(1) get/put with eviction on capacity.
Pending
Iterator Design
Custom iteration order, or lazy evaluation, over a nested or irregular structure.
Pending
Hash Map + List for O(1) Random Ops
Insert, delete, and getRandom all in O(1) by pairing a hash map with a swap-to-end array.
Notes from readers
Comments — via GitHub