146. LRU Cache
mediumAsked at AkamaiDesign a cache that evicts the least-recently-used entry when full. Akamai is one of the largest CDN operators in the world — LRU cache design is not an abstract exercise here, it is a direct description of the eviction policy running on thousands of edge servers handling billions of requests per day.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Akamai loops.
- Glassdoor (2026-Q1)— Multiple Akamai SWE interview reports cite LRU Cache as a defining question in onsite data structures rounds.
- Blind (2025-11)— Akamai threads note this is asked with special emphasis on O(1) complexity and the motivation from edge caching.
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 size 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 a new key-value pair. When the number of keys exceeds 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 get(1) promotes key 1, put(3,3) evicts key 2 (LRU). After put(4,4), key 1 is still recent (last get), key 3 is evicted.
Approaches
1. 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 (MRU side) and tail (LRU side) eliminate null-check 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.cap = capacity;
this.map = new Map();
this.head = new Node(0, 0); // dummy MRU sentinel
this.tail = new Node(0, 0); // dummy LRU sentinel
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.cap) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
}
}Tradeoff: True O(1) for all operations. The map and list must be kept in sync — every insert, delete, and move-to-front touches both. This is the answer Akamai expects; they will ask about the doubly-linked list structure explicitly.
2. Ordered Map shortcut (JavaScript-specific)
JavaScript's Map preserves insertion order. Delete and re-insert on access to simulate LRU ordering. Evict via map.keys().next().value (the oldest entry).
- Time
- O(1) amortized
- Space
- O(capacity)
class LRUCache {
constructor(capacity) {
this.cap = 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.cap) {
this.cache.delete(this.cache.keys().next().value);
}
}
}Tradeoff: Concise. Acceptable in JS-specific contexts, but note the reliance on language implementation. Akamai typically expects the explicit DLL solution to demonstrate data structure understanding.
Akamai-specific tips
Open with the business context: 'LRU eviction is the policy running on your edge servers right now. O(1) get and put at 10^9 requests/day means even a log(n) solution would add milliseconds of overhead.' Then justify the data structure composition: 'I need O(1) lookup — hash map. I need O(1) move-to-front and evict-from-tail — doubly-linked list. Combining them is the textbook LRU design.' Akamai engineers light up when candidates connect the algorithm to their actual infrastructure.
Common mistakes
- Using a singly-linked list — can't remove an arbitrary node in O(1) without a pointer to its predecessor.
- Forgetting to delete the evicted node from the map — the map and list fall out of sync.
- Not moving the accessed node to the front on get() — a cache hit counts as a recent use.
- Skipping dummy head/tail — every insert/remove then requires special-casing null neighbors.
Follow-up questions
An interviewer at Akamai may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used entry; requires frequency bucket tracking.
- How would you make this implementation thread-safe for concurrent reads and writes?
- How does the eviction policy change if you want Least Recently Used but with a TTL expiry per key?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly-linked and not singly-linked?
To remove an arbitrary node in O(1), you need a pointer to its predecessor. A singly-linked list requires O(n) traversal to find it.
Why dummy head and tail?
They eliminate null-checks for inserting at the head or removing from the tail. Every operation is uniform pointer rewiring — no branching for edge cases.
Does Akamai accept the JS Map shortcut?
Sometimes, but always state the JS-specific dependency and offer the DLL version. Akamai interviewers with C++ backgrounds will expect the explicit data structure.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Akamai interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →