Your request path uses an amortized O(1) structure but p99 spikes — how do you explain and fix it?

This is the interview scenario where amortized analysis stops being a whiteboard exercise. A structure on the hot path advertises amortized O(1); throughput is fine, the mean is fine, and the p99 has a periodic cliff. Someone will propose that the library is lying. It is not. ## Why the bound and the symptom are both real An amortized bound constrains the total cost of a sequence. It permits — in fact it is *built around* — the pattern where many cheap operations accumulate deferred work and one later operation discharges all of it. Percentile latency measures individual calls. So the two statements "the structure is amortized O(1)" and "one call in fifty thousand takes twenty milliseconds" are perfectly compatible; they are answers to different questions. Confusion here is common enough that it is worth saying explicitly in the room: **amortized is a throughput guarantee, percentiles are a per-call metric, and the bound was never a promise about the metric you are looking at.** ## Confirm before you rewrite The diagnosis has a distinctive signature, and checking it costs far less than a rewrite: - **Rhythm.** Bulk maintenance in such structures fires at intervals that stretch as the structure grows, so spikes should become less frequent over the lifetime of a process, not more. - **Amplitude.** Each bulk event handles more live elements than the last, so spike duration should grow while frequency falls. - **Correlation.** Instrument the bulk event directly. Every latency spike should carry one, and every bulk event should show up as a spike. If spikes appear without bulk events, look elsewhere: a runtime pause that stops all threads, lock contention, a downstream dependency, or storage. A spike pattern that is *periodic in wall-clock time* rather than in operation count is usually not this at all — that shape points at a timer, a scheduled job, or a cache expiry, and rewriting the data structure would have fixed nothing. ## The ladder of fixes 1. **Pre-size or warm.** If you know the working set's rough magnitude, build the structure at that size before serving traffic. The bulk work still happens; it happens at startup, off the critical path. Cheapest fix, no algorithmic change, and often enough on its own. 2. **Shard or bound the size.** Many smaller structures each do proportionally smaller bulk work, so the worst single call shrinks even though the total work does not. This also spreads the events out in time instead of concentrating them. 3. **De-amortize.** Restructure so that every operation performs a fixed slice of the pending maintenance — incremental reorganisation, or maintaining the old and new state side by side while migration proceeds a step at a time. The amortized total is unchanged, but the worst single call becomes bounded. You pay for it in constant factors, in memory during the transition, and in real implementation complexity. 4. **Change the guarantee.** Adopt a structure with worst-case per-operation bounds. Asymptotically it is often no better, and its constants are usually worse, but it is the only option that turns the tail into a contract instead of an observation. ## What the tradeoff really is De-amortized and worst-case structures are almost always slower in the mean than their amortized cousins — that is precisely why the amortized versions became the default. So the decision is not "correct versus incorrect", it is which metric the system is judged on. A batch pipeline measured on total wall-clock time should keep the amortized structure and ignore the tail entirely. A request path with a p99 SLO, a call that runs while holding a lock, or a real-time deadline should not, and the reason is not that the amortized structure is bad but that it answers a different question than the SLO asks. The organisational half of this is worth naming: interfaces should say which bound they offer. When an internal component documents "O(1)" and means "amortized O(1)", every timeout, retry budget and capacity plan downstream is derived from a number that no single call is obliged to honour. The fix is as much a documentation and review habit as it is a data-structure choice. ## What a strong answer sounds like Name the compatibility of the bound with the symptom, propose the correlation check before any redesign, then give the ordered ladder with its costs. The candidates who do poorly here are the ones who either declare the library broken or leap straight to writing a custom worst-case structure without ever confirming that the bulk events and the spikes line up.