Skip to main content

146. LRU Cache

mediumAsked at Amazon

Design a cache that evicts the least recently used key when full. Amazon asks this to test whether you can combine a doubly-linked list (for O(1) reorder) with a hash map (for O(1) lookup).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring data-structure design problem.
  • Blind (2025-11)— Recurring Amazon interview problem.

Problem

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 the key exists, otherwise return -1. void put(int key, int value) update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

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(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output
[null,null,null,1,null,-1,null,-1,3,4]

Approaches

1. Hash map + JavaScript Map (insertion-ordered)

JS Map preserves insertion order. Delete + re-insert on access to refresh recency.

Time
O(1) average
Space
O(capacity)
class LRUCacheMap {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
    this.map.set(key, value);
  }
}

Tradeoff: Concise and uses language feature. Often acceptable in Amazon interviews if you also offer the doubly-linked-list version. Some interviewers prefer the explicit DS.

2. Doubly linked list + hash map (canonical)

Hash map from key to DLL node + doubly linked list with sentinel head/tail. Move-to-front on get/put; evict from tail.

Time
O(1) worst case
Space
O(capacity)
class Node {
  constructor(key, val) { this.key = key; this.val = val; this.prev = null; this.next = null; }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) { node.prev.next = node.next; node.next.prev = node.prev; }
  _addFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addFront(node);
    return node.val;
  }
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this._remove(node);
      this._addFront(node);
      return;
    }
    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this._addFront(node);
  }
}

Tradeoff: Textbook answer. Sentinel nodes eliminate edge cases that often trip candidates.

Amazon-specific tips

Amazon interviewers grade this on two axes: (1) you understand WHY both structures are needed (hash map for lookup, DLL for O(1) reorder); (2) sentinel head/tail. The interviewer may explicitly say 'don't use language built-ins,' in which case the DLL version is required.

Common mistakes

  • Using a singly linked list — O(1) node removal requires the prev pointer.
  • Forgetting to remove the evicted key from the hash map (memory leak).
  • Off-by-one on capacity check.
  • Forgetting sentinels — leads to null derefs when removing head or tail.

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • LFU Cache (LC 460) — least frequently used.
  • Add TTL per key.
  • Make it thread-safe.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why both data structures?

Hash map gives O(1) lookup. DLL gives O(1) splice (move to front, remove from tail). Neither alone gives both.

Will Amazon accept the Map shortcut?

Some interviewers, yes — for the conciseness. Some explicitly require DLL to verify you understand the data structure. Have both ready.

Practice these live with InterviewChamp.AI

Drill LRU Cache and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →