Design an LRU cache

Design a fixed-size cache that removes the least recently used item when full, with get and put in O(1).

Why interviewers ask it

It tests data-structure design under a strict time limit (O(1) operations), and it's asked both as a coding question and as a design question.

Functional requirements

Non-functional requirements

From version 1 to the final design

  1. Naive: a list kept in order of use. get is O(n), because you must find and move the item.
  2. Better: a dictionary for lookups, but keeping the order still costs O(n).
  3. Final: a dictionary plus a doubly linked list, so both operations are O(1).
  4. Extensions: a TTL per entry, thread safety, or LFU instead of LRU.

The design, step by step

  1. A hash map finds a key's node in O(1).
  2. A doubly linked list keeps items in order of use: most recent at the front, least recent at the back.
  3. get: move the node to the front. put: update and move to the front, or insert at the front and remove the back node if over capacity.

Deep dives

Common mistakes

Not true: get: reads the value and leaves the key's place in the eviction order as it was.
In fact: A read is a use: get must move the key to the most recent end. Otherwise a key that is read all the time would be evicted as if nobody used it.

In the interview

A hash map from key to node gives O(1) lookup, and a doubly linked list keeps items in order of use. get moves the node to the front; put inserts at the front and removes the back node when over capacity. Dummy head and tail nodes keep the code simple.

Part of Unit 7: Low-level design questions in the free System Design course.