Kako dizajnirate LRU cache s O(1) get i put?

Question

Accepted Answer

**LRU (Least Recently Used) cache** uklanja stavku na koju se nije pristupalo najduže kada dostigne kapacitet. Klasični dizajn kombinira **hash mapu** (O(1) lookup) s **dvostruko povezanom listom** (O(1) preuređivanje), dajući **O(1) get i put**. ## The two-structure design ```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` je sam po sebi hash mapa plus dvostruko povezana lista, točno struktura opisana gore. | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Why the doubly linked list Dvostruko povezana lista omogućava vam **odvajanje čvora iz sredine u O(1)** (držite njegov `prev`/`next`), što je nemoguće sa jednostruko povezanom listom ili poljem bez O(n) pomaka. ## Zašto je to važno LRU cache-evi sjede ispred baza podataka, web poslužitelja i CPU-a kako bi održali vruće podatke brze i memoriju ograničenu. Ovaj problem je standardan u intervjuima za starije pozicije jer testira kombiniranje dvije strukture tako da *slabost jedne pokriva druga* — ključna vještina u dizajnu sustava.

The two-structure design

Code

Why the doubly linked list

Zašto je to važno

question.related