LRU Cache - Amazon Interview Question & Solution

Back to All Questions

LRU Cache

Amazon

Hash Table

Doubly Linked List

Design

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

Implement the LRUCache class:

LRUCache(capacity) initializes the cache with a positive size capacity.
get(key) returns the value of the key if it exists, otherwise -1. Accessing a key counts as a "use".
put(key, value) updates the value of the key if it exists, or adds the key-value pair. If the number of keys exceeds capacity, evict the least recently used key.

Both get and put must run in O(1) average time complexity.

Solution Walkthrough

The textbook solution combines a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering of recency, since you can unlink and relink a node without shifting anything).

The hash map stores key → node, where each node lives in a doubly linked list ordered from most-recently-used (head) to least-recently-used (tail).
On get(key): if the key exists, unlink its node and re-insert it at the head (marking it as freshly used), then return its value. Otherwise return -1.
On put(key, value): if the key exists, update its value and move it to the head. Otherwise create a new node at the head; if this pushes the cache over capacity, remove the tail node (the least recently used one) from both the list and the map.

JavaScript's built-in Map actually preserves insertion order and lets you re-insert a key to move it to the "most recent" end, which makes for a much shorter implementation of the same O(1) idea without hand-rolling a linked list:

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // preserves insertion order
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const value = this.cache.get(key);
        // Re-insert to mark as most recently used
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // Map iterates in insertion order, so the first key is the least recently used
            const lruKey = this.cache.keys().next().value;
            this.cache.delete(lruKey);
        }
        this.cache.set(key, value);
    }
}

Related Algorithms

Hashing →

Doubly Linked List →