Composite Data Structure Design
No single structure hits every bound, so combine them and keep the cross references in sync.
Design (LLD)O(1) amortised for most operationsNew26 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
LRU cache
insert delete getRandom in O(1)
min stack
twitter feed
The template
Get this into muscle memory, then adapt the condition per problem.
// LRU: hash map for lookup + doubly linked list for recency
get(k) { const node = map.get(k); if (!node) return -1; moveToFront(node); return node.val; }
put(k, v) { /* evict tail when over capacity */ }If you are stuck
The generic hint ladder for this pattern, in order.
- 1Write down the required time bound for each operation first.
- 2A hash map gives lookup, a list gives order. Use both.
- 3The hard part is keeping both views consistent on every mutation.
Drill it
Every problem in the bank that uses this pattern.
0 / 26 solved