Si e projekton një LRU cache me O(1) get dhe put?

Question

Accepted Answer

Një **LRU (Least Recently Used) cache** heq elementin që nuk është aksesuar për kohën më të gjatë kur arrin kapacitetin. Dizajni klasik kombinon një **hash map** (O(1) lookup) me një **liste të dyfishtë të lidhur** (O(1) rirendajen), duke dhënë **O(1) get dhe put**. ## Dizajni me dy struktura ```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) ``` ## Kodi ```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` është në vetvete një hash map plus një liste e dyfishtë e lidhur, saktësisht struktura e përshkruar më sipër. | Operacioni | Koha | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Pse lista e dyfishtë e lidhur Një liste e dyfishtë e lidhur të lejon të **hiqni një nod nga mesi në O(1)** (e mbani `prev`/`next`), e cila është e pamundur me një liste të vetëm të lidhur ose array pa një zhvendosje O(n). ## Pse është e rëndësishme LRU caches zënë në punët e bazave të të dhënave, serverave web dhe procesorëve për të mbajtur të dhënat e nxehtë të shpejta dhe memorjen e kufizuar. Ky problem është një problem bazë për intervistën e seniorit sepse teston kombinimin e dy strukturave në mënyrë që *secila tjetra ta mbulojë dobësinë* — një aftësi kyçe e dizajnimit të sistemit.