146. LRU Cache
mediumAsked at HPHP's firmware and print-spooler stacks manage limited on-device memory with LRU eviction policies for rendered page segments and font caches. LRU Cache is not just a puzzle — it mirrors a real design decision in HP hardware. Interviewers use it to test whether you can compose two data structures to satisfy a compound O(1) requirement.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in HP loops.
- Glassdoor (2026-Q1)— HP systems-software onsite reports consistently mention LRU Cache as a high-signal medium question across multiple rounds.
- Blind (2025-12)— HP senior SWE interview threads cite LRU Cache as a must-know design-coding hybrid for hardware-adjacent roles.
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 it exists, otherwise returns -1. void put(int key, int value) updates the value if the key exists, otherwise inserts the key-value pair. When the number of keys exceeds the capacity from this operation, 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), key 2 is evicted (LRU). After put(4,4), key 3 is evicted. get(2) returns -1 (evicted).
Approaches
1. Ordered Map (JS built-in)
JS Map preserves insertion order. On access, delete and re-insert to mark a key most-recent. On overflow, evict the first key (map.keys().next().value).
- Time
- O(1) 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: Pragmatic O(1) solution in JS. State that you rely on the ECMAScript insertion-order guarantee. Interviewers may ask for the explicit DLL version.
2. Hash map + doubly-linked list (canonical)
A Map provides O(1) key → node lookup. A doubly-linked list provides O(1) move-to-front and O(1) evict-from-tail. Dummy head and tail eliminate 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);
this.tail = new Node(0, 0);
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 with no language-specific ordering assumptions. HP systems interviewers expect this version to demonstrate understanding of the underlying data structure composition.
HP-specific tips
Before writing any code, state the design: 'I need O(1) lookup → hash map. I need O(1) move-to-front and eviction → doubly-linked list. Combining them gives the LRU cache.' HP values architectural explanation first. Dummy head/tail nodes are essential — without them every operation needs null-pointer guards. The node must store the key (not just the value) so you can remove it from the map on eviction.
Common mistakes
- Storing only value in the node — when you evict the tail, you need the key to remove it from the map.
- Using a singly-linked list — removal requires O(n) traversal to find the predecessor.
- Forgetting to update the map when evicting — the map and list must stay in sync.
- Not moving the node to the front on get() — a cache read counts as a recent use.
Follow-up questions
An interviewer at HP may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item using frequency buckets.
- How would you make this thread-safe for concurrent reads and writes?
- How would you persist the LRU cache to disk and restore it across process restarts?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly-linked, not singly-linked?
To remove an arbitrary node in O(1), you need O(1) access to its predecessor. A doubly-linked node holds that pointer; singly-linked requires O(n) traversal.
Why dummy head and tail?
They eliminate null-pointer checks on every insert/remove. Every operation becomes uniform pointer rewiring without special-casing empty list or single-element list.
Is the JS Map approach acceptable at HP?
Usually yes for web/backend roles. For systems or firmware roles, HP may specifically ask for the explicit DLL version to verify data-structure understanding.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other HP interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →