Hoe ontwerp je een LRU cache met O(1) get en put?

Question

Accepted Answer

Een **LRU (Least Recently Used) cache** verwijdert het item dat het langst niet is geopend wanneer de capaciteit wordt bereikt. Het klassieke ontwerp combineert een **hash map** (O(1) opzoeken) met een **doubly linked list** (O(1) herordenen), wat **O(1) get en put** oplevert. ## De ontwerp met twee structuren ```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` is zelf een hash map plus een doubly linked list, exact de structuur die hierboven wordt beschreven. | Operatie | Tijd | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Waarom de doubly linked list Een doubly linked list laat je een **node uit het midden losmaken in O(1)** (je houdt de `prev`/`next`), wat onmogelijk is met een singly linked list of array zonder een O(n) verschuiving. ## Waarom het belangrijk is LRU caches staan voor databases, webservers en CPU's om hot data snel en geheugen begrensd te houden. Dit probleem is een standaard senior interview omdat het testen combineert twee structuren zodat *elkaars zwakte wordt afgedekt* — een sleutelvaardigheden voor systeemontwerp.