Implement an LRU Cache with Constant-Time Operations in Freebuff Desktop

An LRU cache is a common interview and systems problem because the obvious versions are slow. This example asks Freebuff Desktop for one with constant-time get and put, has it write tests, and then checks the speed independently.

Quick answers

Can Freebuff Desktop implement a non-trivial data structure? Yes. It produced a hash map plus doubly linked list, the standard approach for constant-time LRU caches.

Does it write tests for it? Yes. It wrote 21 tests covering eviction order, recency updates and invalid input, and all passed.

Is it really constant time? The structure is right, and our timing check agreed: 100 times more inserts took roughly 100 times longer, which is linear in total and constant per operation.

The prompt

Open an empty folder in Freebuff Desktop, start a new chat and send:

Implement an LRU cache class in lru.py with O(1) get and put and a capacity limit. Write unit tests with unittest in test_lru.py and run them.

The result

lru.py keeps a dictionary from key to node and a doubly linked list ordered from least to most recently used, with sentinel head and tail nodes so insertion and removal never need special cases:

class LRUCache:
    """Fixed-capacity cache that evicts the least recently used entry.

    A dict maps keys to list nodes for O(1) lookup, and a doubly linked list
    keeps entries ordered from least recently used (head) to most recently
    used (tail). Every operation is O(1).
    """

    def put(self, key: Any, value: Any) -> None:
        """Insert or update ``key``, evicting the LRU entry when full."""
        node = self._nodes.get(key)
        if node is not None:
            node.value = value
            self._move_to_tail(node)
            return

        if len(self._nodes) >= self._capacity:
            lru = self._head.next
            if lru is not None and lru is not self._tail:
                self._unlink(lru)
                del self._nodes[lru.key]

        node = _Node(key, value)
        self._nodes[key] = node
        self._append(node)

class LRUCache:
    """Fixed-capacity cache that evicts the least recently used entry.

    A dict maps keys to list nodes for O(1) lookup, and a doubly linked list
    keeps entries ordered from least recently used (head) to most recently
    used (tail). Every operation is O(1).
    """

    def put(self, key: Any, value: Any) -> None:
        """Insert or update ``key``, evicting the LRU entry when full."""
        node = self._nodes.get(key)
        if node is not None:
            node.value = value
            self._move_to_tail(node)
            return

        if len(self._nodes) >= self._capacity:
            lru = self._head.next
            if lru is not None and lru is not self._tail:
                self._unlink(lru)
                del self._nodes[lru.key]

        node = _Node(key, value)
        self._nodes[key] = node
        self._append(node)

Besides get and put, Freebuff kept a few small extras: peek (read without changing recency), delete, clear and keys(), which the tests use to check the exact eviction order.

Verify the result

python3 -m unittest

python3 -m unittest

Ran 21 tests in 0.001s

OK

Ran 21 tests in 0.001s

OK

Then check the behavior and the speed without trusting the generated tests:

python3 - <<'PY'
import time
from lru import LRUCache
c = LRUCache(2); c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3)
print("evicts b:", c.get("b") is None, "keeps a,c:", c.get("a"), c.get("c"))
for n in (10_000, 1_000_000):
    c = LRUCache(n)
    t = time.perf_counter()
    for i in range(n):
        c.put(i, i)
    print(n, "puts in", round(time.perf_counter() - t, 3), "s")
PY

python3 - <<'PY'
import time
from lru import LRUCache
c = LRUCache(2); c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3)
print("evicts b:", c.get("b") is None, "keeps a,c:", c.get("a"), c.get("c"))
for n in (10_000, 1_000_000):
    c = LRUCache(n)
    t = time.perf_counter()
    for i in range(n):
        c.put(i, i)
    print(n, "puts in", round(time.perf_counter() - t, 3), "s")
PY

evicts b: True keeps a,c: 1 3
10000 puts in 0.002 s
1000000 puts in 0.238 s

evicts b: True keeps a,c: 1 3
10000 puts in 0.002 s
1000000 puts in 0.238 s

Reading a made b the least recently used entry, so adding c evicted b. Your timings will differ by machine. The ratio is what matters.

Troubleshooting

Adding your own cases. Ask Freebuff for more tests, for example capacity one with repeated updates.

Thread safety. For concurrent use, ask Freebuff to add a lock and a concurrent test.

You need expiry. Ask for a time-to-live option, and ask for tests that control the clock instead of sleeping.