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 Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

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).