hardDSA

How do you design an LRU cache?

Q: How do you design an LRU cache?

**Intuition.** An LRU (Least Recently Used) cache evicts the entry untouched for the longest when it's full. To do both get and put in **O(1)**, combine two structures: a **hash map** for instant lookup, and a **doubly linked list** that orders entries by recency (most-recent at the front, least-recent at the back). map → node; list orders by recency most recent evict here <rect x="30" y="56" wid

1.2k views

Understand the problem

Explain LRU cache.

lrudesign

Attempt it yourself

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

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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

Join the discussion

Discussion (0)

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

What is dynamic programming?

How do you merge k sorted lists?