Bagaimana anda merancang cache LRU dengan get dan put O(1)?

Question

Accepted Answer

Cache **LRU (Least Recently Used)** mengeluarkan item yang belum diakses selama waktu paling lama ketika mencapai kapasitas. Desain klasik menggabungkan **hash map** (pencarian O(1)) dengan **doubly linked list** (pengurutan ulang O(1)), memberikan **get dan put O(1)**. ## Desain dua struktur ```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` itu sendiri adalah hash map ditambah doubly linked list, persis struktur yang dijelaskan di atas. | Operasi | Waktu | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Mengapa doubly linked list Douubly linked list memungkinkan anda **melepas node dari tengah dalam O(1)** (anda memegang `prev`/`next` nya), yang tidak mungkin dilakukan dengan singly linked list atau array tanpa pergeseran O(n). ## Mengapa hal ini penting Cache LRU duduk di depan database, server web, dan CPU untuk menjaga data panas tetap cepat dan memori terbatas. Masalah ini adalah soal standar wawancara senior karena menguji penggabungan dua struktur sehingga *kelemahan satu ditutup oleh yang lain* — keterampilan desain sistem kunci.