146. LRU Cache
mediumAsked at Juniper NetworksDesign an O(1) LRU cache backed by a hash map and doubly-linked list. Juniper's Junos control plane caches route lookups and ARP entries with eviction policies — an LRU cache is a real data structure used in forwarding table management, making this a high-signal design-meets-coding problem.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Juniper Networks loops.
- Glassdoor (2026-Q1)— Cited in Juniper SWE onsite reports as a high-signal medium problem across routing and platform teams.
- Blind (2025-12)— Multiple Juniper threads list LRU Cache as the most common medium design-coding hybrid at Juniper.
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 if the key exists, or 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 (LRU) is evicted. After put(4,4), key 3 (LRU — key 1 was recently accessed) is evicted.
Approaches
1. JavaScript Map (insertion-order LRU)
JS Map preserves insertion order. On access, delete and re-insert to move the key to the 'most recent' position. Evict by deleting the first key (the map's oldest entry).
- Time
- O(1) amortized
- 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: O(1) amortized. Relies on JS Map's insertion-order guarantee. A valid practical answer; Juniper may ask for the explicit DLL version to test data structure knowledge.
2. Hash map + doubly-linked list (canonical)
HashMap for O(1) key lookup. Doubly-linked list for O(1) move-to-front (most recent) and evict-from-tail (least recent). 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); // MRU sentinel
this.tail = new Node(0, 0); // 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.capacity) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
}
}Tradeoff: True O(1) for all operations with no language-specific assumptions. The canonical answer Juniper's hardware and systems teams expect.
Juniper Networks-specific tips
Explain the data structure composition before writing code: 'I need O(1) lookup — hash map. I need O(1) recency-based reorder and eviction — doubly-linked list. Combined they give me O(1) for both get and put.' Juniper values structured reasoning. Mention that in Junos, ARP/ND caches and route-lookup caches use bounded-size LRU eviction — this problem is not abstract. Use dummy head/tail to eliminate edge cases.
Common mistakes
- Using a singly-linked list — you cannot remove an arbitrary node in O(1) without a pointer to its predecessor.
- Forgetting to delete the evicted node from the hash map — the map and list fall out of sync.
- Not moving the node to front on a get() — a cache hit counts as most-recently used.
- Forgetting to store the key in each node — you need it to delete from the map on eviction.
Follow-up questions
An interviewer at Juniper Networks may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently used; requires frequency bucket tracking.
- How would you make this thread-safe in a multi-threaded control-plane process?
- Design a TTL-based cache where entries expire after a fixed time.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly-linked list over singly-linked?
Removing an arbitrary node in O(1) requires a pointer to its predecessor. A singly-linked list needs O(n) to find the predecessor.
Why store the key inside the node?
When evicting the LRU node (tail.prev), you need to remove its key from the hash map. Without storing the key, you cannot do this in O(1).
Why use dummy head and tail?
They eliminate null-pointer checks for inserting at head and removing from tail. Every insert and remove becomes uniform pointer rewiring.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Juniper Networks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →