Kif tiddisinja cache LRU b'get u put O(1)?

Question

IT Interview Practice · Accepted Answer

Cache **LRU (Least Recently Used)** iotja l-element li ma kienx aċċessat għal aktar żmien meta tilħaq l-kapaċità. Id-disinn klassiku jgħaqqad **hash map** (lookup O(1)) ma **doubly linked list** (O(1) reordering), u jagħti **O(1) get u put**. ## Disinn ta' żewġ strutturi ```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` hu innifsu hash map flimkien ma doubly linked list, eżattament l-istruttura deskritta hawn fuq. | Operazzjoni | Ħin | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Għaliex doubly linked list Douubly linked list ippermettik **tneħħi node miċ-ċentru f'O(1)** (għandek il-`prev`/`next` tiegħu), li huwa impossibbli ma singly linked list jew array mingħajr O(n) shift. ## Għaliex huwa importanti Cache LRU jiffunzjonaw quddiem databases, web servers, u CPU biex iżommu data sħun veloċi u memorja limitata. Hi din il-problema pyesa standard fl-intervisti senior għaliex tittesta l-għaqda ta' żewġ strutturi sabiex *ir-restrizzjoni ta' waħda tipprovditu minn oħra* — skill essenzjali tad-disinn tas-sistema.

Disinn ta' żewġ strutturi

Code

Għaliex doubly linked list

Għaliex huwa importanti

Mistoqsijiet relatati