Why do converging pointers beat a hash-based pair search on a read-only sorted file of a billion 64-bit amounts, and what arithmetic trap remains?
answer
- what does the hash route cost in bytes?
- two read fronts, both sequential
- the file is already sorted — use it
- adding two extremes can wrap the sum
- widen, check, or argue the ranges
basics
~20 sConverging pointers need O(1) extra memory and two sequential read fronts, so they work on a read-only billion-entry file where an O(n)-space hash structure will not fit. The remaining trap: adding two extreme 64-bit values can overflow and corrupt the comparison.
solid answer
~50 sThe hash route needs an auxiliary structure proportional to the data — on the order of 8 GB of raw values plus table overhead for 10^9 entries — and its probes are random-access, which is hostile to page cache and prefetching. Converging pointers exploit the sortedness the file already has: O(1) auxiliary space, two purely sequential read fronts (one forward, one backward), no writes, one deterministic O(n) pass. The trap is overflow: adding two signed 64-bit amounts near the extremes can wrap, and a corrupted three-way comparison steers a pointer the wrong direction, silently voiding the elimination argument. Related index arithmetic like `lo + hi` (familiar from midpoint calculations) can overflow narrower index types too. Do the sum comparison in wider or overflow-checked arithmetic, or rearrange it only with an explicit range argument for why each side stays in bounds.
go deeper
Know the headline: converging pointers use O(1) extra space and sequential reads, so they scale to inputs far larger than memory-hungry alternatives whenever the data is already sorted.
Be ready to do the arithmetic out loud: a billion eight-byte values is about 8 GB before table overhead, versus two cursors. Explain why sequential access from both ends is cache- and prefetch-friendly.
An interviewer expects the full trade study — space in bytes, access pattern, read-only constraint, determinism — plus the overflow trap in the sum comparison and a concrete mitigation you would actually ship.
Own the meta-lesson: when asymptotics tie, constants, memory ceilings and IO patterns decide. Push designs that exploit structure the data already has before approving ones that rebuild equivalent structure on the side.
## The constraint set A read-only, memory-mapped file holds 10^9 signed 64-bit amounts in ascending order; find two entries summing to an exact chargeback total. Three constraints matter: - the data is far bigger than you want to mirror in memory; - it cannot be mutated; - and it is *already sorted* — structure you paid nothing for. ## Pricing the hash route The standard unsorted-input approach builds an auxiliary lookup structure over the values seen so far. - **Memory.** At this scale the arithmetic is brutal: 10^9 × 8 bytes ≈ 8 GB of raw values before any table overhead — buckets, control metadata, load-factor headroom typically inflate that well past 10 GB. - **Access pattern.** Its probes are random-access, scattering reads across that structure. - **Time guarantee.** Its time guarantee is probabilistic: expected O(1) per operation but O(n) worst case under adversarial collisions. Nothing about it uses the sortedness the file already has. ## Why converging pointers survive Two cursors, one at each end: **O(1) auxiliary space** regardless of n. The access pattern is two purely *sequential* read fronts — one walking forward, one backward — which page caches and prefetchers reward; each page of the file is touched at most once. No writes are ever issued, so a read-only mapping is fine. The pass is **worst-case O(n) and deterministic**, with each inward move justified by sorted order: a too-small sum condemns the low element (its best possible partner already failed), a too-large sum condemns the high one. Asymptotically the two routes look similar — both roughly linear — but constants, the memory ceiling and the IO pattern decide, and here they all point the same way. **The per-element binary-search alternative** — for each entry, search the file for its complement — deserves an explicit rejection too: O(n log n) instead of O(n), and each search performs about 30 scattered probes (log₂ 10^9), exactly the random access the converging pass avoids. On file-backed data the access pattern often costs more than the operation count; an algorithm that streams beats one that jumps. ## The trap that remains: overflow The comparison `a[lo] + a[hi]` versus `T` adds two signed 64-bit values. Amounts near the extremes of the representable range wrap on addition (or trap, depending on the arithmetic rules in force), producing a sum with the wrong sign or magnitude. The damage is subtle and silent: the three-way comparison steers a pointer the *wrong direction*, which voids the elimination proof — the scan can discard the very element the answer needed and then report "no pair" with full confidence. A cousin bug hides in **index arithmetic**: forms like `lo + hi` (the midpoint idiom) computed in a 32-bit signed index type sit uncomfortably close to the cliff at 10^9 entries — the sum of two indices approaches within a few percent of the 2^31 ceiling, and any growth in the file falls off it. ## Mitigations, honestly ranked - (1) **Widen:** perform the sum in a larger integer type where one is available — simplest and hardest to get wrong. - (2) **Checked arithmetic:** overflow-detecting operations that flag or trap, converting silent corruption into a visible failure. - (3) **Algebraic rearrangement** — comparing `a[lo]` against `T - a[hi]` — must be argued, not assumed: the subtraction can overflow for the same extreme operands, so it is safe only with a case analysis on signs and ranges. The senior answer names one strategy and defends why it is safe for these particular ranges, rather than gesturing at "just rearrange it." ## The shape of the answer interviewers want Not "two pointers is O(n), hashing is O(n), so either" — a trade study: - memory ceiling in bytes rather than big-O; - access pattern (two sequential fronts versus random probes); - the read-only constraint; - determinism (worst-case linear versus expected); - and then the residual numeric risk with a concrete mitigation. The meta-lesson generalizes: when data already carries structure — here, sortedness — an algorithm that exploits it will usually beat one that rebuilds equivalent structure on the side.
- Why not binary-search each element's complement instead of converging pointers?It costs O(n log n) instead of O(n), and every search does about 30 scattered probes across the file, defeating prefetch and thrashing the page cache. Converging pointers issue strictly sequential reads from each end, which the storage and memory hierarchy reward. When the data is already sorted, the linear converging pass wins on both operation count and access pattern.
- The rewrite comparing a[lo] against target - a[hi] avoids the addition — is it automatically safe?No: the subtraction can overflow for the same extreme operands. Safe options are widening to a larger integer type, overflow-checked operations that flag or trap, or a case split on signs so each expression provably stays in range. The point to land is that you choose a strategy deliberately — no single algebraic rearrangement is overflow-free by default.
- What changes if new amounts keep being appended to the file?Appends break global sortedness, the pattern's precondition. A practical shape keeps a large sorted segment plus a small recent tail: converging pointers handle pairs within the sorted segment, the tail and cross-segment pairs are handled separately, and the tail is merged in periodically. Sortedness becomes a maintenance obligation you schedule, not a free assumption.
saying these in an interview costs you the question
- Reaches for a hash structure without pricing its memory in bytes at this scale
- Ignores that the input is read-only and already sorted
- Assumes 64-bit addition cannot overflow in practice
- Treats sequential versus random access as irrelevant to algorithm choice