ਤੁਸੀਂ O(1) get ਅਤੇ put ਦੇ ਨਾਲ LRU ਕੈਸ਼ ਨੂੰ ਕਿਵੇਂ ਡਿਜ਼ਾਈਨ ਕਰਦੇ ਹੋ?

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) ``` ## ਕੋਡ ```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) | ## Doubly linked list ਕਿਉਂ ਇੱਕ doubly linked list ਤੁਹਾਨੂੰ **ਵਿਚਕਾਰ ਤੋਂ O(1) ਵਿੱਚ ਇੱਕ ਨੋਡ ਨੂੰ ਵੱਖ ਕਰਨ** ਦਿੰਦਾ ਹੈ (ਤੁਹਾਨੂੰ ਇਸ ਦਾ `prev`/`next` ਹੈ), ਜੋ singly linked list ਜਾਂ array ਦੇ ਨਾਲ O(n) shift ਤੋਂ ਬਿਨਾ ਅਸੰਭਵ ਹੈ। ## ਇਹ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ LRU caches ਡਾਟਾਬੇਸ, ਵੈਬ ਸਰਵਰ, ਅਤੇ CPUs ਦੇ ਸਾਮਣੇ ਬੈਠੇ ਹੋਣ ਆਲੀ ਡੇਟਾ ਨੂੰ ਤੇਜ਼ ਅਤੇ ਮੈਮੋਰੀ ਨੂੰ ਸੀਮਤ ਰੱਖਣ ਲਈ ਬੈਠੇ ਹੁੰਦੇ ਹਨ। ਇਹ ਸਮੱਸਿਆ ਇੱਕ staple senior interview ਹੈ ਕਿਉਂਕਿ ਇਹ ਦੋ ਢਾਂਚਿਆਂ ਨੂੰ ਮਿਲਾਉਣ ਦੀ ਪੜਖ ਕਰਦਾ ਹੈ ਤਾਂਕਿ *ਹਰ ਇਕ ਦੀ ਕਮਜ਼ੋਰੀ ਨੂੰ ਮਢਿਆ ਜਾਵੇ* — ਇੱਕ ਮੁੱਖ system-design ਹੁਨਰ।