In a heap-based k-way merge, which two boundary conditions crash the naive loop?

## The fragment The merge loop is short enough that candidates write it confidently and then get cut on the edges. The version below merges k timestamp-sorted log sources into one feed, and it is wrong in two specific places: ``` h = new min-heap for i in 0..k-1: insert(h, (src[i][0], i, 0)) while size(h) > 0: (v, i, p) = extract_min(h) emit(v) insert(h, (src[i][p+1], i, p+1)) ``` ## Bug one: the empty source at seeding `src[i][0]` assumes every source has a first element. In a fleet of 200 servers, at least one has been idle since the last rotation and its log is empty. Reading element 0 of an empty sequence is an out-of-bounds read. The fix is a guard in the seed loop: insert only if the source is non-empty. The consequence is worth saying out loud — **the heap does not necessarily start with k entries**. Any later logic that assumes "the heap holds exactly k until sources start draining" is now wrong too. Candidates who patch only the read and leave that assumption elsewhere have half-fixed it. ## Bug two: the exhausted source at refill `src[i][p+1]` assumes source i still has an element after position p. It will not, for every source, exactly once — at the moment that source's last element is emitted. Because that happens k times over the run, this is not an exotic edge case; it is guaranteed. The fix is a guard on the refill: push the successor only if `p+1 < length(src[i])`. Otherwise push nothing and let the heap shrink by one. The heap's size therefore decreases monotonically once sources begin to drain, which is exactly what makes the loop terminate. ## Why termination then needs no extra bookkeeping With both guards in place, `while size(h) > 0` is a complete and correct termination condition. The heap holds one entry per source that still has unemitted data; when it empties, every source has been drained and every element emitted. No counter, no sentinel, no per-source "done" flags. That matters because the common third bug is replacing the heap check with a precomputed count: "I know there are N lines total, so I will loop N times." It works only while your idea of N is exact. Any source shorter than assumed and the loop reads past the end of the heap; any source longer and you truncate the feed silently — the worse failure, because it produces plausible output. ## The sentinel alternative, and why it is a trap here A classic trick in older merge code is to pad each source with a sentinel value larger than any real key, so the refill never needs a guard. With a heap that backfires: sentinels are ordinary entries, they get extracted like anything else, and unless the emit step filters them they appear in the output. You have traded a boundary check for a filtering step plus a new correctness assumption — that no real key can exceed the sentinel. With timestamps, someone's clock skew eventually violates it. Guarding the refill is simpler and has no such assumption. ## The related-but-different mistake: losing the source identifier The fragment stores `(value, source index, position)`, which is what makes both the refill and the guard expressible. A version that heaps bare values compiles and even produces correct-looking output for a while — you can still extract minima — but there is no way to advance the right source, so people patch it by re-scanning all k sources for the emitted value. That is `O(k)` per element, quietly turning `O(N log k)` back into `O(N*k)`, and it breaks outright on duplicate timestamps, where the re-scan cannot tell which source's copy was just emitted. ## What an interviewer is listening for 1. You name **both** guards without being prompted, and you know the second one fires k times, not rarely. 2. You notice that the empty-source guard invalidates the "heap always has k entries" assumption. 3. You use heap-emptiness for termination rather than a counter. 4. You keep the source identifier in the entry and can say what breaks without it. A candidate who writes the loop correctly but cannot say *when* the exhaustion branch is taken has memorised it; a candidate who says "once per source, and the last one empties the heap" has understood it.