LRU Cache

Asked byAmazonFacebookMicrosoftAppleBloombergOracle

Problem

Design a Least Recently Used (LRU) cache with a fixed capacity that supports get and put in O(1) average time. When the cache exceeds its capacity, evict the least recently used entry.

Examples

Example 1

Input:capacity = 2; put(1,1); put(2,2); get(1)

Output:1

Example 2

Input:put(3,3) (evicts key 2); get(2)

Output:-1

Key 2 was evicted for being least recently used.

Constraints

1 <= capacity <= 3000
At most 2 * 10^5 calls total.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Linked List pattern

A chain of nodes, each pointing to the next. No random access like an array, but insertion and deletion at a known position is O(1), and many classic problems come down to careful pointer rewiring.

Look for this pattern when

The problem explicitly gives you a linked list (reverse it, merge lists, detect a cycle, reorder it).
You need O(1) insertion/deletion without shifting elements, unlike an array.

Read the full Linked List guide →

Video walkthroughs

Original problem on LeetCode ↗