pythonadvanced15 minutes

Fix the Bug in the Optimized LRU Cache Implementation

Identify and fix the subtle bug in the provided Least Recently Used (LRU) cache implementation which causes it to fail under certain eviction conditions. The solution must maintain O(1) time complexity for get and put operations while correctly managing the cache size and order.

Challenge prompt

You are given a Python class implementing an LRU cache using a dictionary and a doubly linked list. The goal is to store key-value pairs with constant time retrieval and eviction based on the least recently used policy. However, the current implementation has a bug that results in incorrect eviction behavior once the cache reaches its capacity. Your task is to identify and fix the bug so that the cache evicts the correct item when full and maintains the correct internal state.

Guidance

• Pay close attention to the eviction logic when the cache size exceeds capacity.
• Examine how the doubly linked list nodes are updated during get and put operations.
• Verify that all pointers (prev and next) are correctly set during insertions and removals.

Hints

• Check if the tail node is always correctly identified before removal.
• Look for any off-by-one errors or incorrect pointer assignments in the eviction process.
• Consider if the cache size is updated appropriately after node removal.

Starter code

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = dict()  # key -> node
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

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

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

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

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            node_to_remove = self.tail.prev
            self._remove(node_to_remove)
            # Bug here: missing deletion from cache dictionary

Expected output

After fixing, the code should pass these operations: lru = LRUCache(2) lru.put(1, 1) # cache is {1=1} lru.put(2, 2) # cache is {1=1, 2=2} lru.get(1) # returns 1 lru.put(3, 3) # evicts key 2, cache is {1=1, 3=3} lru.get(2) # returns -1 (not found) lru.put(4, 4) # evicts key 1, cache is {4=4, 3=3} lru.get(1) # returns -1 (not found) lru.get(3) # returns 3 lru.get(4) # returns 4

Core concepts

data structureslinked listhash mapcache evictiondebugging

Challenge a Friend

Send this duel to someone else and see if they can solve it.