LRU Cache

🎯

LRU Cache

mediumDESIGNAmazonFacebookGoogle

Imagine you are designing a web browser cache that must quickly retrieve recently visited pages and discard the least recently used ones when full.

💡 This problem is about designing a data structure that supports fast access and eviction based on recent usage. Beginners often struggle because it requires combining multiple data structures to achieve O(1) operations.

📋

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with the following methods: - LRUCache(int capacity): Initialize the cache with positive size capacity. - int get(int key): Return the value of the key if it exists, otherwise return -1. - void put(int key, int value): Update or insert the value if the key is not present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. Both get and put operations must run in O(1) time complexity.

1 ≤ capacity ≤ 10^50 ≤ key, value ≤ 10^9At most 2 * 10^5 calls will be made to get and put

💡

Example

Input"LRUCache cache = new LRUCache(2);\ncache.put(1, 1);\ncache.put(2, 2);\ncache.get(1);\ncache.put(3, 3);\ncache.get(2);\ncache.put(4, 4);\ncache.get(1);\ncache.get(3);\ncache.get(4);"

Output[null, null, null, 1, null, -1, null, 3, 4]

Cache capacity is 2. After putting keys 1 and 2, get(1) returns 1 and makes key 1 most recently used. Putting key 3 evicts key 2. get(2) returns -1 because key 2 was evicted. Putting key 4 evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.

• Capacity = 1, multiple puts and gets → should evict immediately
• Get a key that was never added → returns -1
• Put the same key multiple times → updates value and usage order
• Put keys until capacity, then put one more → evicts least recently used

⚠️

Common Mistakes

Using a list for usage order without efficient removal

Leads to O(n) operations causing timeouts

✅ Use a doubly linked list or ordered dictionary for O(1) removals

Not updating usage order on get operations

Cache evicts wrong keys, causing incorrect results

✅ Always move accessed keys to most recently used position

Evicting the wrong key when capacity exceeded

Removes recently used keys instead of least recently used

✅ Evict the tail node in doubly linked list or first item in ordered dictionary

Not handling capacity = 0 or edge cases

Code may crash or behave unexpectedly

✅ Add checks for capacity and handle edge cases explicitly

Memory leaks in languages like C++ by not deleting nodes

Leads to memory exhaustion in long runs

✅ Properly delete nodes when removing from list and map

🧠

Brute Force (Using List for Cache Order)

💡 This approach helps understand the problem by simulating the cache behavior directly, but it is inefficient. It lays the foundation for why we need better data structures.

Intuition

Maintain a list of keys in order of usage. On get or put, move the key to the end to mark it as recently used. On capacity overflow, remove the first key (least recently used).

Algorithm

1. Initialize an empty list to store keys in usage order and a dictionary for key-value pairs.
2. For get(key), check if key exists; if yes, move it to the end of the list and return its value; else return -1.
3. For put(key, value), if key exists, update value and move key to end; else add key-value and append key to list.
4. If capacity exceeded, remove the first key from the list and delete it from the dictionary.

💡 The challenge is to keep track of usage order and update it on every access, which is easy conceptually but inefficient to implement with a list.

</>

Code

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.usage = []

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.usage.remove(key)  # O(n) operation
        self.usage.append(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.usage.remove(key)  # O(n) operation
            self.usage.append(key)
        else:
            if len(self.cache) == self.capacity:
                lru = self.usage.pop(0)  # O(n) operation
                del self.cache[lru]
            self.cache[key] = value
            self.usage.append(key)

# Driver code
if __name__ == '__main__':
    cache = LRUCache(2)
    print(cache.put(1, 1))  # None
    print(cache.put(2, 2))  # None
    print(cache.get(1))     # 1
    print(cache.put(3, 3))  # None
    print(cache.get(2))     # -1
    print(cache.put(4, 4))  # None
    print(cache.get(1))     # -1
    print(cache.get(3))     # 3
    print(cache.get(4))     # 4

Line Notes

self.capacity = capacityStore the maximum number of items the cache can hold to enforce capacity limit

self.cache = {}Dictionary to store key-value pairs for O(1) access to values

self.usage = []List to track usage order; front is least recently used, back is most recently used

if key not in self.cache:Check if key exists to decide whether to return value or -1

self.usage.remove(key)Remove key from usage list to update its position; this is an O(n) operation and inefficient

self.usage.append(key)Append key to mark it as most recently used (at the end of the list)

if len(self.cache) == self.capacity:Check if cache is full before inserting new key to decide if eviction is needed

lru = self.usage.pop(0)Remove least recently used key from front of usage list; also O(n) due to list shift

import java.util.*;

class LRUCache {
    private int capacity;
    private Map<Integer, Integer> cache;
    private List<Integer> usage;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.usage = new ArrayList<>();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        usage.remove((Integer) key); // O(n) operation
        usage.add(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.put(key, value);
            usage.remove((Integer) key); // O(n) operation
            usage.add(key);
        } else {
            if (cache.size() == capacity) {
                int lru = usage.remove(0); // O(n) operation
                cache.remove(lru);
            }
            cache.put(key, value);
            usage.add(key);
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
        cache.put(4, 4);
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
        System.out.println(cache.get(4)); // 4
    }
}

Line Notes

private int capacity;Store maximum cache size to enforce capacity limit

private Map<Integer, Integer> cache;HashMap for key-value storage with O(1) access

private List<Integer> usage;ArrayList to track usage order; front is least recently used

if (!cache.containsKey(key)) return -1;Return -1 if key not found in cache

usage.remove((Integer) key);Remove key from usage list to update position; costly O(n) operation

usage.add(key);Add key to end to mark as most recently used

if (cache.size() == capacity)Check if cache is full before insertion to decide eviction

int lru = usage.remove(0);Remove least recently used key from front of usage list

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class LRUCache {
    int capacity;
    unordered_map<int, int> cache;
    vector<int> usage;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        auto it = find(usage.begin(), usage.end(), key); // O(n)
        usage.erase(it);
        usage.push_back(key);
        return cache[key];
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            cache[key] = value;
            auto it = find(usage.begin(), usage.end(), key); // O(n)
            usage.erase(it);
            usage.push_back(key);
        } else {
            if ((int)cache.size() == capacity) {
                int lru = usage.front();
                usage.erase(usage.begin());
                cache.erase(lru);
            }
            cache[key] = value;
            usage.push_back(key);
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << "\n"; // 1
    cache.put(3, 3);
    cout << cache.get(2) << "\n"; // -1
    cache.put(4, 4);
    cout << cache.get(1) << "\n"; // -1
    cout << cache.get(3) << "\n"; // 3
    cout << cache.get(4) << "\n"; // 4
    return 0;
}

Line Notes

int capacity;Store max cache size to enforce capacity limit

unordered_map<int, int> cache;Hash map for key-value pairs with O(1) access

vector<int> usage;Vector to track usage order; front is least recently used

if (cache.find(key) == cache.end()) return -1;Return -1 if key not found in cache

auto it = find(usage.begin(), usage.end(), key);Find key position in usage vector; costly O(n) operation

usage.erase(it);Remove key from usage vector to update position

if ((int)cache.size() == capacity)Check if cache is full before insertion to decide eviction

usage.erase(usage.begin());Remove least recently used key from front of usage vector

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.usage = [];
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const index = this.usage.indexOf(key); // O(n)
        this.usage.splice(index, 1);
        this.usage.push(key);
        return this.cache.get(key);
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.set(key, value);
            const index = this.usage.indexOf(key); // O(n)
            this.usage.splice(index, 1);
            this.usage.push(key);
        } else {
            if (this.cache.size === this.capacity) {
                const lru = this.usage.shift();
                this.cache.delete(lru);
            }
            this.cache.set(key, value);
            this.usage.push(key);
        }
    }
}

// Driver code
const cache = new LRUCache(2);
console.log(cache.put(1, 1)); // undefined
console.log(cache.put(2, 2)); // undefined
console.log(cache.get(1));    // 1
console.log(cache.put(3, 3)); // undefined
console.log(cache.get(2));    // -1
console.log(cache.put(4, 4)); // undefined
console.log(cache.get(1));    // -1
console.log(cache.get(3));    // 3
console.log(cache.get(4));    // 4

Line Notes

this.capacity = capacity;Store max cache size to enforce capacity limit

this.cache = new Map();Map for key-value storage with O(1) access

this.usage = [];Array to track usage order; front is least recently used

if (!this.cache.has(key)) return -1;Return -1 if key not found in cache

const index = this.usage.indexOf(key);Find key index in usage array; costly O(n) operation

this.usage.splice(index, 1);Remove key from usage array to update position

if (this.cache.size === this.capacity)Check if cache is full before insertion to decide eviction

const lru = this.usage.shift();Remove least recently used key from front of usage array

⏱

Complexity

TimeO(n) per get/put due to list removal and search

SpaceO(capacity) for storing keys and values

Each get or put requires searching and removing keys from a list, which is O(n). For large n, this is inefficient.

💡 For capacity=1000, each get/put might do up to 1000 operations, which is slow for many calls.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but is useful to understand the problem and why we need better data structures.

🧠

Better Approach (OrderedDict / LinkedHashMap)

💡 This approach uses built-in ordered dictionary data structures that maintain insertion order and allow O(1) deletion and insertion, improving efficiency.

Intuition

Use an ordered dictionary that keeps track of the order keys were accessed. On get or put, move the key to the end to mark it as recently used. Evict from the front when capacity is exceeded.

Algorithm

1. Initialize an ordered dictionary to store key-value pairs.
2. For get(key), if key exists, move it to the end and return value; else return -1.
3. For put(key, value), if key exists, update value and move to end; else add key-value to end.
4. If capacity exceeded, remove the first key in the ordered dictionary.

💡 The key insight is that ordered dictionaries maintain order and allow moving keys to the end in O(1), avoiding costly list operations.

</>

Code

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark as recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # remove least recently used

# Driver code
if __name__ == '__main__':
    cache = LRUCache(2)
    print(cache.put(1, 1))
    print(cache.put(2, 2))
    print(cache.get(1))
    print(cache.put(3, 3))
    print(cache.get(2))
    print(cache.put(4, 4))
    print(cache.get(1))
    print(cache.get(3))
    print(cache.get(4))

Line Notes

from collections import OrderedDictImport ordered dictionary that maintains insertion order and supports efficient reordering

self.cache = OrderedDict()Initialize ordered dictionary for cache storage with order tracking

self.cache.move_to_end(key)Move accessed key to end to mark it as most recently used in O(1)

self.cache.popitem(last=False)Remove first item (least recently used) when capacity exceeded in O(1)

import java.util.*;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
        cache.put(4, 4);
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
        System.out.println(cache.get(4)); // 4
    }
}

Line Notes

extends LinkedHashMap<Integer, Integer>Use LinkedHashMap to maintain access order automatically

super(capacity, 0.75f, true);Enable access order to reorder entries on get/put operations

protected boolean removeEldestEntryAutomatically remove eldest entry when size exceeds capacity

return super.getOrDefault(key, -1);Return value if key exists, else -1

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache {
    int capacity;
    list<pair<int, int>> cacheList; // stores (key, value)
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) return -1;
        cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        return cacheMap[key]->second;
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            cacheMap[key]->second = value;
            return;
        }
        if ((int)cacheList.size() == capacity) {
            int lruKey = cacheList.back().first;
            cacheList.pop_back();
            cacheMap.erase(lruKey);
        }
        cacheList.emplace_front(key, value);
        cacheMap[key] = cacheList.begin();
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << "\n"; // 1
    cache.put(3, 3);
    cout << cache.get(2) << "\n"; // -1
    cache.put(4, 4);
    cout << cache.get(1) << "\n"; // -1
    cout << cache.get(3) << "\n"; // 3
    cout << cache.get(4) << "\n"; // 4
    return 0;
}

Line Notes

list<pair<int, int>> cacheList;Doubly linked list to store keys and values in usage order for O(1) insert and remove

unordered_map<int, list<pair<int, int>>::iterator> cacheMap;Map keys to list iterators for O(1) access to nodes

cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);Move accessed node to front to mark as most recently used in O(1)

cacheList.emplace_front(key, value);Insert new key-value pair at front of list

cacheList.pop_back();Remove least recently used item from back of list

cacheMap.erase(lruKey);Remove evicted key from map

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const value = this.cache.get(key);
        this.cache.delete(key); // remove and re-insert to update order
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size === this.capacity) {
            const lruKey = this.cache.keys().next().value;
            this.cache.delete(lruKey);
        }
        this.cache.set(key, value);
    }
}

// Driver code
const cache = new LRUCache(2);
console.log(cache.put(1, 1));
console.log(cache.put(2, 2));
console.log(cache.get(1));
console.log(cache.put(3, 3));
console.log(cache.get(2));
console.log(cache.put(4, 4));
console.log(cache.get(1));
console.log(cache.get(3));
console.log(cache.get(4));

Line Notes

this.cache = new Map();Use Map which preserves insertion order and supports O(1) operations

this.cache.delete(key);Remove key to update its position on re-insertion, marking it as recently used

this.cache.set(key, value);Insert key-value pair at end to mark as most recently used

const lruKey = this.cache.keys().next().value;Get least recently used key (first inserted) in O(1)

this.cache.delete(lruKey);Remove least recently used key when capacity exceeded

⏱

Complexity

TimeO(1) average for get and put

SpaceO(capacity) for storing keys and values

Using ordered dictionaries or linked hash maps allows constant time updates and evictions by maintaining order internally.

💡 For capacity=1000, each operation takes constant time, making it efficient for large inputs.

Interview Verdict: Accepted / Efficient for large inputs

This approach is practical and accepted in interviews, leveraging built-in data structures for simplicity and efficiency.

🧠

Optimal Approach (Custom Doubly Linked List + Hash Map)

💡 This approach implements the LRU cache from scratch using a doubly linked list and a hash map to achieve O(1) operations without relying on built-in ordered dictionaries.

Intuition

Use a doubly linked list to maintain usage order and a hash map to access nodes in O(1). On get or put, move the node to the front. Evict from the tail when capacity is exceeded.

Algorithm

1. Create a doubly linked list with dummy head and tail nodes to simplify edge cases.
2. Maintain a hash map from keys to nodes in the list.
3. For get(key), if key exists, move the node to the front and return its value; else return -1.
4. For put(key, value), if key exists, update value and move node to front; else create new node at front.
5. If capacity exceeded, remove node from tail and delete from hash map.

💡 The doubly linked list allows O(1) removal and insertion of nodes, and the hash map provides O(1) access to nodes by key.

</>

Code

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev

    def _add(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

# Driver code
if __name__ == '__main__':
    cache = LRUCache(2)
    print(cache.put(1, 1))
    print(cache.put(2, 2))
    print(cache.get(1))
    print(cache.put(3, 3))
    print(cache.get(2))
    print(cache.put(4, 4))
    print(cache.get(1))
    print(cache.get(3))
    print(cache.get(4))

Line Notes

class Node:Define node structure for doubly linked list with key, value, and pointers

self.head = Node()Dummy head node to simplify insertions at front

self.tail = Node()Dummy tail node to simplify removals at end

def _remove(self, node):Helper to unlink a node from the list in O(1) time

def _add(self, node):Helper to insert a node right after head (most recent position)

if key not in self.cache:Check if key exists for get operation to return -1 if missing

self._remove(node)Remove node before re-adding to update usage order

if len(self.cache) > self.capacity:Evict least recently used node when capacity exceeded

import java.util.*;

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private int capacity;
    private Map<Integer, Node> cache;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void add(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        Node node = cache.get(key);
        remove(node);
        add(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            remove(cache.get(key));
        }
        Node node = new Node(key, value);
        add(node);
        cache.put(key, node);
        if (cache.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            cache.remove(lru.key);
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
        cache.put(4, 4);
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
        System.out.println(cache.get(4)); // 4
    }
}

Line Notes

class Node {Node class for doubly linked list with key, value, and pointers

head = new Node(0, 0);Dummy head node for easy insertion at front

tail = new Node(0, 0);Dummy tail node for easy removal at end

private void remove(Node node)Unlink node from list in O(1) time

private void add(Node node)Insert node right after head to mark as most recently used

if (!cache.containsKey(key)) return -1;Return -1 if key not found in cache

if (cache.size() > capacity)Evict least recently used node when over capacity

cache.remove(lru.key);Remove evicted key from map

#include <iostream>
#include <unordered_map>

using namespace std;

class LRUCache {
    struct Node {
        int key, val;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void add(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        Node* node = cache[key];
        remove(node);
        add(node);
        return node->val;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            remove(cache[key]);
            delete cache[key];
        }
        Node* node = new Node(key, value);
        add(node);
        cache[key] = node;
        if ((int)cache.size() > capacity) {
            Node* lru = tail->prev;
            remove(lru);
            cache.erase(lru->key);
            delete lru;
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << "\n"; // 1
    cache.put(3, 3);
    cout << cache.get(2) << "\n"; // -1
    cache.put(4, 4);
    cout << cache.get(1) << "\n"; // -1
    cout << cache.get(3) << "\n"; // 3
    cout << cache.get(4) << "\n"; // 4
    return 0;
}

Line Notes

struct Node {Node struct for doubly linked list with key, value, and pointers

head = new Node(0, 0);Dummy head node for easy insertion at front

tail = new Node(0, 0);Dummy tail node for easy removal at end

void remove(Node* node)Unlink node from list in O(1) time

void add(Node* node)Insert node right after head to mark as most recently used

if (cache.find(key) == cache.end()) return -1;Return -1 if key not found in cache

if ((int)cache.size() > capacity)Evict least recently used node when over capacity

cache.erase(lru->key);Remove evicted key from map

class Node {
    constructor(key, val) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = 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;
    }

    _add(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const node = this.cache.get(key);
        this._remove(node);
        this._add(node);
        return node.val;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this._remove(this.cache.get(key));
        }
        const node = new Node(key, value);
        this._add(node);
        this.cache.set(key, node);
        if (this.cache.size > this.capacity) {
            const lru = this.tail.prev;
            this._remove(lru);
            this.cache.delete(lru.key);
        }
    }
}

// Driver code
const cache = new LRUCache(2);
console.log(cache.put(1, 1));
console.log(cache.put(2, 2));
console.log(cache.get(1));
console.log(cache.put(3, 3));
console.log(cache.get(2));
console.log(cache.put(4, 4));
console.log(cache.get(1));
console.log(cache.get(3));
console.log(cache.get(4));

Line Notes

class Node {Node class for doubly linked list with key, value, and pointers

this.head = new Node(0, 0);Dummy head node for easy insertion at front

this.tail = new Node(0, 0);Dummy tail node for easy removal at end

_remove(node) {Unlink node from list in O(1) time

_add(node) {Insert node right after head to mark as most recently used

if (!this.cache.has(key)) return -1;Return -1 if key not found in cache

if (this.cache.size > this.capacity)Evict least recently used node when over capacity

this.cache.delete(lru.key);Remove evicted key from map

⏱

Complexity

TimeO(1) for get and put operations

SpaceO(capacity) for storing nodes and map entries

Doubly linked list allows O(1) insert and remove; hash map allows O(1) access to nodes.

💡 This approach is the most efficient and demonstrates mastery of data structures for interview coding.

Interview Verdict: Accepted / Optimal solution

This is the best approach to implement in interviews when built-in ordered dictionaries are not allowed or to show deep understanding.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal approach using doubly linked list and hash map is recommended for coding in interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) per get/put	O(capacity)	No	N/A	Mention only - never code
2. Better (OrderedDict / LinkedHashMap)	O(1) average	O(capacity)	No	N/A	Good for quick implementation if allowed
3. Optimal (Custom Doubly Linked List + Hash Map)	O(1)	O(capacity)	No	N/A	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient and introduce better approaches.Step 4: Present the optimal approach with doubly linked list and hash map.Step 5: Write clean code and test with examples.Step 6: Discuss follow-ups and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Ability to design efficient data structures, knowledge of hash maps and linked lists, and coding correctness.

Common Follow-ups

• How to modify for thread safety → Use locks or concurrent data structures.
• How to implement LFU cache → Requires frequency tracking with additional data structures.

💡 Follow-ups test your ability to extend and adapt your design under new constraints.

🔍

Pattern Recognition

When to Use

1) Need to cache data with limited capacity, 2) Must evict least recently used item, 3) Require O(1) get and put, 4) Problem mentions 'recently used' or 'cache eviction'.

Signature Phrases

least recently usedcache capacityevict when fullO(1) get and put

NOT This Pattern When

Problems about simple caching without eviction or with different eviction policies (e.g., FIFO) are different patterns.

Similar Problems

LFU Cache - similar cache eviction but based on frequencyDesign Twitter - uses similar data structures for feed management

Practice

1. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause infinite loops or incorrect list structure?

medium

A. Missing line that sets curr.child to None after splicing

B. Line where tail is found by while tail.next:

C. Line where curr.next is set to child

D. Line where tail.next is connected to curr.next

Solution

1. Step 1: Identify the role of curr.child

   After splicing the child list, curr.child must be set to None to avoid revisiting the child.

2. Step 2: Recognize missing pointer update

   The code does not set curr.child = None, causing infinite loops or incorrect traversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not clearing child pointer leads to repeated processing [OK]

Hint: Always clear child pointer after splicing [OK]

Common Mistakes:

• Forgetting to clear child pointer after splicing
• Incorrectly updating prev pointers instead

2. Consider the following buggy LFUCache get method. Which line contains the subtle bug that can cause incorrect eviction behavior?

def get(self, key: int) -> int:
    if key not in self.key_val_freq:
        return -1
    val, freq = self.key_val_freq[key]
    del self.freq_keys[freq][key]
    if not self.freq_keys[freq]:
        del self.freq_keys[freq]
        # BUG: missing update of min_freq here
    self.freq_keys[freq + 1][key] = None
    self.key_val_freq[key] = (val, freq + 1)
    return val

What is the bug?

medium

A. Missing update of min_freq after deleting freq_keys[freq]

B. Line deleting freq_keys[freq] when empty

C. Line deleting key from freq_keys[freq]

D. Line adding key to freq_keys[freq + 1]

Solution

1. Step 1: Identify the role of min_freq

   min_freq tracks the smallest frequency present in the cache, needed for correct eviction.

2. Step 2: Check frequency list deletion

   When freq_keys[freq] becomes empty and is deleted, if freq equals min_freq, min_freq must be incremented to freq + 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing min_freq update causes stale min_freq and wrong eviction [OK]

Hint: min_freq must update when freq list empties [OK]

Common Mistakes:

• Forgetting to update min_freq after freq list deletion
• Confusing key deletion with frequency list deletion
• Assuming min_freq updates automatically

3. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.

medium

A. O(n²)

B. O(n)

C. O(n log n)

D. O(n * w) where w is the width of the skyline

Solution

1. Step 1: Identify divide and conquer recurrence

   The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.

2. Step 2: Solve recurrence and analyze merge cost

   Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) [OK]

Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]

Common Mistakes:

• Confusing width w with n
• Assuming quadratic due to nested loops

4. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)

5. Suppose the RangeModule must support intervals with negative coordinates and allow intervals to be added and removed multiple times (reusing intervals). Which modification to the optimal balanced BST approach is necessary to handle this correctly?

hard

A. Replace balanced BST with a segment tree to handle negative and overlapping intervals efficiently.

B. Use a hash map keyed by interval length instead of start points to speed up queries.

C. No modification needed; the existing balanced BST approach handles negative and reused intervals naturally.

D. Store intervals as half-open [start, end) and adjust bisect searches to handle negative values correctly.

Solution

1. Step 1: Consider negative coordinates impact

   Bisect operations and interval storage must correctly handle negative values, which requires no change in data structure but careful handling of interval boundaries.

2. Step 2: Consider interval reuse

   Intervals can be added and removed multiple times, so storing intervals as half-open [start, end) and merging intervals correctly remains essential.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adjust bisect and interval representation for negatives and reuse [OK]

Hint: Half-open intervals and bisect handle negatives and reuse correctly [OK]

Common Mistakes:

• Thinking data structure must change to segment tree unnecessarily