Skip to main content

146. LRU Cache

mediumAsked at Cohere

Design a cache that evicts the least-recently-used entry when full. Cohere asks this because LRU caching is a first-class concern in embedding serving — caching recently-requested embedding vectors avoids redundant inference and reduces GPU cost at scale.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Cohere SWE and MLE onsite reports consistently cite LRU Cache as a high-signal design-plus-coding question.
  • Blind (2025-12)— Multiple Cohere threads identify LRU Cache as a must-practise problem for engineering roles at the company.

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 the key 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.

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 is evicted; after put(4,4) key 3 is evicted because it was least recently used after get(1) refreshed key 1.

Approaches

1. Ordered Map (JS-idiomatic)

Use JavaScript's Map which preserves insertion order. On access, delete and re-insert to make the key most recent. Evict the first key (least recent) when capacity is exceeded.

Time
O(1) amortised 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: Clean and concise in JS. Relies on the ECMAScript Map insertion-order guarantee. State this assumption explicitly.

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

A Map provides O(1) key lookup. A doubly-linked list provides O(1) node removal and front insertion. The map stores key → node so get can locate and reposition the node instantly.

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.cap = capacity;
    this.map = new Map();
    this.head = new Node(0, 0); // dummy MRU end
    this.tail = new Node(0, 0); // dummy LRU 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.cap) {
      const lru = this.tail.prev;
      this._remove(lru); this.map.delete(lru.key);
    }
  }
}

Tradeoff: Explicit O(1) without relying on language-specific Map ordering. The expected answer when Cohere says 'implement this from scratch.'

Cohere-specific tips

Cohere's embedding APIs cache recently-computed vectors to avoid redundant GPU inference. Frame your answer in this context: 'In an embedding serving system I would cache (text_hash → embedding_vector) with LRU eviction — get() on a cache hit returns the vector and refreshes its position; put() on a cache miss stores the freshly-computed vector and evicts the stale LRU entry.' Cohere interviewers respond strongly to candidates who ground algorithmic choices in ML-system design.

Common mistakes

  • Using a singly-linked list — O(n) to remove an arbitrary node without a prev pointer.
  • Forgetting to delete the evicted node from the Map — the map and list must stay in sync.
  • Not moving the node to the front on get() — a cache hit counts as a recent use.
  • Skipping dummy head/tail nodes — every insert/remove then needs special-casing for boundary conditions.

Follow-up questions

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

  • LFU Cache (LC 460) — evict the least-frequently-used entry; requires tracking frequency buckets.
  • Thread-safe LRU cache — discuss read-write locks and concurrent access patterns.
  • How would you shard an LRU cache across multiple servers for a distributed embedding store?

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 rather than singly-linked?

Removing an arbitrary node requires a pointer to its predecessor. A singly-linked list needs O(n) traversal to find it; a doubly-linked list provides the prev pointer directly.

Why dummy head and tail?

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

Is the JS Map approach acceptable at Cohere?

Yes — but state explicitly that you are relying on ECMAScript Map insertion-order guarantees, then offer to implement the explicit doubly-linked-list version if required.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →