Requirements checklist

Ask, one at a time, absorbing each answer:

□ capacity: entries or bytes?          splits the whole design
□ operations: get/put/remove only?     no iteration = ordering stays private
□ does get refresh recency?            reads become bookkeeping writes
□ does put-on-existing refresh/evict?  two put paths or one
□ eviction trigger, exactly?           new-key insert at capacity only?
□ null values allowed?                 miss signal ambiguity
□ threading?                           name the single-threaded assumption
□ stats wanted?                        hit needs a DEFINITION, then a counter

The core model

index      Map: key -> Node            -- node, NOT value: the O(1) insight
list       sentinels head/tail; head = just used, tail = victim
Node       key, value, prev, next      -- key aboard for eviction's map-delete
helpers    unlink(n), linkAtHead(n)    -- ALL pointer surgery lives here
get        lookup -> refresh standing -> count hit/miss
put        existing: update+refresh, early return (never evicts)
           new: evict at capacity, insert at head
evict      tail.prev -> unlink + map.remove in ONE flow
policy     EvictionPolicy seam: onAccess/onInsert/onRemove + chooseVictim

Invariants: map.size == list.length ≤ capacity · in cache ⇔ in both structures · only get/put/remove mutate · sentinels never hold data.

Principles demonstrated (name them at the decision)

• Single responsibility — pointer surgery has exactly two homes (unlink, linkAtHead); a linking bug can only exist in one place.
• Open/closed — eviction decisions behind a policy seam with honest hooks; preferences change, capacity bookkeeping doesn't.
• Separation of concerns — storage (map, capacity) knows nothing of ordering metadata; stats are a defined contract, not folklore.

Complexity facts

get / put / remove   O(1) each — BECAUSE the map points at nodes
without that pointer refresh degrades to O(n) list search
space                O(capacity) nodes + map; +2 pointers & a key per entry
timestamps-and-scan  O(1) reads but O(n) eviction — ordering maintained
                     beats ordering recomputed

What earns points, per report dimension

• Requirements & interface — capacity semantics, refresh-on-get, the two put behaviors, null policy, and stats pinned before design.
• Core design & invariants — map-points-at-node said explicitly, policy seam with real hooks, distinct put paths, lockstep invariants stated unprompted.
• Extension probe — the round will move the requirements; points come from locating the change precisely in your model — what changes, what provably doesn't, and why the untouched parts were protected by your seams.
• Complexity honesty — O(1) claims justified by the pointer that makes them true; overheads and expected-case caveats offered unprompted.
• Communication — model in words before code, the two put paths narrated, probes answered directly.