LRU Cache, Constraint by Constraint

Start from brute force

The obvious first version keeps values in a dict and recency in a separate list: on every use, order.remove(key) then order.append(key), and to evict, order.pop(0). It is correct, because the list always runs from least to most recently used, and it takes O(capacity) space. But remove searches the list and pop(0) shifts every remaining element, so each get and put costs O(capacity) time, around 100,000 element moves per hit on a 100,000-entry cache. In the incremental round it has a second cost: two structures must stay in sync through every later stage, so each new rule means two edits that can disagree.

The approach

The insight is that an insertion-ordered map is both the lookup table and the recency list, so one structure absorbs every stage. The invariant: iterating self.d yields keys from least to most recently used, and len(self.d) <= self.cap. Each stage then adds a few lines instead of forcing a rewrite: stage 2 a length check, stage 3 a move-to-end, stage 4 two counters.

In the reference, _touch does self.d[key] = self.d.pop(key), which moves a key to the most-recent end. get counts a hit, touches the key and returns its value, or counts a miss and returns None. put handles an existing key first: it writes the new value, touches the key and returns, so a rewrite can never evict anything or change the size. Only then does it return early when self.cap <= 0, evict next(iter(self.d)), the least recently used key, when the map is full, and insert. stats() reports the two counters, which only get ever changes.

Walk through an example

Trace the reference’s own demo on LRU(2), where the map column lists keys from least to most recently used.

Complexity

Optimal: get, a rewrite and a non-evicting insert are average O(1), and space is O(capacity). An evicting put calls next(iter(self.d)), which in CPython’s dict and V8’s Map steps over slots left by earlier deletions until the table is compacted, so under steady eviction it slows as capacity grows. Brute force (dict plus list): O(capacity) per operation.

Edge cases to test

• Capacity 0: LRU(0), put("a", 1), then (size(), get("a")) → (0, None), and the get counts a miss. Without the self.cap <= 0 guard, Python’s next(iter({})) raises StopIteration, and the Map version quietly stores one entry.
• Rewriting a key while full: with a and b cached, put("a", 9) keeps the size at 2 and evicts nothing, and because it refreshes a, the next new key evicts b.
• A stored None: after put("k", None), get("k") returns None exactly like a miss, but stats() counts it as a hit. A caller that must tell them apart needs a sentinel value or a separate membership check.
• A miss changes only the counter: get("zz") on a cache holding a, b leaves the order a, b and the size at 2.
• Capacity 1: every new key evicts the previous one, so put("a", 1) then put("b", 2) leaves only b.
• A negative capacity behaves like 0, because the guard is self.cap <= 0 rather than == 0.

Common mistakes

• Treating a write to an existing key as an insert — the size must not change and the key must become most-recent.
• Counting a miss as a hit in stats(), or counting an eviction as a miss.
• Refreshing recency on put but not on get, so a hot read-only key gets evicted.
• Writing a clever compressed first version that cannot absorb the next constraint — the exact failure this round format is designed to catch.

Follow-ups an interviewer asks next

Every operation must now be O(1) in the worst case. What changes?

Use a hash map from keys to nodes of a doubly linked list with sentinel head and tail nodes. A use unlinks a node and relinks it before the tail; eviction removes the node after the head. Every step is a few pointer updates, with none of the deleted-slot skipping an insertion-ordered map can do. In Python, OrderedDict.move_to_end and popitem(last=False) give the same guarantee.

Stage 5: entries expire after a time to live. How do you add it?

Store (value, expires_at) and treat an expired entry as a miss on get, deleting it then (lazy expiry). On its own that lets dead entries hold capacity, so also prefer expired keys when evicting, or sweep periodically. Say out loud whether reading an expired key counts as a miss in stats(): raising that ambiguity is exactly what this round rewards.

Stage 6: many threads share the cache. What do you do?

The simplest correct version guards get and put with one lock, because a hit reorders recency, so even reads mutate the structure. Under contention, shard by key hash into independent caches, each with its own lock and a share of the capacity. Recency stays exact within a shard but only approximate across the whole cache.

What would you report beyond hits and misses?

The hit rate, hits / (hits + misses), which is what capacity decisions turn on, and an eviction count, because many evictions of keys that are requested again soon afterward is the sign the cache is too small. Keep evictions as their own counter rather than folding them into misses, which is one of the mistakes listed above.

Where this shows up

Anthropic’s reported coding assessment and similar live-coding rounds at other AI-native companies escalate constraints on a small problem rather than asking one hard question. The signal is adaptability: interviewers watch whether your first solution was over- or under-engineered and how gracefully you refactor when the ground moves. Narrating what breaks before you refactor is worth more than the refactor itself.

Reference solution

class LRU:
    def __init__(self, capacity):
        self.cap = capacity
        self.d = {}          # insertion order == recency order (oldest first)
        self.hits = 0
        self.misses = 0

    def _touch(self, key):
        self.d[key] = self.d.pop(key)          # move to most-recent end

    def get(self, key):
        if key in self.d:
            self.hits += 1
            self._touch(key)
            return self.d[key]
        self.misses += 1
        return None

    def put(self, key, value):
        if key in self.d:                      # update, not insert
            self.d[key] = value
            self._touch(key)
            return
        if self.cap <= 0:
            return
        if len(self.d) >= self.cap:
            oldest = next(iter(self.d))
            del self.d[oldest]
        self.d[key] = value

    def size(self):
        return len(self.d)

    def stats(self):
        return {"hits": self.hits, "misses": self.misses}


c = LRU(2)
c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3)
print(c.get("b"), c.get("a"), c.stats())   # -> None 1 {'hits': 2, 'misses': 1}

class LRU {
  cap: number;
  d: Map<string, any>;      // Map preserves insertion order == recency (oldest first)
  hits = 0;
  misses = 0;
  constructor(capacity: number) { this.cap = capacity; this.d = new Map(); }

  private touch(key: string) {
    const v = this.d.get(key);
    this.d.delete(key);
    this.d.set(key, v);                      // move to most-recent end
  }

  get(key: string): any {
    if (this.d.has(key)) {
      this.hits++;
      const v = this.d.get(key);
      this.touch(key);
      return v;
    }
    this.misses++;
    return null;
  }

  put(key: string, value: any): void {
    if (this.d.has(key)) {                   // update, not insert
      this.d.set(key, value);
      this.touch(key);
      return;
    }
    if (this.cap <= 0) return;
    if (this.d.size >= this.cap) {
      const oldest = this.d.keys().next().value as string;
      this.d.delete(oldest);
    }
    this.d.set(key, value);
  }

  size(): number { return this.d.size; }
  stats(): { hits: number; misses: number } { return { hits: this.hits, misses: this.misses }; }
}

const c = new LRU(2);
c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3);
console.log(c.get("b"), c.get("a"), c.stats());   // -> null 1 { hits: 2, misses: 1 }