तपाई O(1) get र put सहित LRU cache कसरी डिजाइन गर्नुहुन्छ?

Question

Accepted Answer

एक **LRU (Least Recently Used) cache** ले आइटमलाई निष्कासन गर्छ जुन सबैभन्दा लामो समयको लागि पहुँच गरिएको छैन जब यो क्षमतामा पुग्छ। क्लासिक डिजाइनले **hash map** (O(1) lookup) लाई **doubly linked list** (O(1) reordering) सँग संयोजन गर्छ, जसले **O(1) get र put** दिन्छ। ## दुई-संरचना डिजाइन ```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 हो, ठीक उपर वर्णन गरिएको संरचना। | अपरेशन | समय | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Doubly linked list किन एक doubly linked list ले तपाईलाई **मध्यबाट नोडलाई O(1) मा अलग गर्न** दिन्छ (तपाई यसको `prev`/`next` राख्नुहुन्छ), जो singly linked list वा array सँग O(n) shift बिना असम्भव छ। ## यो किन महत्त्वपूर्ण छ LRU caches डेटाबेस, web servers, र CPUs को अगाडि बस्छन् ताकि होट डेटा द्रुत र मेमोरी सीमित रहोस्। यो समस्या एक वरिष्ठ अन्तर्वार्ता प्रधान हो किनभने यो दुई संरचनालाई संयोजन गर्ने परीक्षा गर्छ ताकि *एकले अर्कोको कमजोरीलाई कभर गर्छ* — एक कुञ्जी प्रणाली-डिजाइन कौशल।