146. LRU Cache
mediumAsked at ElasticDesign a cache that evicts the least-recently-used item when full. Elastic asks this because LRU is a first-class concern in search infrastructure — Elasticsearch's request cache and field data cache both use LRU eviction, and candidates who can implement it from scratch demonstrate exactly the systems intuition Elastic values.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Elastic loops.
- Glassdoor (2026-Q1)— LRU Cache listed as a high-signal medium question in multiple Elastic onsite reports — interviewers expect both the Map shortcut and the explicit DLL approach.
- Blind (2025-12)— Elastic SWE threads confirm LRU Cache appears frequently and interviewers probe the O(1) guarantee for both get and put.
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 a positive size capacity. int get(int key) returns the value of the key if the key exists, otherwise returns -1. void put(int key, int value) updates the value of the key if the key exists. Otherwise, adds the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.
Constraints
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^5At most 2 * 10^5 calls will be made to get and put.
Examples
Example 1
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)[null,null,null,1,null,-1,null,1,3,4]Explanation: After put(3,3) capacity is full and key 2 is evicted (LRU). get(2) returns -1. After put(4,4), key 3 is evicted (key 1 was recently accessed).
Approaches
1. JavaScript Map (insertion-order shortcut)
JS Map preserves insertion order. On get or put, delete and re-insert the key to move it to the 'most recent' end. Evict by deleting the first key in the Map (least recent).
- Time
- O(1) amortized get and put
- 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: Concise and correct in JS. Mention explicitly that you are relying on the ECMAScript Map insertion-order guarantee. Offer the DLL version if asked to avoid built-in ordered structures.
2. Hash map + doubly-linked list (canonical)
Map gives O(1) lookup by key; a doubly-linked list gives O(1) move-to-front and tail eviction. Dummy head and tail nodes simplify edge cases.
- Time
- O(1) get and put
- 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 most-recent
this.tail = new Node(0, 0); // dummy least-recent
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: Strictly O(1) for all operations with no language-specific guarantees. This is the expected canonical answer for Elastic's Java/Go-heavy engineering team.
Elastic-specific tips
Before writing code, state the composition: 'I need O(1) key lookup — hash map. I need O(1) move-to-front and tail eviction — doubly-linked list. These compose into the classic LRU design.' Elastic interviewers appreciate this architectural framing. Connect to the real system: 'Elasticsearch's request cache uses this pattern with a maximum byte size rather than item count — a natural follow-up question.' Use dummy head/tail to eliminate all edge-case checks.
Common mistakes
- Using a singly-linked list — removing an arbitrary node in O(1) requires knowing the predecessor.
- Not deleting the evicted node from the map — map and list must stay synchronized.
- Not moving the node to the front on a get — a cache hit counts as a recent use.
- Forgetting to store the key in each node — you need it to delete from the map during eviction.
Follow-up questions
An interviewer at Elastic may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item; requires frequency bucket tracking.
- How does Elasticsearch's field data cache use LRU eviction with a byte-size budget?
- How would you make this cache thread-safe for concurrent access?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly-linked, not singly-linked?
Removing an arbitrary node in O(1) requires a pointer to its predecessor. Singly-linked lists need O(n) traversal to find the predecessor.
Why do we store the key inside each DLL node?
During eviction, we remove the tail node from the list and must also delete it from the map. Without the key stored in the node, we cannot identify which map entry to delete.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Elastic interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →