Skip to main content

146. LRU Cache

mediumAsked at Twilio

LRU Cache is Twilio's premier system-design coding probe: implement get and put in O(1), with eviction of the least-recently-used entry when capacity is exceeded. Twilio's rate-limiter and rolling-window code paths use this exact data structure, and the interview rubric grades whether you reach for a hash map plus doubly-linked list without prompting.

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Heavily-reported as Twilio's signature data-structure design question across SWE-2 and SWE-3 on-sites.
  • LeetCode Discuss (2025-12)— Recurring in Twilio platform-team and SDK-engineering interview reports.

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 it exists, otherwise returns -1. void put(int key, int value) updates the value if the key exists, or adds the key-value pair to the cache. If the number of keys exceeds capacity, evict the least recently used key. 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 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: Evict 2 on put(3,3) and 1 on put(4,4).

Approaches

1. Array of [key,value] + linear scan (rejected)

Store entries in an array; on get/put, scan linearly to find the entry.

Time
O(n) per op
Space
O(n)
class LRUCacheBrute {
  constructor(capacity) {
    this.cap = capacity;
    this.data = [];
  }
  get(key) {
    const idx = this.data.findIndex(e => e[0] === key);
    if (idx === -1) return -1;
    const entry = this.data.splice(idx, 1)[0];
    this.data.push(entry);
    return entry[1];
  }
  put(key, value) {
    const idx = this.data.findIndex(e => e[0] === key);
    if (idx !== -1) this.data.splice(idx, 1);
    else if (this.data.length >= this.cap) this.data.shift();
    this.data.push([key, value]);
  }
}

Tradeoff: Correct but every operation is O(n) — fails the explicit O(1) requirement. Twilio reviewers reject this on the rubric the moment you finish writing it.

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

Hash map keys to list nodes. On access, splice the node out and re-attach at the head (most recent). On overflow, remove the tail.

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

Tradeoff: Two sentinel nodes (head/tail) eliminate all null-edge cases for splice operations. The Map gives O(1) lookup; the doubly-linked list gives O(1) reorder and tail-eviction. Storing key on the node is necessary so eviction can clean up the Map.

3. JS Map insertion-order trick (concise alternative)

Use JavaScript's Map, which preserves insertion order. On access, delete and re-insert to refresh.

Time
O(1) per op (engine-dependent)
Space
O(capacity)
class LRUCacheMap {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, v);
    return v;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.cap) this.map.delete(this.map.keys().next().value);
    this.map.set(key, value);
  }
}

Tradeoff: Cleaner and faster to write in an interview. Acceptable at Twilio if the candidate also explains the underlying hash-map-plus-DLL design — interviewers want to know you understand the data structure, not just the language feature. State 'JS Map preserves insertion order and supports O(1) delete-then-set' before writing it.

Twilio-specific tips

LRU Cache is Twilio's most-asked design question. The bar is the O(1) requirement: be explicit that any O(n) operation per call disqualifies the design. Mention that this exact data structure backs production rate-limit caches at messaging companies (token-bucket with LRU eviction of inactive accounts). If the interviewer asks for a thread-safe variant, mention a single coarse mutex around get/put or a lock-free CAS-based skiplist depending on the read/write ratio.

Common mistakes

  • Singly-linked list instead of doubly — you can't splice in O(1) without a back-pointer.
  • Missing sentinel nodes — leads to null-check branching all over the splice methods.
  • Forgetting to clean up the Map entry on eviction — keys leak and memory grows past capacity.
  • Updating value in put() but not refreshing the recency — the entry gets evicted too early.

Follow-up questions

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

  • How would you make this thread-safe? (Coarse mutex around get/put; or partition keys across N shards each with its own LRU.)
  • How would you adapt it to LFU (Least Frequently Used)? (LC 460 — two hash maps + a min-frequency tracker.)
  • What if the values were large blobs and you wanted to bound by total BYTES, not entry count? (Same skeleton, replace `size >= cap` with `bytes + entry.size > maxBytes`.)
  • How would you support TTL expiration? (Add an expireAt timestamp per node; evict lazily on get() or via a background sweep.)

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 instead of singly-linked?

Because O(1) reorder requires removing a node from anywhere in the list, which requires the prev pointer. With a singly-linked list, removing requires walking to find the predecessor, which is O(n).

Why store the key on the node?

Because eviction starts from the tail (the node), but you need to remove the corresponding entry from the hash map — and the only way to find that entry is by its key. Without storing the key, eviction needs an inverse-lookup which kills the O(1) guarantee.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →