A report recomputes a day's running total from scratch on every query - how do you optimize it, and what do you pay?
answer
- look for work repeated across queries
- count queries times rows, not lines
- can the answer be built once
- the improvement has two terms
- a stored total is a cache
basics
~20 sCompute the totals once and answer each query by lookup: q queries over n rows drop from O(q*n) to one O(n) pass plus O(1) per query. You pay extra memory, and staleness whenever the underlying rows change.
solid answer
~50 sThe bottleneck here is repeated work, not the work itself: every query walks the same day's rows again, so the cost scales as `O(q*n)` for q queries over n rows. The optimization move is precomputation - one pass builds the per-day totals, and each query becomes a lookup, so the cost becomes `O(n)` to build plus `O(1)` per query. What I pay is memory proportional to the number of distinct days, plus a correctness obligation: the stored totals are a cache, so any inserted, corrected or late-arriving row has to update or invalidate them. I would also say the build pass's assumption out loud - that I can group rows by day in that single pass - because that is where the optimized version usually breaks. If queries are rare and rows churn constantly, recomputing on demand can still be the better call.
go deeper
Be ready to point at the repeated work out loud and say what you would store instead. Recall that turning a per-query scan into a lookup is the win, and that storing results costs memory.
Explain the improvement as two terms - one build pass plus a constant lookup per query - and state what the build assumes about the input. Be able to say when one query is too few to amortize a build.
Show the production judgement: a precomputed total is a cache, so name the invalidation path for corrections and late-arriving rows, and say which key you chose to bound memory.
Own the read-versus-write tradeoff for the workload as a whole: whether the totals are maintained incrementally on the write path or rebuilt, what freshness the consumers actually need, and what the wrong key does to a fleet's memory.
## What the optimize phase is actually looking for By the time you reach the optimize step you already have a working brute force and you have said its cost out loud. Optimization is not "make the code tighter" - it is a search for **work that is done more than once**, or work whose result you could have kept. The reconciliation report is the cleanest example of the first kind. Set up the sizes explicitly, because you cannot optimize a cost you have not named: - `n` - the number of transaction rows, - `q` - the number of report queries asked against them, - `d` - the number of distinct calendar days those rows fall on. The naive version answers each query by scanning every row for the requested day. Each query is `O(n)` in the worst case, so q queries cost `O(q*n)`. That is the term to attack: it grows in **two** dimensions at once, so it degrades fastest as the report gets popular, not just as the data gets big. ## The move: pay once, read many One pass over the rows accumulates a total per day into a lookup table keyed by day. After that pass, a query is a single lookup instead of a scan. New cost, stated as two terms: | version | build | per query | q queries | |---|---|---|---| | recompute each time | none | O(n) | O(q*n) | | precompute once | O(n) | O(1) expected | O(n + q) | Two details are worth stating precisely rather than hand-waving: 1. **The build is not free.** It is a full linear pass. If `q` is 1, you have replaced one `O(n)` scan with one `O(n)` scan plus a table - a loss. Precomputation pays when the built structure is read many times. 2. **The lookup is `O(1)` expected**, not `O(1)` guaranteed, if you key the table by hash. Hash lookups are constant on average and amortized; a pathological key distribution degrades them. With a small, dense key space like calendar days you can index directly and get a true constant. ## What you pay - **Memory**: `O(d)` entries. For one year of daily totals that is a few hundred entries - nothing. Change the key to *merchant and day* and it becomes `merchants * days`, which is where a memory ceiling can actually bite. The unit you key by is the memory decision. - **Freshness**: a precomputed total is a cache with an invalidation obligation. A backdated correction that lands after the build silently makes the answer wrong, and it will be wrong *fast*, which is worse than being slow. Interviewers listen for whether you notice this. - **An input assumption**: the single-pass build assumes you can attribute each row to a day as you see it. If rows are unordered, an accumulate-into-a-table pass still works in one pass; if instead you rely on rows arriving grouped, you have added a precondition the caller must honour, and preconditions are where optimized code breaks. ## Saying the improvement so an interviewer hears it Say both terms and name the variables: "the build is one linear pass over n rows; each query is then a constant lookup, so q queries go from `O(q*n)` to `O(n + q)`; memory is one entry per day." Reporting only the query cost - "it's O(1) now" - is the classic overclaim, because it hides the pass you added and the memory you spent. ## When precomputation is the wrong move - **One-shot work.** A single query does not amortize a build pass. - **Write-heavy, read-light data.** If rows change far more often than the totals are read, you are paying invalidation on every write to speed up a read nobody asks for. - **A hard memory ceiling** with a key space that multiplies out much larger than you assumed. - **Strict freshness requirements** that make a cached total unacceptable, unless you update it on the write path. ## The scale follow-up Asked "a year of transactions, a billion rows - what breaks first, time or memory?", answer qualitatively and with the right units. The table stays tiny, because it is keyed by day, not by row; the build pass is still linear but now touches a billion rows, so the pain is the pass itself - reading the data - not the structure it produces. If the answer must be live, the build stops being a step you run inside one request and becomes something you maintain incrementally as rows arrive. If you widen the key so the table grows with the data rather than with the calendar, memory becomes the thing that breaks first. Notice that this is a judgement about *which term grows with what*, not about counting operations per second.
- A year of transactions, a billion rows - what breaks first, time or memory?Memory holds up: the table is keyed by calendar day, so it stays a few hundred entries no matter how many rows feed it. What hurts is the build pass, which still has to touch every row once. At that size the build stops being something you run inside a request and becomes an incrementally maintained total. Memory only becomes the binding constraint if you widen the key so the table grows with the data instead of the calendar.
- Rows arrive late and get backdated. Does precomputing still pay?It depends on the read-to-write ratio. Each late row now costs an update or an invalidation of the affected day, so the saving shrinks as writes grow. If totals are read far more often than rows change, adjusting one day's entry on write is cheap and precomputation still wins. If corrections stream in constantly and reports are rare, the cache costs more than it saves and recomputing on demand is the simpler, more correct choice.
- How would you state the new complexity so the interviewer hears both halves?Name the variables first, then give both terms: n rows, q queries, d distinct days; one O(n) build pass, then O(1) per query, so O(n + q) total with O(d) extra memory. Saying only 'queries are O(1) now' hides the pass you added and the memory you spent, and interviewers read that as not understanding what you traded.
saying these in an interview costs you the question
- Calls precomputation free because it happens only once
- Reports the query cost and hides the build pass
- Says lookups are O(1) with no mention of memory
- Ignores that stored totals go stale when rows change
- Precomputes for a single query that never repeats