After in-place compaction with a write pointer, why must the caller be given a returned length?
answer
- the array object never got smaller
- what still sits past the survivors
- who decides where valid data ends
- valid prefix, meaningless tail
- the write index is the length
basics
~10 sIn-place compaction never shrinks the array, so survivors occupy only a prefix and stale values still sit in the tail. The returned write count is the only signal of how many entries are valid.
solid answer
~40 sA compaction sweep copies every survivor forward to a `write` index and leaves the rest of the array untouched, so the array's physical length is exactly what it was before. After the sweep the region `[0, write)` holds the survivors in their original relative order, and `[write, physical_end)` holds leftovers — either values already copied further left in the same pass, or originals the sweep never overwrote. Nothing about those leftover slots is meaningful, and nothing cleared them. So the count is the contract: the caller must treat `(buffer, count)` as one value and stop iterating at `count`. If the caller loops over the whole physical array instead, it reprocesses records the pass was supposed to remove — the classic review defect on this kind of change.
go deeper
Be ready to say that an in-place removal does not change the array's own size, and that the return value is the count of surviving elements the caller must stop at.
Explain what actually occupies the slots past the returned count, and why a consumer that loops to the physical end reprocesses data the pass was meant to drop.
Show judgment about the contract you hand callers: buffer and count travel together, and decide deliberately whether leftover slots must be cleared or merely ignored.
Own the codebase rule that exactly one place defines where valid data ends. A raw mutable buffer with a separately passed length is a defect the team keeps paying for in bugs.
## What compaction actually does In-place compaction keeps one array and rearranges it so everything worth keeping ends up in a contiguous prefix. It is a two-index sweep: a `read` index visits every slot in order, and a `write` index marks where the next survivor belongs. When the element under `read` is kept, it is copied to `a[write]` and `write` advances; when it is dropped, `write` stays put and the next survivor will land on top of the hole. When the sweep ends, `write` equals the number of survivors. ## Two lengths, only one of which changed There are two different lengths in play, and confusing them is the whole question. - **Physical length** — how many slots the array has. The sweep cannot change this. A fixed-size buffer has the size it was allocated with; even a growable container is not resized by a loop that only assigns into existing slots. - **Logical length** — how many of those slots currently hold valid data. That is `write`, and it exists only as a number the sweep computed. After the sweep the array is in two regions: | Region | Contents | |---|---| | `[0, write)` | exactly the survivors, in their original relative order | | `[write, physical_end)` | unspecified leftovers | The tail is *not* "the removed elements, gathered up." It is whatever the sweep happened to leave: some slots hold values that were also copied further left, some hold originals no copy ever reached. Reading them is reading garbage that merely looks plausible, which is why the bug survives casual testing. ## The review scenario Picture a change that walks a settlement-record list already ordered by account and timestamp and collapses adjacent repeats of the same record. The sweep itself is correct. Two defects still show up in review: 1. **The function returns nothing.** The caller has no way to recover the logical length — it cannot be derived from the array, because the array is unchanged in size. The signature is broken regardless of how good the loop is. 2. **The caller iterates the physical length.** It stops at the array's own end rather than at the returned count, and cheerfully reprocesses the duplicate records in the tail. The removal "didn't work" — except it did; the consumer ignored the contract. A third, quieter one: a test that asserts on the *whole* array after compaction. The tail is unspecified, so such a test pins down incidental behaviour and breaks the first time the loop is optimised. ## Should you clear the tail? Clearing costs `O(physical_end - write)` extra writes and is optional. It earns its cost when: - the slots hold references to large objects that would otherwise stay reachable and unfreed — a leak of the "still referenced" kind, not of the "lost pointer" kind; - the slots held sensitive data you do not want lingering in a long-lived buffer; - the buffer is reused across passes and you want a later out-of-range read to fail loudly rather than plausibly. Otherwise, skip it: the count already says the tail is meaningless. ## How mainstream libraries frame the same split This is not an interview-only distinction. C++'s `std::remove_if` only shuffles survivors forward and hands back a new logical end that the caller must then `erase`; Python's filtering comprehension takes the opposite route and allocates a fresh list, leaving the original untouched. Two mainstream answers to the same question — *who owns the truncation* — and the in-place answer always makes the length something the caller must carry. ## Costs The sweep is `O(n)` time and `O(1)` extra space, with at most `n` element copies. Building a filtered copy instead is `O(n)` time and `O(n)` space, but leaves the source intact and hands back a container whose own length is already correct. On a memory-constrained device that second option may simply not exist, which is exactly why the in-place contract has to be understood rather than avoided. ## What an interviewer is listening for That you say "the array is the same size; the count is the answer," that you can describe what is in the tail without guessing that it was cleared, and that you treat the buffer plus its count as a single unit when you hand it to anyone else.
- Should the sweep also clear the stale tail, and when does that matter?Usually not — the count already declares the tail meaningless, and clearing costs an extra write per leftover slot. Clear it when the slots hold references to large objects that would otherwise stay reachable, when they held sensitive values you do not want lingering in a reused buffer, or when you want a later out-of-range read to fail loudly instead of returning plausible garbage.
- How would you make it impossible for a caller to read past the valid prefix?Stop handing back a bare buffer plus a separate number. Return a bounded view or a pair that the consumer cannot destructure by accident, so the length travels with the data and every read is bounded by construction. If the API must expose the raw buffer, keep the count next to it in the same type and make the iteration helper the only supported way to walk it.
- What should the test assert after a compaction pass?Assert on the returned count and on the prefix it describes — the exact survivors, in the original relative order. Do not assert on the slots past the count: their contents are unspecified, so pinning them freezes incidental behaviour and breaks the first time the loop changes.
It is like crossing names off a printed guest list by rewriting the survivors from the top of the page: the page is still the same length, and the old lines further down are still legible until someone is told where the real list ends.
saying these in an interview costs you the question
- Says the array itself shrinks after in-place removal
- Iterates the full physical array after compaction
- Assumes leftover tail slots were cleared automatically
- Believes the tail holds the removed elements in order
- Treats leftover duplicates in the tail as proof the sweep failed