LRU Cache

Design a Least Recently Used (LRU) cache — the eviction policy behind many in-process caches.

LRUCache(capacity) creates a cache holding at most capacity keys.
get(key) returns the value, or -1 if absent. A successful get makes the key most recently used.
put(key, value) inserts or updates the key (making it most recently used). If this exceeds capacity, evict the least recently used key.

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

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]

Solution and explanation

Show the solution

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

Pair a hash map (key → node) with a doubly linked list ordered by recency. get moves the node to the front; put updates or inserts at the front and, when over capacity, removes the tail node and its map entry. Every step is O(1).

In interviews it's fine to show the language shortcut first — JavaScript's Map and Python's OrderedDict keep insertion order, so "delete and re-insert" moves a key to the most-recent end — then explain (or implement) the linked-list version, as the Java reference does with LinkedHashMap(accessOrder = true).

Reference solution

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // insertion order = recency order (oldest first)
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) this.map.delete(this.map.keys().next().value);
  }
}

class Node {
  prev: Node | null = null;
  next: Node | null = null;
  constructor(public key: number, public value: number) {}
}

class LRUCache {
  private map = new Map<number, Node>();
  private head = new Node(0, 0); // most recent after head
  private tail = new Node(0, 0); // least recent before tail

  constructor(private capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.unlink(node);
    this.pushFront(node);
    return node.value;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) this.unlink(existing);
    const node = new Node(key, value);
    this.map.set(key, node);
    this.pushFront(node);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev!;
      this.unlink(lru);
      this.map.delete(lru.key);
    }
  }

  private unlink(n: Node): void {
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
  }

  private pushFront(n: Node): void {
    n.next = this.head.next;
    n.prev = this.head;
    this.head.next!.prev = n;
    this.head.next = n;
  }
}

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.items:
            return -1
        self.items.move_to_end(key)
        return self.items[key]

    def put(self, key: int, value: int) -> None:
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)

<?php

class LRUCache
{
    /** @var array<int,int> PHP arrays keep insertion order: oldest first. */
    private array $items = [];

    public function __construct(private int $capacity)
    {
    }

    public function get(int $key): int
    {
        if (!array_key_exists($key, $this->items)) {
            return -1;
        }
        $value = $this->items[$key];
        unset($this->items[$key]);
        $this->items[$key] = $value;
        return $value;
    }

    public function put(int $key, int $value): void
    {
        unset($this->items[$key]);
        $this->items[$key] = $value;
        if (count($this->items) > $this->capacity) {
            unset($this->items[array_key_first($this->items)]);
        }
    }
}

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // accessOrder = true: get() moves an entry to the end; removeEldestEntry evicts the LRU one.
        this.map = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}

Common mistakes

Forgetting that get also updates recency.
Updating an existing key without moving it to most-recent.
Evicting before checking whether the key already exists.

Follow-up questions

Make it thread-safe.
Add TTL expiry (see the TTL cache task).
LFU cache: evict the least frequently used key.

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

More Design & Data Structures problems