LRU Cache

Design a data structure that follows Least Recently Used (LRU) eviction with O(1) get and put operations.

Language Selection

Choose your preferred programming language

Showing: Python

LRU Cache

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) – Initialize the LRU cache with positive size capacity.
  • int get(int key) – Return the value of the key if it exists, otherwise return -1.
  • void put(int key, int value) – Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

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]

Explanation:
LRUCache cache = new LRUCache(2);
cache.put(1, 1);    // cache is {1=1}
cache.put(2, 2);    // cache is {1=1, 2=2}
cache.get(1);       // return 1, cache is {2=2, 1=1} (1 is now most recent)
cache.put(3, 3);    // evicts key 2, cache is {1=1, 3=3}
cache.get(2);       // return -1 (not found)
cache.put(4, 4);    // evicts key 1, cache is {3=3, 4=4}
cache.get(1);       // return -1 (not found)
cache.get(3);       // return 3
cache.get(4);       // return 4

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

Approach 1: Language Built-in OrderedDict / LinkedHashMap

Algorithm

Many languages provide an ordered dictionary that maintains insertion order and supports O(1) move-to-end. This gives a concise implementation.

Steps:

  1. Use an ordered dictionary (Python OrderedDict, Java LinkedHashMap)
  2. On get: if key exists, move it to the end (most recent) and return its value
  3. On put: if key exists, move it to the end and update its value; if new, insert at end; if over capacity, remove the first (oldest) entry

Implementation

Python:

from collections import OrderedDict

class LRUCache:
    """
    LRU Cache using Python's OrderedDict
    Time: O(1) for get and put
    Space: O(capacity)
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update value and move to end
            self.cache.move_to_end(key)
            self.cache[key] = value
        else:
            # Insert new entry
            self.cache[key] = value
            if len(self.cache) > self.capacity:
                # Remove least recently used (first item)
                self.cache.popitem(last=False)

Java:

import java.util.*;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    /**
     * LRU Cache using Java's LinkedHashMap
     * Time: O(1) for get and put
     * Space: O(capacity)
     */
    private int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true makes it order by access time
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

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

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

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

Go:

// Go does not have a built-in OrderedDict.
// See Approach 2 for the manual implementation.

JavaScript:

/**
 * LRU Cache using JavaScript Map (maintains insertion order)
 * Time: O(1) for get and put
 * Space: O(capacity)
 */
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        // Move to end by deleting and re-inserting
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // Remove old entry so re-insert goes to end
            this.cache.delete(key);
        }
        this.cache.set(key, value);

        if (this.cache.size > this.capacity) {
            // Remove least recently used (first key)
            const firstKey = this.cache.keys().next().value;
            this.cache.delete(firstKey);
        }
    }
}

C#:

// C# does not have a built-in OrderedDict with move-to-end.
// See Approach 2 for the manual implementation.

Complexity Analysis

  • Time Complexity: O(1) amortized for both get and put
  • Space Complexity: O(capacity) for storing up to capacity entries

Approach 2: Hash Map + Doubly Linked List (Manual Implementation)

Algorithm

Combine a hash map for O(1) key lookup with a doubly linked list for O(1) insertion, deletion, and reordering. The list head is the least recently used item and the tail is the most recently used.

Steps:

  1. Maintain a doubly linked list with dummy head and tail sentinel nodes
  2. Maintain a hash map from key to the corresponding list node
  3. On get: look up the node in the map, move it to the tail (most recent), return its value
  4. On put: if key exists, update value and move to tail; if new, create node at tail; if over capacity, remove the node after head (least recent) and delete from map

Implementation

Python:

class DLinkedNode:
    """Doubly linked list node for LRU cache"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    """
    LRU Cache using hash map + doubly linked list
    Time: O(1) for get and put
    Space: O(capacity)
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> DLinkedNode

        # Dummy head and tail sentinels
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """Remove a node from the linked list"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_tail(self, node):
        """Add a node right before the tail sentinel (most recent)"""
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        node = self.cache[key]
        # Move to most recent position
        self._remove(node)
        self._add_to_tail(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing node
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_tail(node)
        else:
            # Create new node
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_tail(node)

            if len(self.cache) > self.capacity:
                # Evict least recently used (node after head)
                lru = self.head.next
                self._remove(lru)
                del self.cache[lru.key]

Java:

import java.util.*;

class LRUCache {
    /**
     * LRU Cache using hash map + doubly linked list
     * Time: O(1) for get and put
     * Space: O(capacity)
     */

    private class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        DLinkedNode() {}
        DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private Map<Integer, DLinkedNode> cache;
    private DLinkedNode head;
    private DLinkedNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        // Dummy head and tail sentinels
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    private void remove(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToTail(DLinkedNode node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }

        DLinkedNode node = cache.get(key);
        remove(node);
        addToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            DLinkedNode node = cache.get(key);
            node.value = value;
            remove(node);
            addToTail(node);
        } else {
            DLinkedNode node = new DLinkedNode(key, value);
            cache.put(key, node);
            addToTail(node);

            if (cache.size() > capacity) {
                DLinkedNode lru = head.next;
                remove(lru);
                cache.remove(lru.key);
            }
        }
    }
}

Go:

import "container/list"

// LRUCache - LRU Cache using hash map + doubly linked list
// Time: O(1) for Get and Put
// Space: O(capacity)
type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    order    *list.List // front = least recent, back = most recent
}

type entry struct {
    key   int
    value int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        order:    list.New(),
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // Move to back (most recent)
        c.order.MoveToBack(elem)
        return elem.Value.(*entry).value
    }
    return -1
}

func (c *LRUCache) Put(key int, value int) {
    if elem, ok := c.cache[key]; ok {
        // Update existing entry and move to back
        elem.Value.(*entry).value = value
        c.order.MoveToBack(elem)
    } else {
        // Add new entry at back
        elem := c.order.PushBack(&entry{key, value})
        c.cache[key] = elem

        if c.order.Len() > c.capacity {
            // Evict least recently used (front)
            lru := c.order.Front()
            c.order.Remove(lru)
            delete(c.cache, lru.Value.(*entry).key)
        }
    }
}

JavaScript:

/**
 * LRU Cache using hash map + doubly linked list
 * Time: O(1) for get and put
 * Space: O(capacity)
 */
class DLinkedNode {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // key -> DLinkedNode

        // Dummy head and tail sentinels
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

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

    _addToTail(node) {
        node.prev = this.tail.prev;
        node.next = this.tail;
        this.tail.prev.next = node;
        this.tail.prev = node;
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }

        const node = this.cache.get(key);
        this._remove(node);
        this._addToTail(node);
        return node.value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.value = value;
            this._remove(node);
            this._addToTail(node);
        } else {
            const node = new DLinkedNode(key, value);
            this.cache.set(key, node);
            this._addToTail(node);

            if (this.cache.size > this.capacity) {
                // Evict least recently used (node after head)
                const lru = this.head.next;
                this._remove(lru);
                this.cache.delete(lru.key);
            }
        }
    }
}

C#:

using System.Collections.Generic;

public class LRUCache {
    /// <summary>
    /// LRU Cache using hash map + doubly linked list
    /// Time: O(1) for Get and Put
    /// Space: O(capacity)
    /// </summary>

    private class DLinkedNode {
        public int Key;
        public int Value;
        public DLinkedNode Prev;
        public DLinkedNode Next;

        public DLinkedNode(int key = 0, int value = 0) {
            Key = key;
            Value = value;
        }
    }

    private int capacity;
    private Dictionary<int, DLinkedNode> cache;
    private DLinkedNode head;
    private DLinkedNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new Dictionary<int, DLinkedNode>();

        // Dummy head and tail sentinels
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.Next = tail;
        tail.Prev = head;
    }

    private void Remove(DLinkedNode node) {
        node.Prev.Next = node.Next;
        node.Next.Prev = node.Prev;
    }

    private void AddToTail(DLinkedNode node) {
        node.Prev = tail.Prev;
        node.Next = tail;
        tail.Prev.Next = node;
        tail.Prev = node;
    }

    public int Get(int key) {
        if (!cache.ContainsKey(key)) {
            return -1;
        }

        DLinkedNode node = cache[key];
        Remove(node);
        AddToTail(node);
        return node.Value;
    }

    public void Put(int key, int value) {
        if (cache.ContainsKey(key)) {
            DLinkedNode node = cache[key];
            node.Value = value;
            Remove(node);
            AddToTail(node);
        } else {
            DLinkedNode node = new DLinkedNode(key, value);
            cache[key] = node;
            AddToTail(node);

            if (cache.Count > capacity) {
                // Evict least recently used (node after head)
                DLinkedNode lru = head.Next;
                Remove(lru);
                cache.Remove(lru.Key);
            }
        }
    }
}

Complexity Analysis

  • Time Complexity: O(1) for both get and put. Hash map lookup is O(1). Linked list insertion and deletion are O(1).
  • Space Complexity: O(capacity) for storing the cache entries in both the map and the list.

Key Insights

  1. Two Data Structures: A hash map alone cannot track recency order. A linked list alone cannot provide O(1) key lookup. Combining both gives O(1) for all operations.
  2. Sentinel Nodes: Dummy head and tail nodes eliminate null checks when inserting or removing at the boundaries of the list.
  3. Store Key in Node: The doubly linked list node must store the key so that when evicting the LRU node, we can delete the corresponding entry from the hash map.
  4. Move to Tail on Access: Both get and put (for existing keys) move the node to the tail, marking it as most recently used.
  5. Eviction at Head: The node right after the dummy head is always the least recently used, making eviction O(1).

Edge Cases

  1. Capacity of 1: Every new distinct key evicts the previous one
  2. Get on Missing Key: Returns -1 without modifying the cache state
  3. Update Existing Key: put on an existing key updates the value and moves it to most recent
  4. Repeated Gets: Multiple gets on the same key should keep it at the most recent position
  5. Put Then Immediate Eviction: Adding a key that immediately triggers eviction of the oldest entry
  6. All Same Key: Repeated puts on the same key should never trigger eviction

Test Cases

def test_lru_cache():
    # Example from problem statement
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1       # Returns 1, moves key 1 to most recent
    cache.put(3, 3)                # Evicts key 2 (least recently used)
    assert cache.get(2) == -1      # Key 2 was evicted
    cache.put(4, 4)                # Evicts key 1
    assert cache.get(1) == -1      # Key 1 was evicted
    assert cache.get(3) == 3       # Key 3 still present
    assert cache.get(4) == 4       # Key 4 still present

    # Capacity 1
    cache2 = LRUCache(1)
    cache2.put(1, 10)
    assert cache2.get(1) == 10
    cache2.put(2, 20)              # Evicts key 1
    assert cache2.get(1) == -1
    assert cache2.get(2) == 20

    # Update existing key
    cache3 = LRUCache(2)
    cache3.put(1, 1)
    cache3.put(2, 2)
    cache3.put(1, 10)              # Update key 1, moves to most recent
    cache3.put(3, 3)               # Should evict key 2, not key 1
    assert cache3.get(2) == -1
    assert cache3.get(1) == 10
    assert cache3.get(3) == 3

    # Get missing key
    cache4 = LRUCache(2)
    assert cache4.get(1) == -1     # Empty cache
    cache4.put(1, 1)
    assert cache4.get(2) == -1     # Key not present

    print("All tests passed!")

test_lru_cache()

Follow-up Questions

  1. LFU Cache: Design a Least Frequently Used cache where eviction is based on access count (LeetCode #460)
  2. Thread-Safe LRU: How would you make the LRU cache thread-safe for concurrent access?
  3. TTL Support: How would you add time-to-live expiration for cache entries?
  4. Distributed LRU: How would you implement an LRU cache across multiple machines?
  5. Variable Size Entries: What if cached values have different sizes and you have a total memory budget?

Common Mistakes

  1. Forgetting to Store Key in Node: Without the key in the list node, you cannot remove the evicted entry from the hash map
  2. Not Moving on Update: Failing to move a node to the most recent position when put updates an existing key
  3. Null Pointer on Remove: Not handling edge cases when removing from an empty list; sentinel nodes prevent this
  4. Wrong Eviction Order: Evicting the most recently used instead of the least recently used
  5. Off-by-One on Capacity: Inserting before checking capacity, or checking capacity before inserting, leading to cache size exceeding the limit

Interview Tips

  1. Draw the Data Structure: Sketch the doubly linked list with sentinel nodes and the hash map pointing to nodes
  2. Explain Why Two Structures: Clearly articulate that the hash map gives O(1) lookup and the linked list gives O(1) ordering operations
  3. Start with the API: Define the get and put signatures first, then discuss the internal implementation
  4. Mention the Built-in Approach: Show awareness of OrderedDict/LinkedHashMap, but be ready to implement from scratch
  5. Discuss Sentinel Nodes: Explain how dummy head and tail simplify boundary conditions

Concept Explanations

LRU Eviction Policy: When the cache is full and a new entry must be added, evict the entry that was accessed (read or written) least recently. This policy works well in practice because recently accessed data is likely to be accessed again soon (temporal locality).

Hash Map + Doubly Linked List: The hash map provides O(1) access by key. The doubly linked list maintains the access order, with the most recently used at one end and the least recently used at the other. Together, they support O(1) get, put, and eviction.

Sentinel Nodes: Dummy head and tail nodes that never hold real data. They ensure that every real node has a valid prev and next pointer, eliminating special cases for inserting at the front or removing from the back.

Why Not a Singly Linked List: Removing a node from a singly linked list requires a reference to the previous node, which means traversal. A doubly linked list stores the prev pointer, enabling O(1) removal given a direct reference to the node.