آپ 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 ہے، بالکل وہی ساخت جو اوپر بیان کی گئی ہے۔ | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Doubly linked list کیوں ایک doubly linked list آپ کو **O(1) میں درمیان سے ایک node کو detach کرنے** دیتا ہے (آپ کے پاس اس کا `prev`/`next` ہے)، جو singly linked list یا array کے ساتھ O(n) shift کے بغیر ممکن نہیں ہے۔ ## اہمیت کیوں ہے LRU caches ڈیٹا بیس، ویب سرورز، اور CPUs کے سامنے بیٹھتے ہیں تاکہ گرم ڈیٹا تیز رہے اور میموری محدود رہے۔ یہ مسئلہ ایک سینئر انٹرویو کی بنیاد ہے کیونکہ یہ دونوں ساخت کو یکجا کرنے کی جانچ کرتا ہے تاکہ *ہر ایک کی کمزوری دوسرے سے پوری ہو* — یہ ایک اہم نظام ڈیزائن کی مہارت ہے۔