Πώς σχεδιάζεις μια LRU cache με O(1) get και put;

Question

Accepted Answer

Μια **LRU (Least Recently Used) cache** αφαιρεί το στοιχείο που δεν έχει προσπελαστεί για το μεγαλύτερο χρονικό διάστημα όταν φτάσει τη χωρητικότητα. Το κλασικό σχέδιο συνδυάζει έναν **hash map** (O(1) lookup) με μια **doubly linked list** (O(1) αναταξινόμηση), δίνοντας **O(1) get και put**. ## Το σχέδιο δύο δομών ```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) ``` ## Κώδικας ```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` είναι από μόνο του ένας hash map συν μια doubly linked list, ακριβώς η δομή που περιγράφεται παραπάνω. | Λειτουργία | Χρόνος | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Γιατί η doubly linked list Μια doubly linked list σου επιτρέπει να **αποσυνδέσεις έναν κόμβο από το κέντρο σε O(1)** (κρατάς το `prev`/`next` του), κάτι που είναι αδύνατο με μια singly linked list ή πίνακα χωρίς μια μετατόπιση O(n). ## Γιατί είναι σημαντικό Οι LRU caches βρίσκονται μπροστά από βάσεις δεδομένων, web servers και CPUs για να κρατούν τα hot data γρήγορα και τη μνήμη περιορισμένη. Αυτό το πρόβλημα είναι ένα κλασικό ερώτημα senior interview επειδή δοκιμάζει τη σύνδεση δύο δομών ώστε *η καθεμία να καλύπτει την αδυναμία της άλλης* - μια βασική δεξιότητα σχεδιασμού συστημάτων.