146. LRU Cache
mediumAsked at AndurilDesign a Least Recently Used cache with O(1) get and put. Anduril frequently asks this because caching is a building block of real-time command pipelines — you need to compose a hash map and a doubly-linked list correctly and articulate why both structures are necessary.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Anduril loops.
- Glassdoor (2026-Q1)— Listed in Anduril SWE onsite threads as a design-heavy coding question testing data-structure composition.
- Blind (2025-11)— Anduril candidates report LRU Cache as a high-signal medium spanning multiple interview rounds for systems-focused 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 positive capacity. int get(int key) returns the value of the key if it exists, otherwise -1. void put(int key, int value) updates the value if the key exists, or inserts the key-value pair. When 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), key 2 is evicted. After put(4,4), key 3 is evicted (key 1 was recently accessed). get(2) returns -1.
Approaches
1. Ordered Map (JS Map insertion order)
Use JavaScript's Map which preserves insertion order. On access, delete and re-insert to promote the key to most-recent. Evict by deleting the first key.
- 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: Elegant for JS, but relies on language-specific Map insertion-order semantics. State this dependency explicitly. Anduril engineers will often ask for the explicit doubly-linked-list version.
2. Hash map + doubly-linked list (canonical)
A Map gives O(1) key lookup; a doubly-linked list gives O(1) move-to-front and evict-from-tail. Dummy head and tail nodes 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. Dummy head/tail eliminate null checks. This is the canonical answer Anduril systems engineers expect when they say 'don't use JS Map ordering.'
Anduril-specific tips
Begin by explaining the data structure composition: 'I need O(1) lookup — hash map. I need O(1) move-to-front and eviction — doubly-linked list with dummy nodes. Combining them gives the canonical LRU design.' Anduril places high value on this kind of reasoning before you write any code. For embedded systems context, mention that this same structure powers instruction caches and TLB eviction policies in real hardware.
Common mistakes
- Using a singly-linked list — you can't remove an arbitrary node in O(1) without a pointer to its predecessor.
- Forgetting to delete the evicted node from the map — map and list must stay in sync at all times.
- Not moving the node to the front on a get() call — a cache hit counts as a recent use.
- Skipping dummy head/tail — every insert/remove then requires special-casing the empty list.
Follow-up questions
An interviewer at Anduril may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item; requires tracking frequency buckets.
- How would you implement this in a thread-safe manner for a multi-core system?
- How would you shard an LRU cache across multiple processes to support higher throughput?
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 require O(n) traversal to find it.
Why dummy head and tail?
They eliminate null-checks at the list boundaries. Every insert and remove becomes uniform pointer rewiring — no special cases for the first or last node.
Is the JS Map approach acceptable at Anduril?
Yes, but state the dependency on insertion-order semantics (per ECMAScript spec) and offer to implement the explicit DLL version if they prefer the language-agnostic solution.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Anduril interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →