MediumHash TableLinked ListDesignUpdated Sep 2026

146. LRU Cache

Asked at Google, Meta, Amazon, Microsoft and 9 more

Difficulty

Medium

Time

O(1) per get and per put

Space

O(capacity)

Pattern

Hash Table

Companies

13

Problem

Design a data structure called an LRU cache (Least Recently Used cache). It stores at most capacity key-value pairs. When it is full and you add a new pair, it must throw away the pair that was used least recently.

Implement a class LRUCache with two methods. get(key) returns the stored value for that key, or -1 if the key is not present. put(key, value) inserts a new pair, or overwrites the value if the key already exists.

Using a key counts as using it. Both get(key) and put(key, value) must mark that key as the most recently used one. When the cache is over capacity after a put, remove the key that has gone the longest without being touched.

Both methods must run in O(1) average time. That rules out scanning a list to find the oldest key.

A full cache must drop the oldest key

most recent → least recent1=12=2nullnewestoldestAfter put(1,1) and put(2,2) the cache is full; key 2is the least recently used.after put(3,3)3=31=1nullnewestoldestKey 2 is evicted, the new pair 3=3 goes to the front,and key 1 becomes the oldest.
With capacity 2, adding key 3 pushes out key 2 because key 2 was used least recently.

Constraints

  • ●1 <= capacity <= 3000
  • ●0 <= key <= 10^4
  • ●0 <= value <= 10^5
  • ●At most 2 * 10^5 calls will be made to get and put

Examples

Example 1
Input["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output[null, null, null, 1, null, -1, null, -1, 3, 4]
WhyCapacity is 2. After put(1,1) and put(2,2) the cache holds {1, 2}. get(1) returns 1 and makes key 1 the newest, so key 2 is now the oldest. put(3,3) is full, so key 2 is evicted and the cache becomes {1, 3}. get(2) returns -1 because key 2 is gone. put(4,4) evicts key 1 (the oldest now), leaving {3,
Example 2
Input["LRUCache", "put", "get"] [[1], [2, 2], [2]]
Output[null, null, 2]
WhyCapacity is 1. put(2,2) stores the pair, and get(2) finds it and returns 2.
Example 3
Input["LRUCache", "put", "put", "get"] [[1], [2, 2], [3, 3], [2]]
Output[null, null, null, -1]
WhyCapacity is 1. put(2,2) fills the cache. put(3,3) needs room, so the only entry, key 2, is evicted. get(2) then returns -1.

Asked At

13 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
UberMediumView all Uber questions →
AtlassianMediumView all Atlassian questions →
SalesforceMediumView all Salesforce questions →
BloombergMediumView all Bloomberg questions →
Goldman SachsMediumView all Goldman Sachs questions →
TikTokMediumView all TikTok questions →
NVIDIAMediumView all NVIDIA questions →

How to Think About It

1

Two data structures needed: a hash map for O(1) key lookup, and a doubly linked list for O(1) insertion/deletion and maintaining access order.

2

The hash map stores key → node. The doubly linked list stores key-value pairs in access order: most recently used at the front, least recently used at the back.

3

On get or put: move the accessed node to the front of the list. This marks it as recently used.

4

On eviction (put when full): remove the node at the back of the list (least recently used). Also remove it from the hash map.

5

Dummy head and tail nodes simplify edge cases — you never need to check for null pointers during insertion/deletion.

Optimal Approach

Data structures:

  • Hash map: key → node in doubly linked list
  • Doubly linked list: key-value pairs in access order (most recent at front)

get(key):

  1. If key not in map, return -1
  2. Move the node to front (mark as recently used)
  3. Return the value

put(key, value):

  1. If key exists: update value, move to front
  2. If key doesn't exist:
    a. Create new node, add to front, add to map
    b. If over capacity: remove back node from list AND map

Both operations are O(1) because:

  • Hash map lookup: O(1)
  • Doubly linked list insertion/deletion (given the node): O(1)

Hash map plus doubly linked list

map: key → nodekeynode1node(1,1)2node(2,2)Each key points straight at its node, so no searchingis needed.head → ... → tail2=21=1nullfront = MRUback = LRUget(1) unlinks node 1 and re-inserts it at the front,so the order becomes 1=1, 2=2.get: look up in map, unlink node, push to frput existing: update value, push to frontput new: push to front; if size > capacity, Every step touches only a constant number of pointers,which keeps both operations O(1).front = most recently usedback = least recently usedevict = remove back node + its map entry
The map finds a node in O(1); the list keeps the usage order and lets us unlink any node in O(1).
ComplexityTime O(1) per get and per putSpace O(capacity)The hash map gives O(1) key lookup, and the doubly linked list gives O(1) move-to-front and O(1) removal of the oldest node; the map and list together hold at most capacity entries.

What Trips People Up in Real Interviews

1

Not understanding the O(1) requirement for both get and put. A hash map alone gives O(1) get but O(n) eviction. A linked list alone gives O(1) eviction but O(n) lookup. You need both.

2

Confusing "least recently used" with "least frequently used." LRU evicts the item that was accessed longest ago, not the one accessed least often.

3

Forgetting to update access order on get. Every time you access an item (get or put), it becomes the most recently used. Move it to the tail of the linked list.

4

Not handling the case where the cache is full. When adding a new item and the cache is at capacity, evict the head of the linked list (least recently used) before adding.

5

Not storing the key in the linked list node. When evicting the LRU node, you need the key to remove it from the hash map. If the node only stores the value, you can't efficiently remove it.

Solution Code

O(1) per get and per put time
class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

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

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

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

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

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the LRU Cache problem?

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put operations in `O(1)` time. This is a classic system design and coding hybrid question.

How do you solve LRU Cache?

The optimal approach runs in O(1) per get and per put time and O(capacity) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask LRU Cache?

LRU Cache is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Salesforce, Bloomberg, Goldman Sachs, TikTok, NVIDIA. It is a medium difficulty problem.

What are common mistakes on LRU Cache?
  • Not understanding the `O(1)` requirement for both get and put. A `hash map` alone gives `O(1)` get but `O(n)` eviction. A linked list alone gives `O(1)` eviction but `O(n)` lookup. You need both.
  • Confusing "least recently used" with "least frequently used." LRU evicts the item that was accessed longest ago, not the one accessed least often.
  • Forgetting to update access order on get. Every time you access an item (get or put), it becomes the most recently used. Move it to the tail of the linked list.
  • Not handling the case where the cache is full. When adding a new item and the cache is at capacity, evict the head of the linked list (least recently used) before adding.
  • Not storing the key in the linked list node. When evicting the LRU node, you need the key to remove it from the `hash map`. If the node only stores the value, you can't efficiently remove it.