Framework Thinking - Neetcode 150 - LRU Cache

Here is solutions for LRU Cache.

1. Understand the Problem

Design a data structure that supports the following operations in O(1) time:

- get(key) → return value if key exists, else -1

- put(key, value) → insert/update. If cache exceeds capacity, remove Least Recently Used (LRU) key.

2. Clarify Constraints & Ask Questions

Is capacity always > 0?
What to do if put is called on an existing key?

=> Update value & mark as most recently used.

Can key/value be any type? (Assume integers)
What if capacity = 1? Should still handle correctly.
What to return on get() if key not exist? → -1.

3. Explore Examples

capacity = 2
put(1, 1)  → cache = {1=1}
put(2, 2)  → cache = {1=1, 2=2}
get(1)     → returns 1, cache order: {2 (LRU), 1 (MRU)}
put(3, 3)  → remove 2; cache = {1=1, 3=3}
get(2)     → returns -1
put(4, 4)  → remove 1; cache = {3=3, 4=4}
get(1)     → returns -1
get(3)     → returns 3
get(4)     → returns 4

4. Brainstorm 2 - 3 Solutions

4.1. Brute Force - Insert/Delete with O(N) - Put O(N), Get O(N)

Idea: Use a list to insert + re-order the data.

=> Insert/Delete data is O(N)

Data store: A list.
Put: O(N).
Get: O(N).

4.2. Doubly Linked List - Insert/Delete with O(1) - Put O(1), Get O(1)

Idea: Same idea, but using doubly linked list to insert and delete with O(1).

Data store: Doubly linked list.
Put: O(1).
Get: O(1).

4.3. Built-In Data Structure - OrderedDict - Insert/Delete with O(1) - Put O(1), Get O(1)

Idea: Same idea, but using OrderedDict to insert and delete with O(1).

Data store: OrderedDict
Put: O(1).
Get: O(1).

5. Implement solutions

5.1. Brute Force - Insert/Delete with O(N) - Put O(N), Get O(N)

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = []
        self.capacity = capacity

    def get(self, key: int) -> int:
        for i in range(len(self.cache)):
            if self.cache[i][0] == key:
                tmp = self.cache.pop(i)
                self.cache.append(tmp)
                return tmp[1]
        return -1

    def put(self, key: int, value: int) -> None:
        for i in range(len(self.cache)):
            if self.cache[i][0] == key:
                tmp = self.cache.pop(i)
                tmp[1] = value
                self.cache.append(tmp)
                return

        if self.capacity == len(self.cache):
            self.cache.pop(0)

        self.cache.append([key, value])

Put: O(N).
Get: O(N).

5.2. Doubly Linked List - Insert/Delete with O(1) - Put O(1), Get O(1)

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # map key to node

        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left

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

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

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.cap:
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

Put: O(1).
Get: O(1).

5.3. Built-In Data Structure - OrderedDict - Insert/Delete with O(1) - Put O(1), Get O(1)

class LRUCache:

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        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.cap:
            self.cache.popitem(last=False)

Put: O(1).
Get: O(1).

6. Dry run examples

Step	Operation	DLL State (LRU → MRU)	HashMap	Returned
1	`put(1,1)`	`1`	{1:Node(1)}
2	`put(2,2)`	`1 ⇆ 2`	{1, 2}
3	`get(1)` → move 1 to MRU	`2 ⇆ 1`	{1, 2}	1
4	`put(3,3)` → full → remove LRU=2	`1 ⇆ 3`	{1, 3}
5	`get(2)` → not exist	`1 ⇆ 3`	{1, 3}	-1
6	`put(4,4)` → full → remove LRU=1	`3 ⇆ 4`	{3, 4}
7	`get(1)`	`3 ⇆ 4`	{3, 4}	-1
8	`get(3)` → move to MRU	`4 ⇆ 3`	{3, 4}	3
9	`get(4)` → move to MRU	`3 ⇆ 4`	{3, 4}	4

November 30, 2025