After an in-place partition splits payroll rows into contractors and employees, is the original row order preserved?
answer
- think about what a swap does to two distant rows
- the predicate cannot tell same-category rows apart
- constant extra space and order-keeping pull against each other
- one buffer pass keeps order but doubles memory
- staying in place costs a logarithmic time factor
basics
~20 sNo. In-place partition schemes are unstable: they exchange rows across long distances, so rows within each group come out reordered. Preserving order costs O(n) extra space in one pass, or O(n log n) time in place.
solid answer
~50 sSwap-based partitioning is unstable by construction. A single exchange can take a row from the far end of the file and drop it into an early slot, so two contractor rows that were adjacent in the input can end up in either order. Any downstream code that assumed "contractors still appear in file order" is relying on an accident, and it will pass on small or already-grouped inputs and fail later. Getting stability costs something concrete: one pass that appends matches and non-matches to two buffers and concatenates them is stable in `O(n)` time but `O(n)` extra space; staying in place forces a divide-and-conquer scheme with rotations at `O(n log n)` time. The other fix is to stop depending on incidental order — carry the row's original position as an explicit tiebreak field so the ordering requirement is written down rather than inherited.
go deeper
Be ready to say that an in-place swap partition may reorder items within a group, and that only the group boundary is guaranteed.
Explain why exchanging distant elements destroys relative order, and name the two prices of stability: extra space in linear time, or staying in place at n log n.
Show the diagnosis and the fix: how the dependency slipped through testing, and why making the ordering contract explicit in the data usually beats swapping in a stable algorithm.
Own the call under a memory ceiling — doubling peak memory versus a slower, harder-to-maintain in-place scheme versus renegotiating the downstream requirement entirely.
## What stability means here A partition is **stable** if, within each of the two output regions, elements keep the relative order they had in the input. It is a promise about elements the partition predicate cannot tell apart — every contractor row looks identical to a test that only asks "contractor or employee?", so stability is the only thing that can decide their order. Note the direction of the promise: stability says nothing about the two regions relative to each other, and nothing about any ordering *within* a region beyond "as it was". If the rows carry no payload anyone can distinguish, stability is meaningless and free to ignore. ## Why swap-based passes are unstable The in-place schemes work by exchanging elements that are far apart. When the sweep finds a contractor row late in the file and a slot for it early, one swap relocates it — and relocates whatever was in that early slot to the late position. Two rows that were neighbours can end up on opposite ends of their region, and the outcome depends on where the pivot or predicate boundary happened to fall. There is no ordering discipline anywhere in the algorithm to violate, because none was ever established. The three-way in-place split has exactly the same property for the same reason. So does every scheme whose selling point is `O(1)` extra space: constant extra space and stability are in genuine tension, because preserving order in general requires somewhere to park elements you are not ready to overwrite. ## What stability costs | Approach | Time | Extra space | Stable? | |---|---|---|---| | In-place swap partition | `O(n)` | `O(1)` | No | | Two-buffer pass, then concatenate | `O(n)` | `O(n)` | Yes | | In-place divide-and-conquer with rotations | `O(n log n)` | `O(log n)` stack | Yes | | Compaction sweep with a write frontier | `O(n)` | `O(1)` | Only for the kept side | The two-buffer pass is the one most teams actually reach for: walk the file once, append each row to one of two collections, then join them. It is trivially stable, trivially reviewable, and it doubles peak memory for the collection — which is exactly the constraint that made someone pick the in-place version in the first place. The in-place stable version buys the memory back by paying a logarithmic factor in time through repeated rotations, and it is markedly harder to read. This is a place where mainstream ecosystems visibly made different calls on the same concept: some standard libraries expose an unstable in-place partition as the default plus a separate stable variant documented as needing extra memory or extra time, while languages whose partition operation returns two freshly built collections — the functional-library style seen in Rust and Haskell — get stability for free precisely because they paid `O(n)` memory up front and never swap anything. ## The senior judgment The interesting part of this question is not the cost table, it is what you do when review turns up code depending on the accident. Three moves, in rough order of preference: 1. **Make the requirement explicit.** If downstream genuinely needs file order, that is an ordering contract, and contracts belong in the data: carry the original row index as a field and let the consumer order by it. Now the requirement survives someone swapping the partition implementation next quarter. 2. **Buy stability deliberately**, with the cost written down. Choose the two-buffer pass if the memory ceiling allows it; choose the in-place rotation scheme only if it does not, and only if the team can maintain it. 3. **Delete the dependency.** Very often nothing actually needs the order — the consumer was just reading rows in whatever sequence they arrived and someone wrote a test that pinned it. That test was asserting an implementation detail. ## Why this bug survives testing An unstable algorithm is not required to reorder anything; it is merely permitted to. On a five-row fixture, on already-grouped input, or when every row happens to fall on the same side, an unstable pass returns the input order and the test goes green. The bug shows up when the file grows, when the interleaving changes, or when someone swaps one partition scheme for another with identical output guarantees. The way to catch it is to test what the algorithm actually promises: build an input with many rows in each category, each carrying a distinct sequence number, and assert the *region boundaries* — not that the sequence numbers are still ascending, unless stability is a documented requirement, in which case assert exactly that.
- When does the stability of a partition not matter at all?When elements in the same region are indistinguishable to every consumer — plain keys with no payload, or records whose remaining fields nobody reads in order. Stability is a promise about elements the predicate cannot separate, so if nothing downstream can separate them either, the promise buys nothing and you should take the cheaper unstable pass.
- How would you catch this class of bug in tests rather than in production?Build an input with many rows in each category, interleaved, each carrying a distinct sequence field, and assert the property you actually rely on. Small or pre-grouped fixtures pass by luck because an unstable pass is permitted to preserve order, not forbidden from it. If order is a real requirement, assert it explicitly so the next implementation swap fails loudly.
- What does buying stability with O(n) extra space cost at real scale?Peak memory for the collection roughly doubles during the pass, which is often the exact constraint that motivated an in-place approach. On a large in-memory dataset or a memory-capped fleet that can be decisive, and the alternative — an in-place stable scheme built from rotations — trades the memory back for an `O(n log n)` running time and code that is meaningfully harder to review.
Dealing a shuffled deck into two piles by colour keeps every card's arrival order only if you place them down one by one; if instead you swap distant cards in the stack to group them, the colours separate but the sequence within each colour is gone.
saying these in an interview costs you the question
- Assumes partitioning is stable because a small test looked ordered
- Says stability and constant extra space cost nothing to have together
- Confuses stability with each region being sorted
- Thinks reversing one region afterwards restores the input order
- Treats a passing fixture as proof of an ordering guarantee