LRU Cache

Start from brute force

The obvious first version stores values in a dict and recency in a separate Python list order, oldest first. Every get hit and every put calls order.remove(key) and order.append(key), and an overflow evicts order.pop(0) and deletes that key from the dict. It is correct, because the list is exactly the recency order. It costs O(capacity) time per operation, since remove searches the list and both remove and pop(0) shift every later element, and O(capacity) space. That is the wrong cost for a cache, whose whole job is to be the fast path: at capacity 100,000 a single hit can scan and shift 100,000 entries.

The approach

An LRU cache needs three operations to be cheap: look up a key, mark it most recently used, and find the least recently used key. The insight is that an insertion-ordered hash map provides all three if its order is read as recency: popping a key and inserting it again moves it to the newest end, and the first key is the oldest. The invariant after every op: iterating cache lists keys from least to most recently used, and len(cache) <= capacity.

The reference keeps that order in cache and appends get answers to results. A hit does val = cache.pop(key) then cache[key] = val, so a read counts as a use; a miss appends -1 and touches nothing. A put pops an existing key first, inserts cache[key] = val at the newest end, and only if len(cache) > capacity evicts oldest = next(iter(cache)). An update never evicts, because the size did not grow. The classic equivalent, and what OrderedDict does internally, is a hash map from keys to nodes of a doubly linked list.

Walk through an example

The first example with capacity 2, one row per op; the cache column lists keys from least to most recently used.

Complexity

Ordered dict: a get and the insert half of a put are average O(1), and space is O(capacity). Eviction’s next(iter(cache)) skips deleted slots, so under steady eviction it slows as capacity grows (see the follow-ups); a doubly linked list or OrderedDict makes every step O(1). Brute force: O(capacity) per operation from remove and pop(0), O(capacity) space.

Edge cases to test

• Capacity 1: every put of a new key evicts the previous one, so put(1,1), put(2,2), get(1), get(2) gives [-1, 2].
• Updating a key on a full cache refreshes it and evicts nothing: put(1,1), put(2,2), put(1,10), put(3,3) evicts 2, so get(2), get(1) give [-1, 10]. A bare cache[key] = val leaves 1 in the oldest slot and gives [2, -1].
• A get saves a key: put(1,1), put(2,2), get(1), put(3,3), get(1), get(2) gives [1, 1, -1]. A get that does not refresh recency evicts 1 instead and gives [1, -1, 2].
• A miss changes nothing: get(5) returns -1, inserts nothing and leaves the order as it was.
• A stored value of -1 looks like a miss but is a hit: after put(1,-1), put(2,2), get(1), a put(3,3) evicts 2, not 1, and the full run …, get(2), get(1) returns [-1, -1, -1] for two different reasons.

Common mistakes

• Backing it with an array or plain list — moving an element to the front is then O(n), losing the O(1) guarantee.
• Updating recency only on put and not on get — a read must also mark the entry as recently used.
• Updating with a bare cache[key] = val: assigning to an existing key keeps its old position in a dict or Map, so the update does not refresh recency. Pop the key first.
• Evicting before inserting whenever the cache is full: when the key already exists the size does not grow, so put(2, 20) on a full cache holding 1 and 2 wrongly throws out 1.
• Off-by-one on capacity — evict when size exceeds capacity, and remember to update the map, not just the list.

Follow-ups an interviewer asks next

Why does this solution slow down at large capacity, and how do you make eviction truly O(1)?

Python’s dict and JavaScript’s Map keep insertion order in an array and leave deleted slots in place until the table is rebuilt, so next(iter(cache)) must skip every deleted slot in front of the oldest key. Under steady eviction that work grows with capacity. Use collections.OrderedDict with move_to_end(key) and popitem(last=False), or a hash map from keys to doubly linked list nodes.

Make it safe for many threads.

Every operation, even a get, rewrites the recency order, so a read-write lock buys nothing: reads are writes. Put one lock around each operation, or shard the cache by key hash into independent LRU caches with their own locks, which trades exact global recency for less contention. Busy caches often approximate LRU instead, for example with the clock algorithm, where a hit only sets a flag.

Evict the least frequently used key instead.

That is LFU. Keep each key’s value and use count, plus a map from each count to an insertion-ordered set of keys, and track the minimum count. A hit moves its key from bucket count to count + 1; eviction removes the oldest key in the minimum-count bucket. Every step is O(1), and recency breaks ties within a bucket.

Entries should also expire after a time-to-live.

Store an expiry time with each value. On get, treat an expired entry as a miss and delete it. Expired entries that are never read still take space, so sweep them periodically or let LRU push them out, since an unread entry drifts to the old end anyway. Pass the clock in as a parameter so tests can control time.

Where this shows up

LRU and its approximations are the standard eviction policies across the stack: CPU caches use pseudo-LRU, Memcached evicts least-recently-used items, Redis offers sampled LRU policies such as allkeys-lru (its default policy is noeviction), and database buffer pools use variants such as PostgreSQL’s clock sweep or InnoDB’s midpoint-insertion LRU. Python’s own functools.lru_cache is a dict plus a doubly linked list. That combo is the textbook way to get O(1) on both ordering and lookup, and it shows up any time you must bound memory while keeping the hot set.

Reference solution

def lru_cache(capacity, ops):
    cache = {}          # insertion order = recency (oldest first)
    results = []
    for op in ops:
        if op[0] == "get":
            key = op[1]
            if key in cache:
                val = cache.pop(key)
                cache[key] = val          # re-insert → most recently used
                results.append(val)
            else:
                results.append(-1)
        else:  # "put"
            key, val = op[1], op[2]
            if key in cache:
                cache.pop(key)            # remove old position
            cache[key] = val              # insert as most recently used
            if len(cache) > capacity:
                oldest = next(iter(cache))
                cache.pop(oldest)         # evict least recently used
    return results


print(lru_cache(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]))
# -> [1, -1, -1, 3, 4]

function lruCache(capacity: number, ops: (string | number)[][]): number[] {
  const cache = new Map<number, number>(); // insertion order = recency
  const results: number[] = [];
  for (const op of ops) {
    if (op[0] === "get") {
      const key = op[1] as number;
      if (cache.has(key)) {
        const val = cache.get(key)!;
        cache.delete(key);
        cache.set(key, val);              // re-insert → most recently used
        results.push(val);
      } else {
        results.push(-1);
      }
    } else {                              // "put"
      const key = op[1] as number;
      const val = op[2] as number;
      if (cache.has(key)) cache.delete(key);
      cache.set(key, val);                // insert as most recently used
      if (cache.size > capacity) {
        const oldest = cache.keys().next().value as number;
        cache.delete(oldest);             // evict least recently used
      }
    }
  }
  return results;
}

console.log(lruCache(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]));
// -> [1, -1, -1, 3, 4]