Skip to main content

146. LRU Cache

mediumAsked at Cisco

LRU Cache at Cisco is the OOP design problem the company most reliably asks because cache layers sit in every product they ship — from route lookup tables to ARP entries. The interviewer is checking whether you reach for the hash-map-plus-doubly-linked-list combo and whether you can wire the splice/unlink helpers without errors.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II and SDE-III onsite reports cite LRU Cache as the canonical OOP design round.
  • Blind (2025-10)— Cisco interview thread lists LRU Cache as a recurring problem across teams.
  • Levels.fyi (2025-09)— Cisco interview write-ups for backend roles cite LRU as a 45-minute coding round.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initializes the LRU cache with positive size capacity. int get(int key) returns the value of the key if the key exists, otherwise returns -1. void put(int key, int value) updates the value of the key if the key exists. Otherwise, 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.

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), cache is at capacity so key 2 is evicted. After put(4,4), key 1 is evicted.

Approaches

1. Brute-force: array of [key, value] pairs, scan on every op

Linear scan to find a key. Move it to the front on access. Pop from the back on eviction.

Time
O(n) per op
Space
O(n)
class LRUCacheBrute {
  constructor(capacity) {
    this.cap = capacity;
    this.arr = [];
  }
  get(key) {
    const idx = this.arr.findIndex(p => p[0] === key);
    if (idx === -1) return -1;
    const [pair] = this.arr.splice(idx, 1);
    this.arr.unshift(pair);
    return pair[1];
  }
  put(key, value) {
    const idx = this.arr.findIndex(p => p[0] === key);
    if (idx !== -1) this.arr.splice(idx, 1);
    this.arr.unshift([key, value]);
    if (this.arr.length > this.cap) this.arr.pop();
  }
}

Tradeoff: Wrong answer for the rubric — Cisco requires O(1). Useful to show you understand the semantics before optimizing.

2. Hash map + doubly linked list (optimal)

Hash map: key -> Node. Doubly linked list ordered by recency (head = most recent, tail = least). On get/put: unlink node from current position, insert at head. On overflow: remove tail.

Time
O(1) per op
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = { key: 0, val: 0, prev: null, next: null };
    this.tail = { key: 0, val: 0, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertHead(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._unlink(node);
    this._insertHead(node);
    return node.val;
  }
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this._unlink(node);
      this._insertHead(node);
      return;
    }
    const node = { key, val: value, prev: null, next: null };
    this.map.set(key, node);
    this._insertHead(node);
    if (this.map.size > this.cap) {
      const lru = this.tail.prev;
      this._unlink(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff: The classic answer. Sentinel head/tail nodes eliminate the null-check headache on edge nodes. Map values are the linked-list nodes themselves (NOT the values) so unlink is O(1). This is what Cisco wants on the whiteboard.

3. Use JS Map insertion order (interview shortcut)

JS Map preserves insertion order, so delete-and-reinsert moves a key to the most-recent position. iterator.next().value gives the oldest.

Time
O(1) per op
Space
O(capacity)
class LRUCacheShortcut {
  constructor(capacity) { this.cap = 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.cap) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

Tradeoff: Genuinely O(1) per op and uses ~15 lines. But Cisco interviewers want to see you BUILD the doubly-linked-list structure because it's the language-agnostic answer. Use this only if the interviewer says 'JS-idiomatic is fine' or asks specifically for the Map trick.

Cisco-specific tips

Cisco interviewers are strict about two things: (1) you reach for the hash-map-plus-DLL combo BEFORE writing any code, and (2) you use sentinel head/tail nodes to avoid edge-case null checks. State out loud: 'I store nodes in a hash map for O(1) lookup, ordered in a doubly-linked list for O(1) reorder.' Diagram it on the whiteboard with arrows showing prev/next. The map-shortcut version is fine if they explicitly say 'use idioms', but default to the DLL.

Common mistakes

  • Storing values in the map instead of node references — breaks O(1) because you can't unlink without scanning the list.
  • Forgetting to update both `prev.next` AND `next.prev` on unlink — leaves dangling pointers and the next traversal walks off into garbage.
  • Updating the map size but not actually removing the evicted node from the list — slow leak that surfaces on the second eviction.
  • Skipping sentinel nodes — then every unlink/insert has to handle 'is this the head/tail?' edge cases and the code triples in length.

Follow-up questions

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

  • LFU Cache (LC 460) — Least Frequently Used with frequency buckets.
  • Design a TTL cache — entries also expire after time T.
  • Make it thread-safe — discussion of locks / lock-free structures.
  • Capacity as a memory budget rather than entry count.

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 doubly-linked, not singly-linked?

Because unlink-from-the-middle has to update the prev pointer of the next node. With a singly-linked list you'd need to walk from the head to find prev, which kills O(1).

Are the sentinel head/tail nodes really necessary?

Strictly no, but they eliminate the 'is this the only node?' and 'is this the actual head?' null checks throughout. Without sentinels the code is ~2x as long and ~3x as bug-prone. Cisco interviewers EXPECT sentinels — write them on the whiteboard before the methods.

Why store key on the node?

Because on eviction, you need to know which key to delete from the map. If the node only carries the value, you can't tell the map which entry to forget.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →