Data Structure Design Interview Notes
Common O(1)/amortized O(1) structure designs：setAll map, LRU, random set, median stream
#resource / algorithm
#type / concept
#status / growing
#ds / hash
[!info] related notes 算法面试题型 MOC
Data Structure Design Interview Notes
setAll HashMap
- Store for each key:
(value, setTime). - Maintain global
(setAllValue, setAllTime). get(k)returns key’s value ifkeyTime > setAllTime, else returnssetAllValue.
LRU Cache
- HashMap for key -> node.
- Doubly linked list for recency order.
- Operations:
get: move node to tail.put: update + move, or insert; if over capacity, evict head.
Insert/Delete/GetRandom in O(1)
- Array stores values.
- HashMap stores value -> index in array.
- Delete by swapping with last element and updating index.
GetRandom with Duplicates Allowed
- Similar, but value -> set of indices.
Median from Data Stream
- Two heaps:
- max-heap for smaller half
- min-heap for larger half
- Balance sizes so that size diff <= 1.