Coding interview problems › Design & Tries

🗃️ Design & Tries Medium

LRU Cache

LRU Cache interview question explained: why a hash map plus a doubly linked list gives O(1) get and put, tested Python code, pitfalls and a live visual.

Also searched as: LRU cache interview question · least recently used cache · design an LRU cache with O(1) get and put

🗃️

Try it live Free

LRU Cache (HashMap + Linked List)

Run gets and puts and watch a hit move its node to the front of the list while a full cache evicts from the tail, with the hash map pointing into the list the whole time.

Also useful: Linked Lists: Reverse & Floyd's Cycle, Hash Tables

Open the playground →

The problem

Design a cache with a fixed capacity that supports get(key) (return the value, or -1 if absent) and put(key, value). When the cache is full and a new key arrives, it must throw out the least recently used key. Both operations should run in O(1) time.

Inputcapacity = 2; put(1,1), put(2,2), get(1), put(3,3), get(2)
Outputget(1) -> 1, get(2) -> -1

get(1) made key 1 recent, so put(3,3) evicted key 2.

The key insight

You need two things at once: find any key instantly (a hash map does that) and know the recency order so you can drop the oldest (a list does that). A doubly linked list lets you unlink any node in O(1) once you hold a pointer to it, and the hash map stores exactly that pointer. Every access moves the node to the front; eviction takes the node at the back.

Brute force first: Keeping keys in a plain Python list and calling list.remove on every access works, but each operation becomes O(n).

Step-by-step approach

  1. Keep a hash map from key to list node, and a doubly linked list ordered from most recent (front) to least recent (back).
  2. Use two sentinel nodes, head and tail, so inserting and removing never needs special cases for an empty list.
  3. get: if the key is missing return -1; otherwise unlink its node, re-insert it at the front, and return its value.
  4. put: if the key exists, unlink the old node. Insert a fresh node at the front and record it in the map.
  5. If the map now holds more than capacity keys, unlink tail.prev (the least recently used node) and delete its key from the map.

Python solution

PYTHON 3tested
class Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                      # key -> Node
        self.head, self.tail = Node(), Node()  # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):            # front = most recently used
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev           # least recently used
            self._remove(lru)
            del self.map[lru.key]

Complexity

TimeO(1) per operation
SpaceO(capacity)

Every operation is a dictionary lookup plus a constant number of pointer changes. The node stores its own key so that eviction can delete it from the map without searching.

Common mistakes

Frequently asked questions

What is the time and space complexity of an LRU cache?

With a hash map plus a doubly linked list, get and put are both O(1) time. Space is O(capacity), one map entry and one list node per stored key.

Why a doubly linked list and not a singly linked one?

To unlink a node in O(1) you must reach its previous node. A singly linked list would need an O(n) walk to find it; the prev pointer removes that walk.

Can I use Python's OrderedDict in an interview?

OrderedDict with move_to_end and popitem(last=False) is a valid LRU cache in a few lines, and some interviewers accept it. Many ask you to build the map plus linked list yourself, so be ready to do both.

How is LFU different from LRU?

LRU evicts the key used longest ago; LFU evicts the key used least often, breaking ties by recency. LFU needs extra bookkeeping such as a list of keys per frequency.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Design & Tries LRU Cache (HashMap + Linked List) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.