Skip to main content

146. LRU Cache

mediumAsked at Citadel

LRU Cache is directly relevant to Citadel's systems work: caching market data, reference data (security master), and computed risk metrics all require eviction policies. Citadel interviewers use this to verify you can compose a hash map and doubly-linked list into O(1) get and put — and that you understand why each structure is necessary.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2026-Q1)— Citadel SWE candidates frequently cite LRU Cache as a high-signal question in second-round and on-site coding assessments.
  • Blind (2025-11)— Citadel SWE threads list LRU Cache as one of the most-asked data structure design problems, often paired with system design discussion.

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 (LRU) is evicted. After put(4,4), key 3 (now LRU) is evicted.

Approaches

1. JavaScript Map (insertion-order exploitation)

JS Map preserves insertion order. Delete and re-insert a key on access to move it to 'most recent'. Evict the first key (LRU) 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); // move to most-recent end
    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); // evict LRU
    }
  }
}

Tradeoff: O(1) amortized. JS-specific — relies on ECMAScript-spec Map insertion order guarantee. Fast in practice. Citadel interviewers will ask for the explicit DLL version to verify understanding.

2. Hash map + doubly-linked list (canonical)

Map gives O(1) key lookup; doubly-linked list gives O(1) move-to-front and tail eviction. Dummy head and tail simplify boundary operations.

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(); // key -> node
    this.head = new Node(0, 0); // dummy MRU
    this.tail = new Node(0, 0); // dummy LRU
    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: Explicit O(1) for all operations, no reliance on language-specific Map ordering. Required by Citadel when they say 'implement without built-in ordered structures.' The doubly-linked list must store the key in each node so the map can be updated on eviction.

Citadel-specific tips

Explain the data structure composition before coding: 'O(1) lookup → hash map. O(1) move-to-front and eviction → doubly-linked list. The DLL node stores the key (not just value) so the map entry can be deleted on eviction.' Citadel will press on thread safety: 'How would you make this concurrent?' Answer: reader-writer locks or a concurrent skip list. At low latency, a bounded-size concurrent map with CAS-based eviction is the production answer — mention it even if you don't implement it.

Common mistakes

  • Storing only the value (not the key) in the DLL node — you can't delete the map entry on eviction without the key.
  • Forgetting to delete from the map when evicting — the map and list go out of sync, causing stale gets.
  • Not moving a node to the front on get() — a cache hit counts as recent use.
  • Skipping dummy head/tail — every insert/remove then needs special null checks for the empty-list case.

Follow-up questions

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

  • LFU Cache (LC 460) — evict least-frequently-used; requires frequency buckets.
  • How would you make the LRU cache thread-safe for concurrent reads and writes?
  • Design a distributed LRU cache across multiple nodes.

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 does the DLL node need to store the key?

When evicting the LRU node (tail.prev), you must also delete it from the hash map. Without the key in the node, you can't find the map entry in O(1).

Why dummy head and tail?

They eliminate null-pointer checks when inserting at the front or removing from the back. Every operation becomes uniform four-pointer rewiring.

At Citadel's scale, what replaces an in-process LRU cache?

A distributed cache with TTL-based expiry and probabilistic eviction, implemented in C++ with lock-free data structures or hardware-assisted compare-and-swap. Mentioning this demonstrates production systems thinking.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →