LRU Cache

Build a fixed-size cache that evicts the least recently used key, with constant-time reads and writes. The standard test of combining a hash map with a linked list. Solve it below in Python or JavaScript, then read the walkthrough.

MediumHash Table Linked List Design Doubly-Linked List Asked at 196 companies incl. Google, Amazon, Meta

Problem

Design a class LRUCache that stores up to capacity key-value pairs. When it's full and a new key arrives, it throws out the key that was used least recently.

Implement:

LRUCache(capacity) creates an empty cache with a positive capacity.
get(key) returns the value stored for key, or -1 if it isn't there. A successful read counts as using the key.
put(key, value) inserts or overwrites key. Writing counts as using the key. If this pushes the cache past capacity, remove the least recently used key first.

Both operations must run in O(1) average time.

In the tests, each case is a list of operations and their arguments. The first operation constructs the cache, and the expected output lists what each call returns (null for the constructor and for put).

Example 1

Input: ["LRUCache", "put", "put", "get", "put", "get", "get"] [[2], [1, 10], [2, 20], [1], [3, 30], [2], [3]]
Output: [null, null, null, 10, null, -1, 30]

Reading key 1 makes key 2 the least recently used, so putting key 3 into the full cache evicts key 2.

Example 2

Input: ["LRUCache", "put", "put", "get"] [[1], [5, 1], [5, 2], [5]]
Output: [null, null, null, 2]

Writing an existing key overwrites it without evicting anything.

Constraints

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2 × 10⁵ calls to get and put.

Practice

Runs 8 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked LRU Cache in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve LRU Cache

Pattern: Hash map + doubly linked list

You need two things to be fast at once: finding a key, and reordering keys by recency. A hash map finds keys in O(1) but has no notion of order. A linked list can move a node to the front or drop the tail in O(1), but finding a node in it is O(n).

Combine them: keep the entries in a doubly linked list ordered from most to least recently used, and have the hash map point from each key straight to its list node. Every get or put unlinks the node and re-links it at the front. Eviction pops the node at the back and deletes its key from the map.

Approach 1: Array or list with timestamps

Store entries with a "last used" counter and scan for the smallest counter when you need to evict. Simple, but eviction (or reordering a list) costs O(n), which fails the O(1) requirement.

Time O(n) per operation · Space O(capacity)

Approach 2: Ordered map from the standard library

Python's OrderedDict (with move_to_end and popitem(last=False)) and JavaScript's Map (which iterates in insertion order, so delete-and-reinsert moves a key to the end) both give O(1) LRU behavior. Interviewers often accept this, but many will then ask you to build the underlying structure yourself.

Time O(1) · Space O(capacity)

Approach 3: Hash map + doubly linked list

Use sentinel head and tail nodes so you never special-case an empty list.

get(key): look up the node; if missing return -1, otherwise move it to the front and return its value.
put(key, value): if the key exists, update the value and move it to the front. Otherwise create a node, add it to the front and the map, and if the map is now over capacity, remove the node just before tail and delete its key.

Each node stores its key so eviction knows which map entry to delete.

Time O(1) · Space O(capacity)

Approach	Time	Space
Array or list with timestamps	O(n) per operation	O(capacity)
Ordered map from the standard library	O(1)	O(capacity)
Hash map + doubly linked list	O(1)	O(capacity)

Solution code

Try the practice editor first. Both solutions pass every test above.

LRU Cache solution in Python

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}  # key -> Node
        self.head = Node()  # most recent side
        self.tail = Node()  # least recent side
        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_to_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        node = Node(key, value)
        self.nodes[key] = node
        self._add_to_front(node)
        if len(self.nodes) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.nodes[lru.key]

LRU Cache solution in JavaScript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.nodes = new Map(); // key -> node
    this.head = { prev: null, next: null }; // most recent side
    this.tail = { prev: this.head, next: null }; // least recent side
    this.head.next = this.tail;
  }

  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  addToFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.nodes.get(key);
    if (!node) return -1;
    this.remove(node);
    this.addToFront(node);
    return node.value;
  }

  put(key, value) {
    const existing = this.nodes.get(key);
    if (existing) {
      existing.value = value;
      this.remove(existing);
      this.addToFront(existing);
      return;
    }
    const node = { key, value, prev: null, next: null };
    this.nodes.set(key, node);
    this.addToFront(node);
    if (this.nodes.size > this.capacity) {
      const lru = this.tail.prev;
      this.remove(lru);
      this.nodes.delete(lru.key);
    }
  }
}

Common mistakes

Forgetting that a successful get also updates recency.
Evicting before checking whether put is overwriting an existing key, which throws out an entry for no reason.
Not storing the key on the list node, so eviction can't find the map entry to delete.
Using a singly linked list, which makes unlinking a node O(n) because you need its predecessor.

What interviewers look for

Say why each structure is there before writing code: "the map gives me O(1) lookup, the list gives me O(1) reordering, and I need both." That sentence is most of what the interviewer is checking for.

Write the two helpers, remove(node) and add_to_front(node), first and test them in your head. Once they're right, get and put are a few lines each. If you start with OrderedDict or Map, say so up front and offer to implement the list version.

Follow-up questions

How would you make it thread-safe?

Wrap get and put in a single lock, since both mutate the list. For high concurrency, shard the cache by key hash so each shard has its own lock and list.

How does this differ from an LFU cache?

LFU evicts the key used the fewest times, breaking ties by recency. It needs a map from frequency to a list of keys plus a tracked minimum frequency, so every operation still stays O(1).

What if entries should also expire after a time-to-live?

Store an expiry timestamp on each node and treat expired entries as missing on read. To reclaim memory proactively, keep a min-heap of expiry times or sweep lazily from the tail.

Companies that ask LRU Cache

LRU Cache is tagged by 196 companies in our interview dataset. The score shows how often it comes up at each company.

and 172 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

LRU Cache

MediumHash Table Linked List Design Doubly-Linked List Asked at 196 companies incl. Google, Amazon, Meta

Problem

Design a class LRUCache that stores up to capacity key-value pairs. When it's full and a new key arrives, it throws out the key that was used least recently.

Implement:

LRUCache(capacity) creates an empty cache with a positive capacity.
get(key) returns the value stored for key, or -1 if it isn't there. A successful read counts as using the key.
put(key, value) inserts or overwrites key. Writing counts as using the key. If this pushes the cache past capacity, remove the least recently used key first.

Both operations must run in O(1) average time.

Example 1

Input: ["LRUCache", "put", "put", "get", "put", "get", "get"] [[2], [1, 10], [2, 20], [1], [3, 30], [2], [3]]
Output: [null, null, null, 10, null, -1, 30]

Reading key 1 makes key 2 the least recently used, so putting key 3 into the full cache evicts key 2.

Example 2

Input: ["LRUCache", "put", "put", "get"] [[1], [5, 1], [5, 2], [5]]
Output: [null, null, null, 2]

Writing an existing key overwrites it without evicting anything.

Constraints

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2 × 10⁵ calls to get and put.

Practice

Runs 8 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked LRU Cache in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve LRU Cache

Pattern: Hash map + doubly linked list

Approach 1: Array or list with timestamps

Store entries with a "last used" counter and scan for the smallest counter when you need to evict. Simple, but eviction (or reordering a list) costs O(n), which fails the O(1) requirement.

Time O(n) per operation · Space O(capacity)

Approach 2: Ordered map from the standard library

Time O(1) · Space O(capacity)

Approach 3: Hash map + doubly linked list

Use sentinel head and tail nodes so you never special-case an empty list.

get(key): look up the node; if missing return -1, otherwise move it to the front and return its value.
put(key, value): if the key exists, update the value and move it to the front. Otherwise create a node, add it to the front and the map, and if the map is now over capacity, remove the node just before tail and delete its key.

Each node stores its key so eviction knows which map entry to delete.

Time O(1) · Space O(capacity)

Approach	Time	Space
Array or list with timestamps	O(n) per operation	O(capacity)
Ordered map from the standard library	O(1)	O(capacity)
Hash map + doubly linked list	O(1)	O(capacity)

Solution code

Try the practice editor first. Both solutions pass every test above.

LRU Cache solution in Python

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}  # key -> Node
        self.head = Node()  # most recent side
        self.tail = Node()  # least recent side
        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_to_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        node = Node(key, value)
        self.nodes[key] = node
        self._add_to_front(node)
        if len(self.nodes) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.nodes[lru.key]

LRU Cache solution in JavaScript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.nodes = new Map(); // key -> node
    this.head = { prev: null, next: null }; // most recent side
    this.tail = { prev: this.head, next: null }; // least recent side
    this.head.next = this.tail;
  }

  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  addToFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.nodes.get(key);
    if (!node) return -1;
    this.remove(node);
    this.addToFront(node);
    return node.value;
  }

  put(key, value) {
    const existing = this.nodes.get(key);
    if (existing) {
      existing.value = value;
      this.remove(existing);
      this.addToFront(existing);
      return;
    }
    const node = { key, value, prev: null, next: null };
    this.nodes.set(key, node);
    this.addToFront(node);
    if (this.nodes.size > this.capacity) {
      const lru = this.tail.prev;
      this.remove(lru);
      this.nodes.delete(lru.key);
    }
  }
}

Common mistakes

Forgetting that a successful get also updates recency.
Evicting before checking whether put is overwriting an existing key, which throws out an entry for no reason.
Not storing the key on the list node, so eviction can't find the map entry to delete.
Using a singly linked list, which makes unlinking a node O(n) because you need its predecessor.

What interviewers look for

Say why each structure is there before writing code: "the map gives me O(1) lookup, the list gives me O(1) reordering, and I need both." That sentence is most of what the interviewer is checking for.

Follow-up questions

How would you make it thread-safe?

Wrap get and put in a single lock, since both mutate the list. For high concurrency, shard the cache by key hash so each shard has its own lock and list.

How does this differ from an LFU cache?

LFU evicts the key used the fewest times, breaking ties by recency. It needs a map from frequency to a list of keys plus a tracked minimum frequency, so every operation still stays O(1).

What if entries should also expire after a time-to-live?

Store an expiry timestamp on each node and treat expired entries as missing on read. To reclaim memory proactively, keep a min-heap of expiry times or sweep lazily from the tail.

Companies that ask LRU Cache

LRU Cache is tagged by 196 companies in our interview dataset. The score shows how often it comes up at each company.

and 172 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve LRU Cache

Approach 1: Array or list with timestamps

Approach 2: Ordered map from the standard library

Approach 3: Hash map + doubly linked list

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How would you make it thread-safe?

How does this differ from an LFU cache?

What if entries should also expire after a time-to-live?

Companies that ask LRU Cache

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve LRU Cache

Approach 1: Array or list with timestamps

Approach 2: Ordered map from the standard library

Approach 3: Hash map + doubly linked list

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How would you make it thread-safe?

How does this differ from an LFU cache?

What if entries should also expire after a time-to-live?

Companies that ask LRU Cache

Practice next

Get live help in the real interview