LRU Cache
On this page
Problem statement
Design a cache with a fixed capacity that supports get(key) and put(key, value), both in O(1) average time.
getreturns the value or −1 if the key is missing.putinserts or updates a key; if that pushes the cache over capacity, it first removes the least recently used key. Bothgetandputcount as a use.
One of the most frequently asked design-style coding questions. It checks whether you can combine two data structures so that each covers the other's weakness. Original problem: LeetCode 146.
Example

LRUCache(2)
put(1, A); put(2, B)
get(1) -> A # order now: 1, 2
put(3, C) # evicts 2 (least recently used)
get(2) -> -1
get(3) -> C
Constraints (assumed)
- 1 ≤ capacity ≤ 3,000; up to 2 × 10⁵ calls.
- Keys and values are integers.
What this question tests
- Recognizing that no single structure gives O(1) lookup and O(1) reordering.
- Implementing a doubly linked list with sentinels without pointer bugs.
- Keeping the map and the list consistent on every operation.
Questions to ask first
- Does
getcount as a use? (Here: yes, it refreshes the key.) - Does updating an existing key count as a use? (Here: yes.)
- Can I use the language's ordered map (Python
OrderedDict, JavaLinkedHashMap)? Many interviewers want it built by hand. - Is it single-threaded? (Here: yes. Concurrency is a common follow-up.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.