Skip to main content

146. LRU Cache

mediumAsked at Broadcom

Design a cache that evicts the least-recently-used entry when full. Broadcom asks this because LRU is the dominant eviction policy in ARP caches, MAC address tables, and route-cache entries inside Broadcom's switching and routing ASICs — getting O(1) get and put right is a real firmware concern.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Cited in Broadcom SWE onsite reports as a high-signal design-plus-coding question across networking and infrastructure software roles.
  • Blind (2025-11)— Broadcom threads list LRU Cache as a near-mandatory medium problem — especially for roles involving caching layers and firmware.

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.

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: get(1) refreshes key 1; put(3,3) evicts key 2 (LRU). get(2) returns -1. put(4,4) evicts key 1 (now LRU after key 3 was inserted). get(1)=1 because key 1 was put back by put(4,4) — no, key 1 was evicted; follow the sequence carefully.

Approaches

1. Ordered Map (JavaScript built-in)

JS Map preserves insertion order. On access, delete and re-insert the key to move it to the 'most recent' position. 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) amortised. Relies on JS Map insertion-order guarantee. A good practical answer in JS. Broadcom interviewers may ask for the explicit doubly-linked-list version to test data-structure composition.

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

A Map gives O(1) key lookup; a doubly-linked list gives O(1) move-to-front (most recent) and eviction from the tail (least recent). Dummy head and tail nodes 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); // most recent end
    this.tail = new Node(0, 0); // least recent 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: Explicit O(1) for all operations. No reliance on language-specific map ordering. This is what Broadcom expects when they say 'implement this in C — how would you do it?' The doubly-linked list mirrors how kernel slab caches and ARP table LRU management actually works.

Broadcom-specific tips

At Broadcom, open with the design rationale: 'I need O(1) lookup — hash map. I need O(1) move-to-front and eviction — doubly-linked list. Combining them is the textbook LRU design, and it's exactly how ARP table management works in your switching ASIC control plane.' Broadcom interviewers for firmware roles often ask for the C equivalent — be ready to describe the linked-list pointer operations in terms of raw pointer arithmetic.

Common mistakes

  • Using a singly-linked list — you can't remove an arbitrary node in O(1) without a pointer to its predecessor.
  • Forgetting to delete the evicted node from the map — map and list fall out of sync.
  • Not moving the node to the front on a get() — a cache hit counts as a recent use.
  • Skipping dummy head/tail — every edge case (empty list, single node) requires special-casing.

Follow-up questions

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

  • LFU Cache (LC 460) — evict the least-frequently-used entry; requires frequency buckets.
  • How would you make this thread-safe for concurrent get/put calls?
  • How does LRU cache eviction policy compare to LFU and ARC in terms of hit-rate performance?

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?

To remove an arbitrary node in O(1) you need a pointer to its predecessor. Singly-linked lists require O(n) traversal to find it.

Why dummy head and tail?

They eliminate null-checks when inserting at the head or removing from the tail. Every pointer operation becomes uniform.

Is the JS Map approach acceptable at Broadcom?

Yes, as a starting point — but state explicitly that you're relying on ECMAScript-specified insertion order for Map. Then offer the DLL version, which is language-agnostic and closer to how it's implemented in C-based firmware.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →