Skip to main content

74. LRU Cache

mediumAsked at Plaid

Design an LRU cache with O(1) get and put. Plaid asks this because their idempotency-key store and recent-transactions cache both need O(1) bounded-memory LRU semantics.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II onsite — framed as idempotency-key store.
  • Blind (2026)— Plaid backend platform OA.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with int capacity, get(key) returns -1 if not present, and put(key, value) inserts or updates. Both operations 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)
Output
1, -1

Approaches

1. Map with timestamps + sort on eviction

Sort by last-access to find LRU.

Time
O(n log n) per put
Space
O(n)
// Sort on eviction. Misses O(1) requirement.

Tradeoff: Misses the O(1) requirement.

2. HashMap + Doubly Linked List

Map key -> node. Doubly linked list orders by recency. Get: move node to head. Put: insert at head; evict tail if over capacity. Or: use JS Map (insertion-ordered) and re-insert on access.

Time
O(1)
Space
O(capacity)
class LRUCache {
  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);
    this.map.set(key, value);
    if (this.map.size > this.cap) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

Tradeoff: JS Map preserves insertion order, so delete+set on access moves an entry to the back (most recent). The first entry is the LRU. Production version uses a HashMap + DLL to handle non-JS languages.

Plaid-specific tips

Plaid loves the JS-Map version because it's a clean way to demo the algorithm. For a non-JS language, ship the HashMap + DLL version explicitly. Bonus signal: mention that this is what they use internally for their idempotency-key store (TTL'd, bounded size).

Common mistakes

  • Forgetting to delete-then-set on get — leaves the entry in its old position.
  • Evicting before insertion — order matters.
  • Using a plain object (insertion order not guaranteed pre-ES2015 spec).

Follow-up questions

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

  • LFU cache (LC 460) — harder, two priority criteria.
  • TTL-aware LRU.
  • Multi-level LRU (L1 + L2 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 does delete + set move to back?

JS Map preserves insertion order. Deleting removes the old position; setting appends to the end (newest).

When is HashMap + DLL preferred?

In Java/Python where the standard Map doesn't preserve insertion order, or when you need explicit control over the linked list (e.g., for analytics on access patterns).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →