Skip to main content

146. LRU Cache

mediumAsked at eBay

eBay's product catalog and search-result caching rely on LRU eviction to keep hot listings in memory while purging stale ones. This design problem tests whether you can compose a hash map and doubly-linked list to achieve O(1) get and put — a real production data structure that eBay's infrastructure engineering teams implement and discuss in depth.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Cited as a high-frequency eBay medium problem, especially for senior SWE and staff candidates, often used as a system-design bridge.
  • Blind (2025-12)— eBay SWE threads report LRU Cache as one of the most discussed medium problems, testing data structure composition under time pressure.

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 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 or 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 (LRU). After put(4,4), key 3 is evicted (LRU). get(2) returns -1 (evicted).

Approaches

1. Ordered Map (JS-idiomatic)

JavaScript's Map preserves insertion order. On get or put, delete and re-insert the key to move it to the 'most recent' end. Evict the first key (least recent) when over capacity.

Time
O(1) amortized
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) amortized. Relies on JS Map insertion-order guarantee. Concise but language-specific — eBay interviewers often want the explicit DLL version to verify structural understanding.

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

A Map gives O(1) key lookup; a doubly-linked list with dummy head/tail nodes gives O(1) move-to-front and evict-from-tail. The map stores key → node pointer.

Time
O(1) all operations
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); // dummy MRU sentinel
    this.tail = new Node(0, 0); // dummy LRU sentinel
    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. Interviewers at eBay expect this canonical version for senior-level discussions — it demonstrates you understand the underlying mechanics, not just language conveniences.

eBay-specific tips

State the data structure composition before writing any code: 'I need O(1) lookup — hash map. I need O(1) move-to-front and tail eviction — doubly-linked list. I'll wire them together.' eBay interviewers frame the follow-up around scale: 'How would this perform at 10 million product pages in memory?' The answer involves thread safety (synchronized blocks or concurrent data structures in Java), sharding, and TTL-based expiry on top of LRU eviction.

Common mistakes

  • Using a singly-linked list — removing an arbitrary node requires O(n) to find its predecessor.
  • Forgetting to delete the evicted node from the map — the map and list go out of sync.
  • Not moving the node to the front on a get() call — reading a key counts as a recent use.
  • Skipping dummy head/tail sentinel nodes — every pointer operation then requires null checks for the list boundaries.

Follow-up questions

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

  • LFU Cache (LC 460) — evict the least-frequently-used item; requires tracking frequency buckets and a doubly-nested structure.
  • How would you make this cache thread-safe for concurrent readers and writers?
  • How would you add TTL (time-to-live) expiry on top of LRU eviction?

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 and not singly-linked?

To remove an arbitrary node in O(1) you need a pointer to its predecessor. A singly-linked list requires O(n) traversal to find it; doubly-linked stores prev directly on every node.

Why dummy head and tail?

They eliminate null-pointer checks when inserting at the front or removing from the tail. Every operation becomes uniform pointer rewiring — no special cases.

Is the JS Map approach acceptable at eBay?

Yes for a phone screen, but eBay senior interviews expect you to offer the explicit DLL version and explain why: 'The Map approach relies on JS-specific insertion-order behavior that doesn't generalize to Java or C++, where you'd need the DLL explicitly.'

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →