Skip to main content

68. LRU Cache

mediumAsked at Salesforce

Design a Least-Recently-Used cache with O(1) get and put. Salesforce uses this as the canonical data-structure-design problem — they use LRU eviction in their platform cache layer.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses LRU in their platform cache and SOQL query plan cache.
  • Blind (2025-12)— Salesforce L5 onsite favorite.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity), int get(int key), void put(int key, int value). Both get and put must run in O(1) average time complexity.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • At most 2 * 10^5 calls will be made to get and put.

Examples

Example 1

Input
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,null,-1,3,4]

Approaches

1. Sorted by timestamp

Map + timestamp; on get, update timestamp; on eviction, find min timestamp.

Time
O(n) for eviction
Space
O(n)
// Skipped — O(n) eviction fails the O(1) requirement.

Tradeoff: Linear eviction violates the constraint.

2. Hash map + doubly linked list

Map: key -> node. DLL: most-recent at head. On get/put, move node to head. On overflow, evict tail.

Time
O(1)
Space
O(n)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map(); // Map preserves insertion order in JS
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.cap) this.map.delete(this.map.keys().next().value);
    this.map.set(key, value);
  }
}

Tradeoff: JavaScript Map preserves insertion order, giving a built-in LRU. Cleanest code possible. For other languages, hand-roll the DLL.

Salesforce-specific tips

Salesforce uses LRU heavily — platform cache, SOQL query plan cache, AppExchange package metadata. They specifically grade on whether you reach for the hashmap-plus-DLL combo (or in JS, exploit the Map insertion-order property). Bonus signal: discuss the trade-offs vs LFU (LC 460) — LFU adds frequency tracking.

Common mistakes

  • Implementing only a Map without re-inserting on get — fails to update LRU order.
  • Using a queue instead of a DLL — O(n) to move a node to the front.
  • Forgetting to delete-then-set in JS Map — set on an existing key doesn't change order.

Follow-up questions

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

  • LFU Cache (LC 460).
  • Design In-Memory File System (LC 588).
  • Generalize to TTL-based 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 does delete-then-set work for LRU order?

JavaScript Map preserves insertion order. Delete removes the key; set inserts it at the end. After this, the oldest key is at the start, which is what we want for eviction.

What if we need thread safety?

Wrap operations in a lock (mutex). Salesforce production caches use this pattern; ConcurrentHashMap + LinkedList with synchronization.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →