Cache LRU (Least Recently Used) nglurug item sing ora ditusuk paling suwe nalika kapasitas kepenuhan. Design klasik nggabung hash map (O(1) look up) karo doubly linked list (O(1) nata ulang), menehi O(1) get lan put.
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)
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 dhewe-dhewe hash map plus doubly linked list, persis struktur sing kaandharake ing ndhuwur.
| Operasi | Wektu |
|---|---|
| get | O(1) |
| put | O(1) |
| space | O(capacity) |
Doubly linked list nyamanake sampeyan nglurug node saka tengah ing O(1) (sampeyan nyekel prev/next dheweke), apa sing ora bisa karo singly linked list utawa array tanpa O(n) shift.
Cache LRU duduk ing ngarep database, web server, lan CPU kanggo njaga data panas cepet lan memori terbatas.
Masalah iki minangka tugas standar senior interview amarga nguji nggabung loro struktur supaya masing-masing kalemahan katutup — skill penting ing system design.