Skip to main content

146. LRU Cache

mediumAsked at Bloomberg

Bloomberg Terminal caches thousands of live ticker snapshots in memory — this problem tests whether you can build the eviction policy that keeps the most-recently-accessed instruments hot while dropping stale ones in O(1) per operation.

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

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with a capacity constructor, get(key) returning the value or -1, and put(key, value) inserting or updating the key-value pair, evicting the LRU key when capacity is exceeded. Both operations must run in O(1) average time.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls 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) the cache is full and key 2 (LRU) is evicted. After put(4,4) key 1 would be evicted but get(1) refreshed it earlier, so key 3 is the LRU.

Approaches

1. Hash map + ordered structure (naive)

Use a Map to track insertion order, iterate to find and evict the least-recently-used key. O(n) eviction.

Time
O(n) evict, O(1) get/put otherwise
Space
O(capacity)
class LRUCache {
  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);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff:

2. Hash map + doubly linked list (optimal O(1))

A doubly linked list keeps recency order; a hash map gives O(1) node access. On get/put, splice the node to the tail (most recent). On eviction, remove from the head (least recent).

Time
O(1) all operations
Space
O(capacity)
class Node {
  constructor(k, v) { this.key = k; this.val = v; this.prev = this.next = null; }
}

class LRUCache {
  constructor(capacity) {
    this.cap = 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;
  }
  _addToTail(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addToTail(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._addToTail(node);
    this.map.set(key, node);
    if (this.map.size > this.cap) {
      const lru = this.head.next;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff:

Bloomberg-specific tips

Bloomberg asks this question specifically to probe your system-design instincts — they want to hear you connect the abstract cache to something concrete, like buffering real-time Bloomberg Terminal quote updates. Nail the O(1) invariant up front, then walk through the doubly linked list pointer surgery carefully; interviewers have seen candidates lose an offer by getting the sentinel-node wiring wrong under pressure.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →