LRU Cache: OrderedDict Gives You O(1) Get and Put

LRU Cache asks for get and put in O(1). A dictionary is O(1) for lookup and is unordered for eviction. A list of keys is ordered and is O(n) to move a key to the front. You need both: a map from key to value, and a structure that can splice a node to the most-recent end in O(1). That structure is a doubly linked list. In Python, OrderedDict is that list plus the map, and move_to_end is the splice.

Say this out loud before you code. Interviewers who have banned OrderedDict want the nodes written out. Interviewers who have not are checking that you know why a single dict is not enough. Either way the design is the same.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.items:
            return -1
        self.items.move_to_end(key)
        return self.items[key]

    def put(self, key: int, value: int) -> None:
        if key in self.items:
            self.items.move_to_end(key)
        self.items[key] = value
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)

move_to_end marks the key as most recently used. popitem(last=False) evicts the least recently used, the front of the order. Update of an existing key must also move it. Forgetting that is the bug: a hot key sits at the old position and gets evicted while a key you touched once stays.

Complexity and the edges

Each call is O(1) average. Space is O(capacity).

Capacity 1 is the edge they use. put(1, 1), put(2, 2), get(1) returns -1. The first key was evicted. get on a missing key returns -1 and must not insert. A get that inserts changes the cache and fails the next eviction.

If they want the linked list explicit, keep a dict of key to node and a dummy head and tail. get detaches the node and reinserts it before the tail. put of a new key, when size is at capacity, detaches the node after the head. The code is longer. The operations are the ones OrderedDict already performs. Draw the two dummies on the board so "remove from the middle" is visibly O(1): you have the node, you rewire its neighbors, you never scan.

Do not sort a list of timestamps on each call. That is O(n log n) and it misses the point of the question.