Leetcode 146 LRU Cache

Soru

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Örnek 1

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Çözüm

• “146. LRU Cache” sorusu, en az kullanılan öğe (Least Recently Used - LRU) önbellek sistemi tasarlamayı ister. Bu önbellek, belirli bir kapasiteye sahiptir ve bu kapasite aşıldığında, en az kullanılan öğe önbellekten atılır ve yeni öğe eklenir. Sorun, bu önbellek mekanizmasını verimli bir şekilde uygulamayı gerektirir, bu da hem get hem de put işlemlerinin O(1) zaman karmaşıklığında çalışmasını zorunlu kılar.
• Girdi: Belirli bir kapasite ile başlatılacak bir LRU önbelleği.
• Çıktı: get(key) ve put(key, value) işlemleri üzerinden dinamik olarak yönetilen bir önbellek.
• LRU önbelleğini verimli bir şekilde uygulamak için sıklıkla çift yönlü bağlı liste (doubly linked list) ve hash tablosu (dictionary) kullanılır:
• Çift Yönlü Bağlı Liste: Bu liste, öğelerin sırasını korur. En son kullanılan öğeler liste başına yakın, en az kullanılanlar ise liste sonuna yakın yer alır.
• Hash Tablosu: Anahtarlar ve bağlı listedeki düğümlerin referanslarını saklar, bu sayede herhangi bir öğeye O(1) zamanda erişim sağlanır.
• Çalışma Mekanizması:
• İnitializasyon: Dummy baş ve son düğümleri ile çift yönlü bir liste oluşturulur.
• Node Ekleme ve Çıkarma: Öğelerin kolayca eklenebilmesi ve çıkarılabilmesi için yardımcı fonksiyonlar kullanılır.
• Get ve Put İşlemleri: get işlemi, öğeyi erişildiğinde başa taşır. put işlemi, yeni bir öğe eklerken kapasiteyi aştığı takdirde en son öğeyi kaldırır.

Code

class ListNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def removeNode(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev
    
    def addNode(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def moveToHead(self, node):
        self.removeNode(node)
        self.addNode(node)
    
    def popTail(self):
        res = self.tail.prev
        self.removeNode(res)
        return res
    
    def get(self, key: int) -> int:
        node = self.cache.get(key, None)
        if not node:
            return -1
        self.moveToHead(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        node = self.cache.get(key)
        if not node:
            newNode = ListNode(key, value)
            self.cache[key] = newNode
            self.addNode(newNode)
            if len(self.cache) > self.capacity:
                tail = self.popTail()
                del self.cache[tail.key]
        else:
            node.value = value
            self.moveToHead(node)

Complexity

• Time complexity (Zaman Karmaşıklığı): Her işlem O(1) zamanında çalışır çünkü doğrudan hash tablosu erişimi ve sabit zamanlı düğüm ekleme/çıkarma işlemleri kullanılır.
• Space complexity (Alan Karmaşıklığı): O(capacity), çünkü önbellek boyutu kapasite ile sınırlıdır ve bu kapasitede düğüm ve hash girişleri saklanır.