LRU CacheStep 2 of 5

get and put

12345

Step 2 — get and put

Now wire the hash map to the list. Every access makes a key the most-recently-used, which means moving its node to the front.

  • get(key) — return the value, or None if absent; on a hit, move the node to the front
  • put(key, value) — if the key exists, update its value and move it to the front; otherwise create a node, add it to the map and the front of the list

Don't worry about capacity yet — that's the next step. Reuse _remove and _add_front.

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):
        """Return the value (moving the key to most-recent), or None if absent."""
        # TODO:
        #   if key not in self._map: return None
        #   node = self._map[key]; move it to the front; return node.value
        pass

    def put(self, key, value):
        """Insert or update key=value and mark it most-recent."""
        # TODO:
        #   if key in self._map: update value, move node to front, return
        #   else: make a Node, store in self._map, add to front
        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