LRU Cache Design

दो structures, एक काम

LRU cache को O(1) get, O(1) put, और least-recently-used item का O(1) eviction चाहिए। अकेला hash map तेज़ lookup देता है पर कोई क्रम नहीं; अकेली linked list क्रम देती है पर धीमी lookup। दोनों मिलाने से दोनों मिलते हैं।

Doubly linked list + hash map

Hash map key -> node को O(1) lookup के लिए रखता है। Doubly linked list nodes को उपयोग-क्रम में रखती है: access पर node को आगे (सबसे हाल का) ले जाएँ, और भरने पर पीछे (सबसे पुराना) से हटाएँ।

class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node(0, 0)   # dummy most-recent end
        self.tail = Node(0, 0)   # dummy least-recent end
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, val):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, val)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

Python का शॉर्टकट

Interviews में इसे हाथ से बनाया जाता है, पर असली Python code में collections.OrderedDict यह पहले से करता है — access पर move_to_end() और सबसे पुराना हटाने के लिए popitem(last=False)।

त्वरित जांच

Design की समझ परखें।

त्वरित जाँच: LRU cache को singly linked list के बजाय doubly linked list की ज़रूरत क्यों है?

• यह कम memory इस्तेमाल करती है
• यह किसी node को केवल उसका pointer देकर O(1) में हटाने देती है
• यह keys को वर्णानुक्रम में क्रमबद्ध करती है
• Hash maps को doubly linked lists चाहिए ही होती हैं