DSA & Algorithms
Part 13 of 16 · DSA Advanced & Company FavoritesDesign Data Structures - LRU/LFU, MinStack, Snapshot, RandomizedSet
Design coding favorites: LRU/LFU, MinStack, Snapshot Array, RandomizedSet with O(1) targets.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The prompt asks for O(1) operations on a custom structure
Prefer
Combine a hash map with an ordered node
LRU is a map plus a doubly linked list. Min stack is two stacks.
- Move the touched node to the front.
- Evict the tail.
- RandomizedSet swaps with the last index before pop.
Alternative
Use one list and scan it
Get and put become linear.
- You delete a node without the previous pointer.
- You keep capacity off by one.
- You reshuffle the whole array on delete.
Map plus order
The hash finds the node. The list keeps the order.
- 1
Put the node in both
Key to node, node in the list. - 2
Touch moves it
LRU moves to the front. LFU bumps a frequency. - 3
Evict the end
Tail for LRU. Lowest frequency for LFU.
Overview
Design coding favorites: LRU/LFU, MinStack, Snapshot Array, RandomizedSet with O(1) targets.
When companies ask this
Recognition cues: design LRU/LFU; MinStack; insert/delete/getRandom O(1); snapshot array; time-based KV.
Company asks: Meta/Amazon/Uber love LRU; Google design clarity.
Mental model
Decisions
- 1
Step 1 Read the required cost of every op
- nextStep 2 Which design?
- ?
Step 2 Which design?
- LRUStep 3a HashMap key to node plus a doubly linked list
- LFUStep 3b HashMap key to node, one LRU list per frequency, minFreq
- O(1) insert, delete, randomStep 3c Array plus index map - swap with last on delete
- 3
Step 3a HashMap key to node plus a doubly linked list
- nextStep 4 get moves the node to the front; put evicts the tail when full
- 4
Step 3b HashMap key to node, one LRU list per frequency, minFreq
- nextStep 5 Access bumps freq; evict the LRU node of the minFreq list
- heap keyed by frequencyFailure path - O(log n) per op misses the O(1) bar
- 5
Step 3c Array plus index map - swap with last on delete
- 6
Step 4 get moves the node to the front; put evicts the tail when full
- 7
Step 5 Access bumps freq; evict the LRU node of the minFreq list
- 8
Failure path - O(log n) per op misses the O(1) bar
Lesson map
Design Data Structures - LRU/LFU, MinStack, Snapshot, RandomizedSet
Design coding favorites: LRU/LFU, MinStack, Snapshot Array, RandomizedSet with O(1) targets.
Architecture. Step 1 Read the required cost of every op Ready. Step 2 Which design? Ready. Step 3a HashMap key to node plus a doubly linked list Ready. Step 3b HashMap key to node, one LRU list per frequency, minFreq Ready. Step 3c Array plus index map - swap with last on delete Ready. Step 4 get moves the node to the front; put evicts the tail when full Ready. Step 5 Access bumps freq; evict the LRU node of the minFreq list Ready. Failure path - O(log n) per op misses the O(1) bar Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Q["Step 1 Read the required cost of every op Ready"] L["Step 2 Which design? Ready"] A["Step 3a HashMap key to node plus a doubly linked list Ready"] B["Step 3b HashMap key to node, one LRU list per frequency, minFreq Ready"] C["Step 3c Array plus index map - swap with last on delete Ready"] G["Step 4 get moves the node to the front put evicts the tail when full Ready"] H["Step 5 Access bumps freq evict the LRU node of the minFreq list Ready"] F["Failure path - O(log n) per op misses the O(1) bar Ready"] Q -->|continues| L L -->|LRU| A L -->|LFU| B L -->|O(1) insert, delete, random| C A -->|continues| G B -->|continues| H B -->|heap keyed by frequency| F
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- LRU get/put O(1); RandomizedSet O(1) avg.
- Pitfalls: get must move to front; delete node from map on eviction; swap-remove index update.
Interviewer traps
LeetCode drill (real problems)
- LRU Cache
- LFU Cache
- Min Stack
- Insert Delete GetRandom O(1)
- Snapshot Array
- Time Based Key-Value Store
- Design Twitter
- Design Circular Queue
- Design HashMap
YouTube
Interview Q&A
LRU structures?
Answer
HashMap + doubly linked list.
Why DLL?
Answer
O(1) move/remove with node pointer.
RandomizedSet delete?
Answer
Swap with last; update index map.
MinStack?
Answer
Parallel min stack or store pairs.
LFU?
Answer
Freq map of DLLs; track min freq.
Snapshot?
Answer
Append (snap_id, val); bisect.
Related wave-1?
Answer
hashing, heaps, linked-lists.
Thread safety?
Answer
Mention locks; see concurrency doc.