LRU CacheStep 3 of 5

Eviction at Capacity

12345

Step 3 — Eviction at Capacity

A cache is bounded. When inserting a new key would exceed capacity, evict the least-recently-used entry — the node just before _tail — from both the list and the map.

Add eviction to put: after inserting a new key, if len(self._map) > self.capacity, drop the LRU node. Updating an existing key must not trigger eviction (the size didn't grow), and a key you just accessed with get should survive while colder keys are evicted.

Hints
Starter code
class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self._map = {}
        self._head = Node()
        self._tail = Node()
        self._head.next = self._tail
        self._tail.prev = self._head

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

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

    def order(self):
        out = []
        n = self._head.next
        while n is not self._tail:
            out.append(n.key)
            n = n.next
        return out

    def get(self, key):
        if key not in self._map:
            return None
        node = self._map[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key, value):
        if key in self._map:
            node = self._map[key]
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        node = Node(key, value)
        self._map[key] = node
        self._add_front(node)
        # TODO: if len(self._map) > self.capacity, evict the LRU node:
        #   lru = self._tail.prev
        #   self._remove(lru)
        #   del self._map[lru.key]
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step