మీరు O(1) get మరియు putతో LRU cacheని ఎలా డిజైన్ చేస్తారు?

Question

Accepted Answer

**LRU (Least Recently Used) cache** సామర్థ్యానికి చేరుకున్నప్పుడు, ఎక్కువ సమయం యాక్సెస్ చేయని అంశాన్ని బహిష్కరిస్తుంది. క్లాసిక్ డిజైన్ **hash map** (O(1) lookup)ని **doubly linked list** (O(1) మరలా అమర్చడం)తో కలుపుతుంది, ఇది **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 ఎందుకు Douubly linked list మీరు **O(1) నుండి మధ్య నుండి నోడ్‌ను డిటాచ్ చేయడానికి** అనుమతిస్తుంది (మీరు దాని `prev`/`next`ను కలిగి ఉన్నారు), ఇది singly linked list లేదా O(n) సాపేక్ష లేకుండా array లతో అసాధ్యం. ## ఇది ఎందుకు ముఖ్యమైనది LRU caches డేటాబేస్‌ల, వెబ్ సర్వర్‌ల మరియు CPUల ముందు ఉండి వేడి డేటాను వేగవంతంగా మరియు స్మృతిని సীమితంగా ఉంచుతాయి. ఈ సమస్య సిన్యర్ ఇంటర్‌వ్యూ కోసం ఒక ప్రధానమైన సమస్య, ఎందుకంటే ఇది రెండు నిర్మాణాలను కలపడం పరీక్షిస్తుంది, తద్వారా *ఒక ఇతర యొక్క బలహీనతను కవర్ చేస్తుంది* — ఒక కీ సిస్టమ్-డిజైన్ నైపుణ్యం.