A long-running planner's memo table for route distances grows without bound - how do you bound it without risking wrong answers?

seniorshould knowfreq 44%

answer

any eviction policy is correct here
only hit rate is at stake
unbounded keys, unbounded table
scope the table to the work
high evictions plus low hits means thrashing

basics

~20 s

Any bound is safe, because dropping an entry of a pure lookup only costs a recomputation. Cap the entry count with a recency policy, scope the table to a unit of work so it dies naturally, or shrink the key space - then measure the hit rate you kept.

solid answer

~40 s

Start from the freedom purity gives you: for a pure lookup, every eviction policy is correct, so the only thing at stake is hit rate. That turns the problem into three practical choices. Cap the number of entries (or their total footprint) and evict by recency or frequency, which keeps the hot pairs and pays one recomputation for the rest. Scope the table to a unit of work - one request, one planning session - so it is discarded when the work ends and never accumulates across a long-running process. Or shrink the key space itself, by normalising keys or memoizing only a bounded catalogue of known stops while rare pairs fall through to the computation. Then measure: an unbounded memo over an unbounded key space is a leak wearing a cache's clothing.

Start from the freedom purity gives you: for a pure lookup, **every** eviction policy is correct, so the only thing at stake is hit rate. That turns the problem into three practical choices. Cap the number of entries (or their total footprint) and evict by recency or frequency, which keeps the hot pairs and pays one recomputation for the rest. Scope the table to a unit of work - one request, one planning session - so it is discarded when the work ends and never accumulates across a long-running process. Or shrink the key space itself, by normalising keys or memoizing only a bounded catalogue of known stops while rare pairs fall through to the computation. Then measure: an unbounded memo over an unbounded key space is a leak wearing a cache's clothing.

code

pseudocode · 14 lines

pseudocode

table = empty map
capacity = C

function distance(from, to)
    key = pair(identifier_of(from), identifier_of(to))
    if table has key
        mark key as most recently used
        return table at key
    value = compute_distance(from, to)
    if count of table = capacity
        drop the least recently used entry   // costs one recomputation later
    store value in table at key
    mark key as most recently used
    return value

go deeper

for a junior

The key point to hold: throwing entries away is always allowed here, because the next caller just computes the same value again. What you lose by throwing them away is speed, never correctness.

for a middle

Explain the choices and what each bounds - a capacity cap with a recency policy, a table scoped to one unit of work, or a deliberately smaller key space - and note that a cap smaller than the working set collects almost no hits.

for a senior

Diagnose from live signals: entry count tracking uptime with a flat hit rate is a leak, and constant evictions with a low hit rate is thrashing. Bring the memory budget and the hit rate you traded for it as numbers.

for a principal

The call worth owning is where these caches are allowed to live at all - per request by default, process-wide only for a bounded catalogue - so that no long-running service accumulates memory whose growth is driven by traffic.

Why the bound is a free choice here

With an impure lookup, eviction policy and correctness are entangled: dropping or keeping an entry can change what a caller sees. With a pure lookup they are completely separate. Any entry can be dropped at any moment and the next caller recomputes the identical value. So the design question is never "is this safe?" - it is "which entries do I want to keep paying for?"

That also means the whole discussion is measurable. Every candidate policy can be compared on two numbers: the memory it holds and the hit rate it retains.

Recognising the leak

An unbounded memo is fine exactly when the key space is bounded and small. The failure looks like this:

the number of distinct keys grows with traffic rather than with a catalogue - arbitrary coordinate pairs, user-typed locations, keys carrying a caller identifier;
the table's entry count tracks the process's uptime, with no plateau;
the hit rate stops improving long before the table stops growing, which says most retained entries are never read again.

That last signal is the decisive one: it means you are paying memory for entries that have already delivered everything they ever will.

Three ways to bound it

strategy	what it bounds	what it costs	best when
capacity cap with a recency or frequency policy	entries, or total footprint	one recomputation per eviction	a hot subset exists inside a large key space
scoping to a unit of work	lifetime of the table	repetition across units is lost	heavy repetition inside one request or session
shrinking the key space	how many keys exist at all	rare keys never get cached	a known catalogue of stops plus a long tail

Cap the size. Choose a maximum entry count or a footprint budget, and evict least-recently-used or least-frequently-used entries. Recency suits traffic with shifting hot spots; frequency suits a stable hot set with occasional one-off queries that would otherwise flush it. Both are correctness-neutral here, so pick by measurement.
Scope the table to a unit of work. A memo created for one planning request, used heavily within it, and discarded at the end has a natural bound: the work that built it. This is often the highest-value option, because the repetition in this kind of workload is usually intense and local - one request asking for the same leg dozens of times - rather than spread evenly across days.
Shrink the key space. Normalise keys so equivalent questions share an entry, and consider memoizing only what is worth memoizing: pairs drawn from a known catalogue of stops, with everything else falling through to the computation. A cache that deliberately refuses the long tail stays bounded by construction.

A fourth option exists where the runtime offers it: hold entries through references the memory manager is allowed to reclaim under pressure. It bounds the table without you choosing a number, at the price of a hit rate you no longer control and cannot predict - runtimes differ substantially in when they reclaim such references.

The trap: a cap that thrashes

Capping does not automatically bound cost. If the working set is larger than the cap, entries are evicted just before their next use: you pay the bookkeeping of a cache, hold the memory of a full table, and collect almost no hits. The symptom is a high eviction rate alongside a low hit rate. The fix is not blindly raising the cap - it is deciding whether repetition exists at that scale at all, and if it does not, scoping the cache to where it does.

What to measure before and after

hit rate, before the change and after, on real traffic rather than a replay of one key;
eviction rate, whose ratio to hit rate exposes thrashing immediately;
entry count and footprint per entry, so the memory budget is a number and not an adjective;
distinct keys over a window, which tells you whether a cap can ever hold the working set;
the latency of a miss, because that is exactly what an eviction costs a caller.

The framing to carry into the review

Because this is a memo over a pure computation, no reviewer needs to reason about staleness, ordering, or what happens if two callers race to fill the same key - the worst outcome of a race is the same value computed twice. The review is about memory and hit rate only, which is a far smaller argument to have, and it is why bounding a memo is usually a tuning exercise rather than a redesign.

## Why the bound is a free choice here With an impure lookup, eviction policy and correctness are entangled: dropping or keeping an entry can change what a caller sees. With a pure lookup they are completely separate. Any entry can be dropped at any moment and the next caller recomputes the identical value. So the design question is never "is this safe?" - it is "which entries do I want to keep paying for?" That also means the whole discussion is measurable. Every candidate policy can be compared on two numbers: the memory it holds and the hit rate it retains. ## Recognising the leak An unbounded memo is fine exactly when the key space is bounded and small. The failure looks like this: - the number of distinct keys grows with traffic rather than with a catalogue - arbitrary coordinate pairs, user-typed locations, keys carrying a caller identifier; - the table's entry count tracks the process's uptime, with no plateau; - the hit rate stops improving long before the table stops growing, which says most retained entries are never read again. That last signal is the decisive one: it means you are paying memory for entries that have already delivered everything they ever will. ## Three ways to bound it | strategy | what it bounds | what it costs | best when | |---|---|---|---| | capacity cap with a recency or frequency policy | entries, or total footprint | one recomputation per eviction | a hot subset exists inside a large key space | | scoping to a unit of work | lifetime of the table | repetition across units is lost | heavy repetition inside one request or session | | shrinking the key space | how many keys exist at all | rare keys never get cached | a known catalogue of stops plus a long tail | 1. **Cap the size.** Choose a maximum entry count or a footprint budget, and evict least-recently-used or least-frequently-used entries. Recency suits traffic with shifting hot spots; frequency suits a stable hot set with occasional one-off queries that would otherwise flush it. Both are correctness-neutral here, so pick by measurement. 2. **Scope the table to a unit of work.** A memo created for one planning request, used heavily within it, and discarded at the end has a natural bound: the work that built it. This is often the highest-value option, because the repetition in this kind of workload is usually intense and local - one request asking for the same leg dozens of times - rather than spread evenly across days. 3. **Shrink the key space.** Normalise keys so equivalent questions share an entry, and consider memoizing only what is worth memoizing: pairs drawn from a known catalogue of stops, with everything else falling through to the computation. A cache that deliberately refuses the long tail stays bounded by construction. A fourth option exists where the runtime offers it: hold entries through references the memory manager is allowed to reclaim under pressure. It bounds the table without you choosing a number, at the price of a hit rate you no longer control and cannot predict - runtimes differ substantially in when they reclaim such references. ## The trap: a cap that thrashes Capping does not automatically bound cost. If the working set is larger than the cap, entries are evicted just before their next use: you pay the bookkeeping of a cache, hold the memory of a full table, and collect almost no hits. The symptom is a high eviction rate alongside a low hit rate. The fix is not blindly raising the cap - it is deciding whether repetition exists at that scale at all, and if it does not, scoping the cache to where it does. ## What to measure before and after - **hit rate**, before the change and after, on real traffic rather than a replay of one key; - **eviction rate**, whose ratio to hit rate exposes thrashing immediately; - **entry count and footprint per entry**, so the memory budget is a number and not an adjective; - **distinct keys over a window**, which tells you whether a cap can ever hold the working set; - **the latency of a miss**, because that is exactly what an eviction costs a caller. ## The framing to carry into the review Because this is a memo over a pure computation, no reviewer needs to reason about staleness, ordering, or what happens if two callers race to fill the same key - the worst outcome of a race is the same value computed twice. The review is about memory and hit rate only, which is a far smaller argument to have, and it is why bounding a memo is usually a tuning exercise rather than a redesign.

Why is scoping a memo to a single request often better than capping a process-wide one?
Because the repetition in this kind of workload is usually local and intense: one planning request asks for the same leg many times, while two requests a day apart share little. A per-request table captures that repetition, is bounded by the work itself, and needs no policy, no cap and no coordination between callers.
The cap is in place but the hit rate is still near zero while evictions are constant. What does that tell you?
That the working set is larger than the cap, so entries are evicted before their next use. You are paying for a cache and collecting none of its benefit. Either the repetition exists at a smaller scope - move the table there - or the traffic has no repetition to exploit and the memo should go.
Two callers miss on the same key at the same time and both compute it. Is that a problem?
Not for correctness: a pure computation gives both the identical value, so whichever is stored last is the same entry. It is only a cost question - duplicated work on a hot key. Coordinating the fill removes the duplication, and paying for that coordination is a measurement decision like any other here.

saying these in an interview costs you the question

Argues a particular eviction policy is needed for correct answers.
Adds a time-to-live and calls the entries safer than before.
Raises the cap as the first response to a low hit rate.
Treats an unbounded table as fine because entries never go stale.
Ignores that two callers filling one key is only duplicated work.
Picks a cap without measuring distinct keys over a window.

A long-running planner's memo table for route distances grows without bound - how do you bound it without risking wrong answers?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why the bound is a free choice here

Recognising the leak

Three ways to bound it

The trap: a cap that thrashes

What to measure before and after

The framing to carry into the review

▾common follow-ups3 questions

▾red flags6 flags

Why the bound is a free choice here

Recognising the leak

Three ways to bound it

The trap: a cap that thrashes

What to measure before and after

The framing to carry into the review

answer

go deeper