146. LRU Cache
mediumAsked at AtlassianLRU Cache is Atlassian's classic OOP-and-data-structure design problem. Design a fixed-capacity cache that evicts the least-recently-used key on overflow with O(1) get and put. Atlassian asks it to test whether you can combine a doubly-linked list with a hash map without dropping pointer invariants under pressure.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Atlassian loops.
- Glassdoor (2026-Q1)— Atlassian SWE-II / Senior onsite reports cite LRU Cache as a recurring data-structure-design problem, often as the second technical round.
- Blind (2025-10)— Multiple Atlassian onsite threads list LRU Cache (sometimes with a TTL twist) as a favorite design question.
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int 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 of the key if it exists; otherwise adds the key-value pair to the cache. If inserting causes the number of keys to exceed capacity, evict the least recently used key. Both get and put must run in O(1) average time.
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]Approaches
1. JavaScript Map (insertion-ordered, concise)
JS Map preserves insertion order. Delete + re-insert on access to refresh recency; map.keys().next().value is the LRU.
- Time
- O(1) average
- Space
- O(capacity)
class LRUCacheMap {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
}
get(key) {
if (!this.map.has(key)) return -1;
const val = this.map.get(key);
this.map.delete(key);
this.map.set(key, val);
return val;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size >= this.capacity) {
this.map.delete(this.map.keys().next().value);
}
this.map.set(key, value);
}
}Tradeoff: Idiomatic JS, ~25 lines, and uses a language feature most candidates don't know exists. Many Atlassian interviewers accept it AS LONG AS you also describe the doubly-linked-list version when asked 'what would you do in Java?'.
2. Doubly linked list + hash map (canonical)
Map from key → DLL node. Doubly linked list with sentinel head and tail; head.next is MRU, tail.prev is LRU. Move-to-front on get/put; evict from tail.prev.
- Time
- O(1) worst-case
- Space
- O(capacity)
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
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;
}
_addToFront(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._addToFront(node);
return node.value;
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this._remove(node);
this._addToFront(node);
return;
}
if (this.map.size >= this.capacity) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
const node = new Node(key, value);
this._addToFront(node);
this.map.set(key, node);
}
}Tradeoff: True O(1) worst case (Map insertion is amortized O(1) but the eviction step is genuinely constant — no rehash bursts dragging in extra cost). Atlassian interviewers want to see this version because it generalizes cleanly to LFU and TTL variants in follow-ups.
Atlassian-specific tips
Atlassian almost always follows LRU with one of: 'now add a 60-second TTL', 'now make it thread-safe', or 'now make it LFU (least frequently used)'. Sketch the API and class fields on the board before writing methods — Atlassian interviewers value upfront design narration. Use sentinel head/tail nodes; not using sentinels is the #1 cause of NullPointer-equivalent bugs candidates ship in the heat of the moment.
Common mistakes
- Forgetting to update the hash map when you evict the tail — the map and the list drift out of sync, and the next put for that key inserts a duplicate.
- Trying to implement DLL without sentinel head and tail — every move-to-front becomes a conditional and you double the code length.
- On the Map-based solution, calling this.map.keys().next() instead of this.map.keys().next().value — eviction silently deletes nothing.
Follow-up questions
An interviewer at Atlassian may pivot to one of these next:
- LFU Cache (LeetCode 460) — replace MRU/LRU with frequency buckets.
- Add a TTL per key — store an expiry timestamp on the node and check it in get; lazily evict expired entries.
- Make it concurrent — what data races appear when two threads both call get on the same hot key?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Is the Map solution accepted at Atlassian?
Usually yes for SWE-I / SWE-II, but expect to be asked 'walk me through the DLL version anyway' as a follow-up. For Senior+ the DLL version is the expected starting point; the Map answer reads as evading the data-structure question.
Why doubly linked list and not singly linked?
You need to remove a node in O(1) given a reference to it (from the hash map). Singly linked requires walking from the head to find the predecessor, which kills the O(1) target.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Atlassian interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →