The lookup works. Why does the next insert lose it?
Margin Notes keeps two recent documents in a small cache. A read returns the expected document, but the next insertion removes a document the reader just opened.
The question
Fictional exercise. The supplied code, data and outcomes are authored teaching examples, not an employer question or model output.
function createCache(capacity) {
return {
capacity,
items: /* @__PURE__ */ new Map()
};
}
function put(cache, key, value) {
cache.items.delete(key);
cache.items.set(key, value);
if (cache.items.size > cache.capacity) cache.items.delete(cache.items.keys().next().value);
}
function readUnchanged(cache, key) {
if (!cache.items.has(key)) return null;
return cache.items.get(key);
}
// Each trace starts with createCache(itsCapacity).
// Call put(cache, key, value) or readUnchanged(cache, key).Keys are strings. Stored values are positive integers; null means a missing key and is never stored. Map order is least recent first. A successful get moves its key last; a miss changes nothing. put adds or updates a value and moves its key last. An overwrite uses one slot. When size exceeds capacity, remove the oldest key. Each trace begins empty. This packet covers local caches of capacity one or two, without concurrency or expiration.
| Operation | Key | Value | |
|---|---|---|---|
| 1 | put | a | 1 |
| 2 | put | b | 2 |
| 3 | get | a | Not supplied |
| 4 | put | c | 3 |
| 5 | get | a | Not supplied |
Margin Notes is a fictional documentation app. All code, operations and expected states are authored teaching data.
“Trace the supplied code. Find the first state mismatch, choose a useful test and defend the repair.”
Not saved by this site. Your browser may restore text when you navigate back.
A strong answer, step by step
Open each step in turn. This is one strong answer, not the only one.
Step 1: Name the state promise
What would you do here? Open the move you’d make.
Check only the returned value
Tempting, but it misses something. The first get(a) returns 1 even when recency is wrong.
Check the value, retained entries and order
The strong move. The next eviction depends on both retained identity and recency.
Clear the other entries on every read
Tempting, but it misses something. A read must preserve the other stored entries.
See how a strong candidate says it
“A successful read must preserve all stored entries and move the read key to the most-recent position. Returning the right value and staying within two entries are necessary but do not establish that recency is correct.”
Why it works: The contract covers the state that a later operation observes.
Step 2: Trace before editing
What would you do here? Open the move you’d make.
Mark the order after get(a) as the first mismatch
The strong move. The return value agrees, but recency already violates the contract.
Say put(b,2) already exceeds capacity
Tempting, but it misses something. Two distinct entries fit the capacity of two.
Treat the last null as the only evidence
Tempting, but it misses something. It exposes the effect but misses the earlier state transition that explains it.
See how a strong candidate says it
“After put(a,1) and put(b,2), the order is a,b. The starting get(a) returns 1 and leaves that order unchanged. The contract requires b,a. That is the first mismatch; the next put(c,3) then removes a rather than b.”
Why it works: The state defect appears before the final failed lookup.
Step 3: Select a discriminating test and repair
What would you do here? Open the move you’d make.
Keep get unchanged because its first return passes
Tempting, but it misses something. The later insertion exposes the wrong eviction.
Clear the cache and keep only a
Tempting, but it misses something. The other entry must survive a read.
Move only the read key and check read-then-evict
The strong move. This changes the faulty state transition while preserving other entries.
See how a strong candidate says it
“I would read a, insert c, then read a again, while also checking retained entries and order. A delete/reinsert of only a after a hit preserves its value and moves it last. Clearing the cache would lose b and fail a separate retention check.”
Why it works: A repair must satisfy the whole contract, not just one return.
Step 4: Report the actual coverage
What would you do here? Open the move you’d make.
Call the cache formally verified
Tempting, but it misses something. These examples do not quantify over every possible operation sequence.
Report the matching traces and untested domains
The strong move. The claim matches the supplied evidence.
Check only that every run ends with two entries
Tempting, but it misses something. Capacity alone can hide the wrong entries or values.
See how a strong candidate says it
“I would inspect the five authored traces: read/eviction, retention, overwrite, missing read and one-slot capacity. Matching those expected values and states supports this finite packet. It does not prove concurrency, expiration or every input.”
Why it works: A useful outcome names both the evidence and its boundary.
The answer, in short
- Decision
- Repair the read's recency update and compare the full state.
- Because
- The correct returned value hides an earlier order mismatch.
- What would change it
- A different cache contract, concurrency model or expiration policy would need different evidence.
Common traps
- Treating a plausible result as proof of the full contract.
- Claiming more than the shown inputs and checks establish.
Check your answer
- Did you name value, entry retention and recency separately?
- Did you identify the first state mismatch after the read?
- Did your test expose the next eviction and preserve the other entry?
- Did you keep the five-trace coverage limit?
Last reviewed Nov 10, 2026