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. You need to design a data structure that supports incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

Solution

1. Step 1: Understand operation requirements

   Increment, decrement, getMaxKey, and getMinKey must all be O(1).

2. Step 2: Evaluate approaches

   Hash map + linear scan (B) is O(n) for max/min. Balanced BST (C) and priority queue (D) have O(log n) operations. Doubly linked list with buckets and hash maps (A) supports O(1) updates and retrievals.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket list + hash maps enable O(1) increments, decrements, and max/min retrievals [OK]

Hint: Bucket list + hash maps enable O(1) max/min updates [OK]

Common Mistakes:

• Thinking balanced BST or priority queue can achieve O(1) for all operations

2. Given the following code snippet for the optimal UndergroundSystem implementation, what is the value of travel_time when checkOut(1, "Leyton", 20) is called after checkIn(1, "Paradise", 3) and checkIn(2, "Leyton", 10)?

class Node:
    def __init__(self, id, station, time):
        self.id = id
        self.station = station
        self.time = time
        self.next = None

class UndergroundSystem:
    def __init__(self):
        self.head = None
        self.route_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        new_node = Node(id, stationName, t)
        new_node.next = self.head
        self.head = new_node

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        prev = None
        curr = self.head
        while curr:
            if curr.id == id:
                travel_time = t - curr.time
                route = (curr.station, stationName)
                if route not in self.route_data:
                    self.route_data[route] = [0, 0]
                self.route_data[route][0] += travel_time
                self.route_data[route][1] += 1
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                return
            prev = curr
            curr = curr.next

easy

A. 10

B. 17

C. 7

D. 20

Solution

1. Step 1: Trace checkIn calls

   First, checkIn(1, "Paradise", 3) adds Node(id=1, station="Paradise", time=3) at head. Then checkIn(2, "Leyton", 10) adds Node(id=2, station="Leyton", time=10) at head.

2. Step 2: Trace checkOut(1, "Leyton", 20)

   Traverse linked list from head: Node with id=2 (not match), then Node with id=1 (match). travel_time = 20 - 3 = 17.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Check-in time for id=1 is 3, checkout time is 20, difference is 17 [OK]

Hint: Subtract check-in time from checkout time for travel_time [OK]

Common Mistakes:

• Using wrong node's time due to linked list order

3. 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

4. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs

5. Suppose the UndergroundSystem is extended to allow multiple check-ins by the same passenger without requiring a check-out first (i.e., passengers can start multiple trips before finishing any). Which modification to the data structure or algorithm is necessary to handle this correctly?

hard

A. Keep a stack of check-in nodes per passenger id to track multiple active trips.

B. Use a hash map from passenger id to a single check-in node, overwriting previous check-ins.

C. Store all check-ins in a linked list and traverse fully on each checkOut to find the earliest unmatched check-in.

D. Disallow multiple check-ins by the same passenger to avoid complexity.

Solution

1. Step 1: Understand the problem extension

   Passengers can have multiple active trips simultaneously, so a single check-in per id is insufficient.

2. Step 2: Choose data structure to track multiple check-ins

   A stack per passenger id allows tracking multiple check-ins in order, enabling correct matching on checkOut.

3. Step 3: Why other options fail

   Overwriting check-ins loses data (A). Traversing full list each time (C) is inefficient. Disallowing multiple check-ins (D) is not a solution.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack per id supports multiple active trips correctly [OK]

Hint: Stack per id tracks multiple active check-ins [OK]

Common Mistakes:

• Overwriting check-in info loses data