Skip to main content

71. LRU Cache

mediumAsked at Datadog

Design a cache with get and put operations in O(1). Datadog asks this constantly — every metric ingestion pipeline has an LRU at some boundary for resolving high-cardinality tag IDs to interned values.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite design-warmup — graded on O(1) discipline.
  • Blind (2025-12)— Recurring at Datadog NYC.
  • LeetCode Discuss (2025-11)— Single most-asked Datadog onsite question.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with capacity, get(key), put(key, value). 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.

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]

Approaches

1. Ordered Map (JS Map preserves insertion order)

JS Map iterates in insertion order. On access, delete + re-insert.

Time
O(1) all ops
Space
O(capacity)
class LRUCache {
  constructor(capacity) { this.cap = capacity; this.m = new Map(); }
  get(key) {
    if (!this.m.has(key)) return -1;
    const v = this.m.get(key);
    this.m.delete(key);
    this.m.set(key, v);
    return v;
  }
  put(key, value) {
    if (this.m.has(key)) this.m.delete(key);
    this.m.set(key, value);
    if (this.m.size > this.cap) this.m.delete(this.m.keys().next().value);
  }
}

Tradeoff: Datadog accepts this in JS interviews but may push for the underlying data structure.

2. HashMap + Doubly Linked List (optimal — language-agnostic)

Map<key, node>. Node = { key, val, prev, next }. On access, move node to head. On eviction, drop tail.

Time
O(1) all ops
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;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _addFront(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._addFront(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._addFront(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._addFront(node);
  }
}

Tradeoff: True O(1). Datadog-canonical: the hash + DLL is what they actually use in their tag-cache layer.

Datadog-specific tips

Datadog grades on whether you can describe the hash + DLL even if you ship the Map version. The dummy head/tail nodes are critical — they remove all special cases for empty list, single node, head/tail position.

Common mistakes

  • Forgetting dummy head/tail — needs special cases for empty list operations.
  • Forgetting to update map on eviction — leaks memory and breaks future puts.
  • Storing only value in the node — when you evict the tail, you need its KEY to delete from the map.

Follow-up questions

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

  • LFU Cache (LC 460) — least frequently used.
  • TTL cache — eviction by age + access.
  • Datadog-style: high-cardinality tag-ID interning cache.

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 store key in the node?

On eviction, you remove the tail node and need to delete its key from the map. Without storing key, you couldn't.

Why doubly linked?

Singly linked can't remove a middle node in O(1) (need prev pointer). DLL gives O(1) splice.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →