A memoized route-distance lookup keyed by two stop values almost always misses - what should you suspect about the key?
answer
- hits depend on what counts as equal
- too fine misses, too coarse lies
- reference equality defeats the table
- extra fields make every call unique
- equality and hashing must agree
basics
~20 sThat entries are being compared as distinct when they should be considered the same. A key compared by reference, or one carrying a field the distance does not depend on, gives every caller a fresh entry even though the arguments mean the same thing.
solid answer
~40 sAlmost certainly that the key is too fine. A memo hits only when a later call's key is considered equal to a stored one, so equality is the whole mechanism. Two failures produce constant misses: keys compared by reference, so two stop values with identical contents land in different slots, and keys that carry something the result does not depend on - a request identifier, a timestamp, a display label - which makes every call unique by construction. Both cost hits, never correctness: you simply recompute. The opposite mistake is far worse. A key that is too coarse, omitting an argument the result really depends on, hits constantly and returns the answer to a different question. When the key is a value that can be mutated after insertion, you get both symptoms at once.
code
pseudocode · 11 linestable = empty map
function distance(from, to)
key = pair(identifier_of(from), identifier_of(to))
// built from contents, so two separately constructed stops
// holding the same identifier reach the same entry
if table has key
return table at key
value = compute_distance(from, to)
store value in table at key
return valuego deeper
Know that a memo only helps when the next call's key counts as the same as a stored one. If keys are compared as objects rather than by their contents, you will store many entries and hit none.
Explain both directions and their costs: a key with too much in it kills the hit rate, a key with too little in it returns answers to the wrong question. Add that equality and hashing must agree for lookups to find what was stored.
Diagnose from evidence: a table growing at the rate of calls with a near-zero hit rate points at key construction, not at sizing. Be ready to describe normalising keys and copying them on insertion so callers cannot mutate what you filed.
The lasting decision is making key types values that cannot change after construction, so the whole mutable-key failure class stops existing across the codebase rather than being fixed one cache at a time.
## Equality is the mechanism, not a detail A memo is a map from arguments to results. A later call hits only if its key is considered equal to a key already stored, so "what counts as the same arguments" is not a side issue - it is the entire behaviour of the cache. Everything that goes wrong with a memo over a pure function goes wrong here. ## Two directions, two very different costs | the key is... | symptom | what it costs | |---|---|---| | too fine - equal arguments look different | almost every call misses, table grows fast | time and memory; results stay correct | | too coarse - different arguments look equal | almost every call hits, table stays small | **wrong answers**, silently | Hold that direction firmly, because it is the one candidates reverse. A key with too much in it makes the cache useless. A key with too little in it makes the cache lie. ## Why a too-fine key produces constant misses - **Compared by reference rather than by content.** If two stop values holding the same identifier are treated as different keys because they are different objects, then every caller that constructs its own stop value gets its own entry. The table grows linearly with calls and the hit rate sits near zero. - **Carrying what the result does not depend on.** A request identifier, a session, the moment the call was made, a label chosen for display - none of these change the distance, and each of them makes every call unique. This is the most common way a working memo is accidentally disabled during a refactor. - **Unnormalised representations of the same thing.** The same stop arriving sometimes as an identifier and sometimes as a pair of coordinates produces two entries for one question. Whether direction itself may be normalised - treating a query from one stop to another as the same key as the reverse - depends on the domain: it is sound only if the modelled cost really is the same in both directions, which for one-way legs it is not. ## Why a too-coarse key is the dangerous one Drop an argument the result depends on and the memo starts answering a different question than the caller asked - for instance keying only by the destination while the result also depends on the origin. Nothing fails loudly. The hit rate looks excellent, the table is small, and the answers are wrong for every caller after the first. This is why the key must list **every** argument the computation reads, and why lifting a hidden input into an argument (to make the function pure) also obliges you to add it to the key. ## Designing the key 1. **Start from the arguments the result depends on - all of them, and nothing else.** That set is exactly the key. Anything extra costs hits; anything missing costs correctness. 2. **Define equality on content.** Two keys built from the same identifiers must be interchangeable. If the key is a composite, its equality and its hashing must agree: keys that compare equal have to land in the same slot, or the lookup will miss on keys it already holds. 3. **Normalise before storing.** Fold equivalent spellings of the same argument into one canonical form so the table holds one entry per question, not one per phrasing. 4. **Make the key immutable, or copy it on the way in.** A key stored and then mutated by the caller is no longer findable at the slot it was filed under, and it may also collide with a different question. ## The mutable key This last case deserves its own mention because it produces both failures at once. Suppose a stop value is stored as part of a key, and the caller later edits that value. The entry is now filed under a location computed from the old contents while its contents read as something else. Lookups for the old arguments miss - the entry is effectively unreachable and leaked - and lookups for the new arguments may find an entry computed for the old ones, which is a wrong answer. Immutable keys make the whole class impossible, which is one reason memoization sits so comfortably in code built on values that do not change after construction. ## The takeaway A memo over a pure function cannot go stale, but it can still be useless or wrong, and both failures live in the key. Ask two questions of every memo: does this key mention everything the result depends on, and does it mention anything else?
- Which of the two key mistakes would you rather ship, and why?The too-fine key, every time. It costs recomputation and memory while every answer stays correct, and its symptom - a hit rate near zero - is visible in a single measurement. A too-coarse key returns the answer to a question the caller did not ask, hits almost always, and looks healthy on every dashboard until someone notices the numbers are wrong.
- What breaks if a value used as a memo key is mutated after the entry is stored?Both things at once. The entry is filed under a location derived from the old contents, so lookups for the old arguments no longer find it and it is effectively leaked, while a lookup for the new arguments may find a result computed for the old ones. Copying the key on insertion, or using values that cannot change, removes the class.
saying these in an interview costs you the question
- Thinks a missing hit means the cached value expired.
- Believes a too-fine key can return a wrong answer.
- Adds a request identifier to the key and expects hits.
- Compares composite keys by reference and calls it equality.
- Assumes any two equal keys hash to the same slot automatically.
- Stores a mutable value as a key and edits it afterwards.