Skip to main content

22. LRU Cache

mediumAsked at ServiceNow

Design a data structure that supports O(1) get and put with least-recently-used eviction. ServiceNow asks this because their platform caches CMDB records and knowledge article lookups at high QPS, making LRU cache design directly applicable to real engineering work.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • LeetCode Discuss (2026)— Flagged as a ServiceNow SDE-II onsite data-structure design question.
  • Blind (2025)— Listed among top-5 ServiceNow engineering interview questions.

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 cache; get(key) returns the value if it exists and marks it recently used, otherwise -1; put(key, value) inserts or updates the value and marks it recently used. If at capacity, evict the least recently used item before inserting.

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 (least recently used). After put(4,4), key 1 is evicted.

Approaches

1. Map-based with manual key ordering

Use a JavaScript Map which preserves insertion order; on access, delete and re-insert to move to end. Evict the first key (oldest) when over capacity.

Time
O(1) amortized
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.cache = new Map(); // JS Map preserves insertion order
  }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // move to end
    return val;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.cap) {
      this.cache.delete(this.cache.keys().next().value); // evict oldest
    }
  }
}

Tradeoff: Elegant in JavaScript due to Map's insertion-order property, but not portable to languages without ordered maps. Interviewers may ask you to implement the doubly-linked list version to show you understand the underlying mechanics.

2. HashMap + doubly linked list

Maintain a doubly linked list from least-recently-used (head) to most-recently-used (tail), plus a Map from key to node. O(1) get moves the node to tail. O(1) put inserts at tail; eviction removes from head. Dummy head and tail nodes eliminate null checks.

Time
O(1) for get and put
Space
O(capacity)
class Node {
  constructor(k, v) { this.key=k; this.val=v; this.prev=null; this.next=null; }
}
class LRUCache {
  constructor(cap) {
    this.cap = cap;
    this.map = new Map();
    this.head = new Node(0,0); // dummy LRU end
    this.tail = new Node(0,0); // dummy MRU end
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertTail(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertTail(node);
    return node.val;
  }
  put(key, val) {
    if (this.map.has(key)) this._remove(this.map.get(key));
    const node = new Node(key, val);
    this._insertTail(node);
    this.map.set(key, node);
    if (this.map.size > this.cap) {
      const lru = this.head.next;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff: Language-agnostic, fully explicit O(1) operations. Dummy head/tail nodes are the key technique that eliminates five edge-case checks. This is the answer ServiceNow senior engineers expect.

ServiceNow-specific tips

ServiceNow interviewers specifically ask about the dummy node technique — it simplifies remove and insert to two pointer swaps each with no null checks. Describe the doubly linked list design before writing code, name the LRU and MRU ends explicitly, and explain why storing the node reference in the map (not just the key) is necessary for O(1) removal.

Common mistakes

  • Storing only the value in the map instead of the node pointer — makes removal O(n) because you can't locate the node in the list.
  • Forgetting to delete the evicted node from the map after removing it from the list — causes the map to grow without bound.
  • Inserting a new put at the head (LRU end) instead of the tail (MRU end) — reverses the eviction order.

Follow-up questions

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

  • LFU Cache: evict the least frequently used item (LC 460).
  • All O(1) data structure: insert, delete, and getRandom all in O(1) (LC 380).
  • Design a distributed LRU cache with multiple shards.

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 use dummy head and tail nodes?

Dummy nodes ensure the list always has at least two nodes, so insert and remove never need to check for null pointers at the ends. The code becomes two pointer swaps regardless of whether the list has 1 or 3000 real nodes.

Can I use a doubly-ended queue (deque) instead?

Yes, but a raw deque gives O(n) removal by value. The critical property is that the Map stores the node reference, enabling O(1) removal anywhere in the list.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →