आप O(1) get और put के साथ एक LRU कैश को कैसे डिज़ाइन करते हैं?

Question

Accepted Answer

एक **LRU (Least Recently Used) कैश** वह आइटम निकाल देता है जिसे सबसे लंबे समय से एक्सेस नहीं किया गया है जब यह क्षमता तक पहुंचता है। क्लासिक डिज़ाइन एक **hash map** (O(1) lookup) को एक **doubly linked list** (O(1) पुनः क्रमण) के साथ जोड़ता है, जो **O(1) get और put** देता है। ## The two-structure design ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Code ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` `OrderedDict` स्वयं एक hash map जमा doubly linked list है, बिल्कुल ऊपर वर्णित संरचना। | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Why the doubly linked list एक doubly linked list आपको **मध्य से O(1) में एक नोड को अलग करने** की अनुमति देता है (आप इसके `prev`/`next` को रखते हैं), जो एक singly linked list या array के साथ O(n) शिफ्ट के बिना असंभव है। ## यह महत्वपूर्ण क्यों है LRU कैश डेटाबेस, वेब सर्वर और CPUs के सामने बैठते हैं ताकि हॉट डेटा को तेज़ और मेमोरी बाउंडेड रखा जा सके। यह समस्या सीनियर साक्षात्कार में एक प्रमुख है क्योंकि यह दो संरचनाओं को जोड़ने का परीक्षण करता है ताकि *एक दूसरे की कमजोरी को कवर किया जा सके* — एक मुख्य system-design कौशल।