আপনি কীভাবে O(1) get এবং put সহ একটি LRU ক্যাশ ডিজাইন করেন?

Question

Accepted Answer

একটি **LRU (Least Recently Used) ক্যাশ** এমন আইটেম বের করে দেয় যা সবচেয়ে দীর্ঘ সময় ধরে অ্যাক্সেস করা হয়নি যখন এটি ক্ষমতায় পৌঁছায়। ক্লাসিক ডিজাইন একটি **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, যা উপরে বর্ণিত কাঠামোর ঠিক একই রকম। | অপারেশন | সময় | |---|---| | 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 ক্যাশগুলি ডাটাবেস, ওয়েব সার্ভার এবং CPUs-এর সামনে বসে গরম ডেটা দ্রুত রাখতে এবং মেমরি সীমাবদ্ধ রাখতে। এই সমস্যা একটি সিনিয়র ইন্টারভিউর একটি বিশেষত্ব কারণ এটি দুটি কাঠামো একত্রিত করা পরীক্ষা করে যাতে *প্রতিটি অন্যের দুর্বলতা কভার করা হয়* - একটি মূল সিস্টেম-ডিজাইন দক্ষতা।