Debug: broken cache eviction

Expected question

"A teammate's LRU-like cache sometimes returns stale values and occasionally grows past capacity. Debug the buggy sketch and fix the invariants."

Variant forms

• "Here's a broken cache — find the bug and explain the invariant."
• "Why might eviction not run even when size > capacity?"
• "Debug a race where two threads both insert the same key."
• "The cache returns a value that was already evicted — what's wrong?"
• "How do you add assertions/tests that would have caught this in CI?"
• "Fix without rewriting from scratch — minimal correct patch."
• "What logging would you add to diagnose in production?"
• "Explain the fix as if mentoring a junior who wrote the bug."

The question, as it might actually be asked

A teammate's LRU-like cache sometimes returns stale values and occasionally grows past capacity. Here is a simplified buggy sketch: python class BuggyCache: def __init__(self, capacity: int): self.capacity = capacity self.data = {} # key -> value self.order = [] # keys, oldest at index 0 def get(self, key): if key not in self.data: return None # BUG 1: refreshes by append without removing old index self.order.append(key) return self.data[key] def put(self, key, value): self.data[key] = value self.order.append(key) # BUG 2: evicts using order[0] even if that key was refreshed while len(self.data) > self.capacity: old = self.order.pop(0) if old in self.data: del self.data[old] Find the bugs, explain failure modes, and provide a correct fix (or point to the proper LRU structure).

How you'd talk while coding

I wouldn't rewrite from scratch first. I'd ask: intended LRU or FIFO? Single-threaded? Is O(n) ok for a mid-interview fix? Then I'd reproduce — capacity 2, put 1, put 2, get 1, put 3 — and watch order grow duplicates while eviction pops a stale index and deletes the wrong key (or shrinks past what you expect). Root cause: refresh appends without removing the old position. Fix: remove then append on refresh (O(n)), or say "for O(1) switch to HashMap + DLL — coding/01." Staff+ stop line: "Hypothesis → minimal repro → fix → complexity cost. I'd ship a regression test for that exact sequence — logging alone wouldn't have caught it in CI."

Where this actually gets asked

2025–2026 loops increasingly use debug/extend instead of greenfield. You're given plausible code with a subtle bug; Staff+ narrates hypothesis → test → fix.

Problem

A teammate's LRU-like cache sometimes returns stale values and occasionally grows past capacity. Here is a simplified buggy sketch:

class BuggyCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = {}          # key -> value
        self.order = []         # keys, oldest at index 0

    def get(self, key):
        if key not in self.data:
            return None
        # BUG 1: refreshes by append without removing old index
        self.order.append(key)
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.order.append(key)
        # BUG 2: evicts using order[0] even if that key was refreshed
        while len(self.data) > self.capacity:
            old = self.order.pop(0)
            if old in self.data:
                del self.data[old]

Find the bugs, explain failure modes, and provide a correct fix (or point to the proper LRU structure).

Clarifying questions you should ask first

1. Is this intended to be LRU or FIFO?
2. Are keys hashable / comparable?
3. Single-threaded?
4. Do we need O(1) or is O(n) acceptable for the fix in-interview?

Approach ladder

Reference fix (clear O(n) acceptable mid-interview; then note O(1))

class FixedCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data: dict = {}
        self.order: list = []

    def get(self, key):
        if key not in self.data:
            return None
        self.order.remove(key)  # O(n)
        self.order.append(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.order.remove(key)
        self.data[key] = value
        self.order.append(key)
        while len(self.data) > self.capacity:
            old = self.order.pop(0)
            del self.data[old]

Staff+ then says: "For O(1), switch to HashMap + doubly linked list — see coding/01."

Verbal tests to narrate

1. capacity=2; put 1, put 2, get 1, put 3 — buggy may delete wrong key / grow
2. After fix: 2 evicted, 1 and 3 remain

Staff+ deep dive

What not to discuss

• Rewriting the whole service mesh
• Silent "I'd just use Redis" without explaining the local bug

What's expected at each level

• Mid-level: Finds one bug with hints.
• Senior: Finds both; provides working fix.
• Staff+: Explains invariant, complexity trade-off, better structure.
• Principal: Connects to review culture / invariant testing in real caches.

Follow-up questions to expect

• "First debugging move?" — Minimal failing sequence, then state the invariant out loud.
• "How do you prove the fix?" — Invariant tests: map size matches order length, eviction order matches LRU.
• "Concurrency or logic?" — Separate races from single-threaded invariant breaks — this sketch is the latter.
• "Is logging enough?" — No. Ship a regression test for the exact failure sequence.

Related

• 01-lru-cache-with-concurrency.md
• 00-staff-plus-coding-bar.md