Doubly linked list + hash map: the map gives O(1) lookup, the list gives O(1) eviction and promotion - always evict from the tail, always insert/promote to the head.

LRU Cache

Problem

Design a data structure that follows the Least Recently Used cache eviction policy. Implement get(key) (return value or -1) and put(key, value) (insert or update, evicting LRU if capacity exceeded). Both operations must run in O(1) time.

Example 1:

Input: LRUCache(3); put(5, 50); put(6, 60); get(5); put(7, 70); get(6); put(9, 90); get(5); get(7); get(9)
Output: [null, null, null, 50, null, -1, null, -1, 70, 90]
Explanation: get(5) makes 5 the most recently used, so put(7, 70) evicts key 6 and put(9, 90) evicts key 5.

Constraints:

1 <= capacity <= 1000
0 <= key <= 10^4
0 <= value <= 10^4
At most 10^4 calls will be made to get and put.

Try it

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

class LRUCache:
    def __init__(self, capacity: int):
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

Tests

cache = LRUCache(2)
cache.put(5, 50); cache.put(6, 60)
assert cache.get(5)==50
cache.put(7, 70)
assert cache.get(6)==-1
cache.put(9, 90)
assert cache.get(5)==-1
assert cache.get(7)==70
assert cache.get(9)==90

Hints (3)

Solution Breakdown

Approach: Hash map for lookup, doubly linked list for ordering.

The two operations need two different powers, so use two structures. A hash map from key to node gives O(1) lookup. A doubly linked list ordered by recency gives O(1) reordering: most recently used sits just after a dummy head, least recently used just before a dummy tail. The list must be doubly linked because removing an arbitrary node in O(1) needs its predecessor, and .prev supplies that without traversal. The two sentinels mean _remove and _insert_front never hit a None neighbor, so there is no empty-list or single-node special case. _remove unlinks a node with node.prev.next = node.next; node.next.prev = node.prev; _insert_front splices it in right after head.

get looks the key up, and on a hit removes the node and reinserts it at the front to mark it most recent, returning its value (or -1 on a miss). put has two branches. If the key exists, overwrite its value and promote it to the front. If it is new and the cache is already at capacity, evict first: tail.prev is the LRU node, so unlink it and - critically - del self.map[lru.key]. This is why each node stores its own key: eviction starts from the list side and must reach back into the map. Then build the new node, register it in the map, and insert at the front.

Edge cases: Eviction only fires when len(self.map) == self.capacity on a new key; updating an existing key never evicts. A miss on get returns -1 and leaves the list untouched.

Complexity: O(1) time per get/put - hash lookup plus constant relinking; O(capacity) space.

LRU Cache

Problem

Solution Breakdown

Discussion