LRU Cache

Signal

"O(1) get and put, with eviction by recency" needs two structures wearing one trenchcoat: a hash map for O(1) key lookup, plus an ordering structure that supports O(1) move-to-front and O(1) remove-from-back. Neither alone gets you there — a plain dict has no recency order, a plain linked list has no O(1) lookup by key.

Approach

Python's collections.OrderedDict already keeps insertion/access order and supports O(1) reordering, so it's the ordering structure and the hash map in one. On get, if the key exists, move it to the "most recently used" end and return its value. On put, if the key exists, update it and move it to the most-recent end; otherwise insert it, and if that pushes size over capacity, pop the least-recently-used end.

Skeleton

cache = OrderedDict()

def get(key):
    if key not in cache: return -1
    cache.move_to_end(key)
    return cache[key]

def put(key, value):
    if key in cache: cache.move_to_end(key)
    cache[key] = value
    if len(cache) > capacity:
        cache.popitem(last=False)

Solution

from collections import OrderedDict


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

    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.capacity:
            self.cache.popitem(last=False)

Complexity

O(1) time per get/put — OrderedDict implements move-to-end and pop-oldest in O(1) via an internal doubly linked list. O(capacity) space.

Pitfalls

• Reaching for a plain dict and a separate list to track order — list operations like "move this key to the end" are O(n), which silently breaks the O(1) requirement.
• Forgetting to move_to_end on an updating put (not just on get) — overwriting a key's value counts as using it.
• The from-scratch version (hash map of key → doubly-linked-list node, with manual splice-out/splice-to-front) is the answer if an interviewer says "no library data structures" — know the pointer surgery even if OrderedDict is what you'd actually ship.