Project: Building an LRU Cache

Build the mental model

A cache needs two things simultaneously: instant lookup by key, and a way to know which entry was used longest ago so it can be evicted when full. A hash map alone gives O(1) lookup but has no notion of order — you'd have to scan every entry to find the least-recently-used one, making eviction O(n). A plain linked list alone gives O(1) reordering (move a node to the front on access) but O(n) lookup, since finding a node by key means walking the list. The LRU cache design beats both naive approaches by combining them: a hash map stores key to node references for instant lookup, and a doubly linked list maintains recency order, with the node's list pointers letting it be unlinked and relinked in O(1) without shifting anything. Every `get` moves the accessed node to the front in O(1); every `put` either updates in place or evicts the tail (least recently used) in O(1) once capacity is exceeded. Python's `OrderedDict` implements exactly this hybrid internally, which is why `move_to_end()` and `popitem(last=False)` are both O(1).

Connect it to a real scenario

This is literally what would sit in front of the Tutorial Platform's lesson-loading logic: hot lessons that many learners request repeatedly (a popular Python intro, a trending JS tutorial) get cached in memory with a fixed capacity, so a repeated request skips re-reading the file or re-hitting the database entirely. When a new lesson is requested and the cache is full, the LRU policy evicts whichever cached lesson hasn't been touched in the longest time — a reasonable bet that it's least likely to be requested again soon, versus evicting arbitrarily or never evicting (which would leak memory as the site's lesson catalog grows past 55 tutorials).

• A hash map alone can't track recency order, so eviction becomes an O(n) scan
• A linked list alone gives O(1) reordering but O(n) key lookup
• Combining a hash map with a doubly linked list makes both get and put O(1)

Try the working example

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # OrderedDict internally pairs a hash map with a doubly linked list:
        # move_to_end() and popitem(last=False) are both O(1) because of it.
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        # Accessing a key counts as "recently used" -> move it to the front
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            # Refresh existing entry's position before updating
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Evict the least-recently-used entry (front of the OrderedDict)
            self.cache.popitem(last=False)

if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put("python-basics", "<lesson html>")
    cache.put("js-intro", "<lesson html>")
    print(cache.get("python-basics"))  # hit -> becomes most recently used
    cache.put("rust-ownership", "<lesson html>")  # evicts "js-intro"
    print(cache.get("js-intro"))  # -1, was evicted
    print(list(cache.cache.keys()))  # remaining cached lesson slugs

Prints `<lesson html>`, then `-1`, then the remaining cache keys `['python-basics', 'rust-ownership']`, showing that `js-intro` was evicted.

Python Docs — functools.lru_cache — Data Structures & Algorithms