For a quarter-turn board rotation on memory-tight devices, how do you choose in-place cycling over a fresh copy?
answer
- Two decisions hide inside one question
- Ask who still holds the original board
- Non-square changes the footprint's shape
- Transpose-plus-reverse allocates nothing either
- Constant factor versus review cost
basics
~20 sAsk first whether the original must survive and whether the board is square: those two answers usually decide it outright. Only when peak memory is genuinely the binding constraint is the harder in-place ring cycle worth its review cost, and transpose-plus-reverse is already in-place anyway.
solid answer
~50 sI separate two questions people merge. "In place or copy?" is a requirements question: if an undo stack, an animation that blends the old and new boards, or any other reader still holds the original, a copy is not overhead — it is the requirement. If the board is not square, in-place is impossible, because the rotated result has a different shape. "Ring cycle or transpose-plus-reverse?" is a separate implementation question, and the one candidates get backwards: transpose-then-reverse-each-row is *also* in-place, at the same `Theta(n^2)` cost, in two testable passes. The ring cycle buys one pass instead of two, priced in layer-and-offset arithmetic that is a known bug source. So I default to transpose-plus-reverse and adopt the cycle only if a measurement on real board sizes demands it, pinned by a property test against a copying reference.
go deeper
Know that a copy needs room for a second board while an in-place rotation reuses the first, and that a rectangular board rotates into a different shape. Say plainly whether the original is still needed.
Explain that transpose-plus-reverse is itself in-place, so the real comparison against ring cycling is two passes versus one at the same order of cost. Give the extra-space figure for each option.
Demonstrate the requirements questions first — surviving readers, board shape, peak footprint ceiling — then justify the implementation with a measurement and describe the tests that keep the harder version honest.
Own the whole call, including its cost to the team: default to the formulation that can be reviewed and re-derived, escalate only on evidence, pin any clever version with a property test against a reference, and record the rationale so the next engineer inherits a decision rather than a puzzle.
## Separate the two decisions The question sounds like one tradeoff and is really two, and merging them is what produces bad answers. **Decision 1 — must the transformation be in place at all?** This is set by requirements, not by taste: - *Does anything still hold the original?* An undo stack, an animation interpolating between the pre- and post-rotation board, a replay log, another component reading the same grid. If yes, you must produce a new board regardless; "saving" the copy would mean destroying data someone needs. - *Is the board square?* Rotating an `m x n` grid a quarter turn produces an `n x m` grid. The footprint changes shape, so there is no in-place option at all and the discussion is over. When you are copying anyway, skip the two-step decomposition and write each source cell directly to its destination in a single pass. - *What is the peak footprint budget?* A copy roughly doubles the grid's peak residency for the duration of the rotation. On a device with a hard ceiling, peak — not average — is what fails, and it fails as a crash rather than a slowdown. **Decision 2 — which in-place algorithm?** Only reached if decision 1 said in-place. And here is the correction most candidates need: **transpose-then-reverse-each-row is already in-place.** It never allocates a second grid. The genuine alternative is walking each concentric ring and cycling four cells at a time. ## Comparing the two in-place formulations | | Transpose + reverse each row | Ring cycle | |---|---|---| | Extra grid | none | none | | Time | `Theta(n^2)`, two passes | `Theta(n^2)`, one pass | | Index arithmetic | two independent, obvious loops | layer, offset, four coupled positions | | Testability | each half testable alone | all-or-nothing | | Odd side length | nothing to handle | innermost ring is the classic off-by-one | The asymptotics are identical, and both are optimal — every cell moves, so `Omega(n^2)` is a floor. The ring cycle's advantage is a constant factor: one traversal writing four cells per step instead of two traversals. That is a real difference, and it is also a difference that is invisible next to almost anything else a board-rendering path does. ## The organisational argument The ring cycle is not merely harder to write; it is harder to *review* and harder to *change*. Its loop bounds encode the layer count and the per-layer offset range, and every variant — a different rotation direction, a rectangular special case, a partial board — re-derives them. That cost lands on whoever touches the file in eighteen months, not on whoever writes it today. So the position I would defend to a team is: 1. **Default to transpose-plus-reverse.** It satisfies the memory constraint already, and its two halves can be unit-tested separately, which is the property that keeps it correct through later edits. 2. **Measure before escalating.** For puzzle boards of a few hundred cells, the entire rotation is noise against a single frame; a constant-factor win on a routine that does not appear in a profile is not a win. Escalate only when a measurement on real board sizes and real rotation frequency says the routine matters. 3. **If you adopt the cycle, pin it.** Keep a straightforward copying implementation in the test code as the reference oracle and assert the two agree on randomised boards, including odd side lengths, one-by-one and two-by-two. That is a property test, and it makes the clever version safe to keep. 4. **Write down which decision you made and why**, next to the code. The next person's instinct will be to "simplify" it back or to "optimise" it further, and a one-line rationale is what makes that a decision instead of a coin flip. ## The answers that sound senior but aren't - *"In-place is always better on constrained devices."* Not when the original is still needed — then in-place is a correctness bug wearing an efficiency costume. - *"Use the ring cycle to avoid allocating."* The two-pass recipe allocates nothing either. This conflates the two decisions. - *"It's O(n^2) either way so it doesn't matter."* Asymptotics are silent about constants, and constants are exactly what the second decision is about. The honest form is: it doesn't matter *until a measurement says it does*, which is a claim about your profile, not about the notation. - *"Rotate lazily by remapping indices on read."* A legitimate design — but it moves cost to every reader and complicates every other access; propose it as a design change with its own tradeoffs, not as a free win.
- A teammate argues the ring cycle is needed to avoid allocating — how do you respond?By separating the decisions. Transpose-then-reverse-each-row allocates nothing: both passes swap within the original square grid. So the ring cycle is not buying in-place-ness, it is buying one traversal instead of two — a constant factor. I would ask for a profile showing rotation on the hot path at real board sizes before trading two testable loops for coupled layer-and-offset arithmetic.
- What if the board is not square?Then in-place is off the table: the rotated result has the transposed shape, so it cannot occupy the original footprint. Allocate the destination of the new shape and write each source cell straight to its rotated position in one pass — the two-step decomposition exists to stay in place, and there is nothing left for it to buy once a copy is unavoidable.
- How would you keep the in-place version safe if you do adopt it?A property test against a straightforward copying implementation kept in the test code as the oracle: generate randomised boards, rotate both ways, assert equality. Cover odd and even side lengths explicitly, plus one-by-one and two-by-two. That converts a clever routine from a liability into one that can survive future edits by people who did not derive its bounds.
saying these in an interview costs you the question
- Assumes in-place is always the better choice
- Thinks only the ring cycle rotates without allocating
- Forgets a rectangular board changes shape when rotated
- Optimises a constant factor with no profile
- Ignores callers still holding the original board