Sign in
Skip to solution
hardDSA

How do you design an LRU cache?

1.2k views
01

Understand the problem

Explain LRU cache.

lrudesign
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Combine a hash map (key → node) with a doubly linked list ordering nodes by recency. Get/put move the node to the front; when full, evict the tail. Both operations are O(1).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

LRU cache
Run Playground
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()   # ordered by recency

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark most recent
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # evict least recent


# --- demo --- (capacity 2)
lru = LRUCache(2)
lru.put(1, 1); lru.put(2, 2)
print(lru.get(1))     # 1
lru.put(3, 3)         # full -> evicts key 2
print(lru.get(2))     # -1
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 102 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track