Skip to main content

146. LRU Cache

mediumAsked at AMD

Design a Least Recently Used cache with O(1) get and put. AMD asks this because cache design is central to their business — TLBs, L1/L2/L3 caches, and GPU shared-memory eviction policies all operate on LRU or LRU-like principles. Understanding the data structure composition here directly maps to hardware cache architecture reasoning.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates consistently cite LRU Cache as a high-frequency medium at AMD, often accompanied by hardware cache follow-ups.
  • Blind (2025-11)— AMD interview threads flag LRU Cache as the canonical data-structure-composition problem for AMD's hardware-aware engineering culture.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity) initializes the LRU cache with a positive size capacity. int get(int key) returns the value of the key if it exists, otherwise -1. void put(int key, int value) updates the value if the key exists, otherwise inserts the key-value pair. When the number of keys exceeds the capacity, evict the least recently used key. Both get and put must 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]

Explanation: After put(3,3), key 2 (least recently used) is evicted. After put(4,4), key 1 was used by get(1), so key 3 is evicted instead.

Approaches

1. Ordered Map (JS Map insertion order)

JS Map preserves insertion order. On access, delete and re-insert to move to the end (most recent). Evict the first key (least recent) when over capacity.

Time
O(1) 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;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
  }
}

Tradeoff: O(1) amortized. Relies on JS Map's insertion-order guarantee (ECMAScript spec). Practical for JS. AMD interviewers will typically ask for the explicit doubly-linked-list version to confirm understanding.

2. Hash Map + Doubly Linked List (canonical)

A Map provides O(1) key lookup; a doubly-linked list provides O(1) move-to-front and evict-from-tail. The map stores key → node. Dummy head and tail sentinels eliminate edge cases.

Time
O(1) get and put
Space
O(capacity)
class Node {
  constructor(key, val) { this.key = key; this.val = val; this.prev = this.next = null; }
}
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(0, 0); // dummy MRU end
    this.tail = new Node(0, 0); // dummy LRU end
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertFront(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._insertFront(node);
    return node.val;
  }
  put(key, value) {
    if (this.map.has(key)) this._remove(this.map.get(key));
    const node = new Node(key, value);
    this._insertFront(node);
    this.map.set(key, node);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff: True O(1) for all operations. No reliance on language insertion-order behavior. This is the answer AMD expects for a hardware-aware role.

AMD-specific tips

AMD's entire product line revolves around cache design: CPU L1/L2/L3, GPU shared memory, TLBs, texture caches, and PCIe buffer caches all use LRU or pseudo-LRU eviction. Frame your answer architecturally before writing code: 'O(1) lookup needs a hash map; O(1) move-to-front and O(1) eviction from the tail need a doubly-linked list — a singly-linked list can't remove a node in O(1) without its predecessor.' AMD interviewers will probe how hardware LRU differs from this software version — mention that hardware uses pseudo-LRU trees for associativity constraints.

Common mistakes

  • Using a singly-linked list — removing an arbitrary node requires O(n) traversal.
  • Forgetting to remove the evicted node from the map — the map and DLL must stay in sync.
  • Not moving the node to the front on get() — a cache hit makes the entry most-recently-used.
  • Skipping dummy head/tail — every insert/remove then requires null-checks for the first and last node.

Follow-up questions

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

  • LFU Cache (LC 460) — evict the least-frequently-used entry; requires a frequency-bucket DLL.
  • How does hardware pseudo-LRU differ from true LRU in a set-associative cache?
  • What is the time complexity if you implemented this with a sorted array instead?

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 a doubly-linked list and not a singly-linked list?

To remove an arbitrary node in O(1), you need a pointer to its predecessor. A singly-linked list requires O(n) traversal to find the predecessor.

Why dummy sentinel nodes?

They eliminate null checks at the head and tail. Every insert and remove is uniform pointer rewiring — no special cases for empty list or single-element list.

How does pseudo-LRU differ from this software LRU?

Hardware caches have fixed associativity (e.g., 8-way). Tracking true LRU order for 8 slots needs 3 bits per way. Pseudo-LRU approximates this with a binary tree of bits, sacrificing perfect LRU for simpler hardware implementation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →