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
- get(key): return the value, or nothing if missing; it counts as a use.
- put(key, value): insert or update; if the cache is full, remove the least recently used item.
Non-functional requirements
- Both operations in O(1) time.
- Optionally thread-safe.
From version 1 to the final design
- Naive: a list kept in order of use. get is O(n), because you must find and move the item.
- Better: a dictionary for lookups, but keeping the order still costs O(n).
- Final: a dictionary plus a doubly linked list, so both operations are O(1).
- Extensions: a TTL per entry, thread safety, or LFU instead of LRU.
The design, step by step
- A hash map finds a key's node in O(1).
- A doubly linked list keeps items in order of use: most recent at the front, least recent at the back.
- 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
- Dummy head and tail nodes remove the edge cases.
- Thread safety: one lock around get and put (or several locks for parts of the cache).
- In Python, OrderedDict with move_to_end does the same in a few lines; know both versions.
Common mistakes
- A singly linked list, which can't remove a node in O(1).
- Forgetting to update the order on get.
- Forgetting to delete the evicted key from the dictionary.
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.