Even computer programmers can get it wrong, and even reify the wrongness into interview questions. The correct answer to the common question of "how do you reverse an array" is that you don't reverse it. You read it backwards. Details vary from language to language; languages with iterators can find this particularly easy. But this is often not the "correct" answer according to the interviewer.

In the end, all data structures are functions. The academic applications of that may make your eyes glaze over, but the practical application is that if you want a reversed array/tree/etc., you just need the reading/iteration "function" for the array to return the data as if it was reversed. A matrix can be "transposed" just by reading its transpose. (Caching or other consequences may result in you choosing to manifest it in memory anyhow, but if it was stored cleverly in the first place, or you're only going to read it once anyhow such that using it once is as expensive as reading it once to reconstruct it anyhow, then there's no reason to.) An array can be randomly permuted simply by wrapping the read function with a permutation on the index, it need not be manifested in memory. etc.

The "invert binary tree" interview question can be solved by swapping the accessors of the node type:

  tmpfn = tree.left
  tree.left = tree.right
  tree.right = tmpfn

Now when tree.left(node) is applied, it returns the right child, and vice versa. All traversals use the accessors, QED.

> The correct answer to the common question of "how do you reverse an array" is that you don't reverse it. You read it backwards.

This only works if you can easily find the end during iteration. Which you cannot in e.g. the case where you reverse a part of a larger array and want to keep the result contiguous.

If you don't know what the end of your array is, you've got bigger problems.

I also don't understand why people seem to think that all you can do is maybe write one line of code or something. You can write as much code as it takes. Presumably, you know, not thousands and thousand just to read the array backwards or in some funky order, but you're not limited to calling the standard-library-provided "reverse" function and giving up if it doesn't exist.

These protests that "I can't do that because I'm just so helpless" make no sense to me. Read the array in whatever order you want, whenever you want. It's not that hard. It's just about the easiest thing there is. (Too much vibe coding?)

> If you don't know what the end of your array is, you've got bigger problems.

That's called “a pointer”. Not all ways of representing arrays and spans come with explicit lengths.

> These protests that "I can't do that because I'm just so helpless" make no sense to me. Read the array in whatever order you want, whenever you want. It's not that hard. It's just about the easiest thing there is. (Too much vibe coding?)

I don't know why you think I am too helpless to write it; I've never said such a thing. I have never used AI to write code in my life, and I'm perfectly able to write code to both reverse an array and read it backwards (in multiple languages, thank you). But sometimes, you _actually want to reverse it_ because it makes other parts of the code more convenient and/or faster.

I defy you to name an environment in which it is impossible to read an array from backwards to forwards.

That's an array, as in, things already in memory. Not a stream. An array. A collection of fixed-size-in-RAM elements, contiguously in order.

That is not "an environment which doesn't provide a one-liner to do it". C, for instance, may not provide a backwards iterator, but then, it doesn't exactly provide a forwards iterator either. It is trivial to iterate backwards on an array in C. To the extent that it's a pain to provide a function that does it either way, that's C's problem, not the fact it can't be done. Everything's a pain in C.

Cache coherency is not an issue here either because I have specified it as being read once and already called out that if you're going to read it multiple times it may be worth it. Reading it once to do whatever it is you are doing is faster than reading it once, writing it in a new order, then reading it in that new order, at least on anything remotely resembling real, existing hardware.

Uh, no, you're missing the point. It's always possible for you to reverse the array and read it backwards. After all, that's how you are capable of reversing it! The problem is that the thing that you are handing it to might not be capable of that. You can't pass an array to write(2) and tell it to actually print it in reverse order. You can't mmap a page where first byte of data is actually at the high address. Your DMA engine won't flip your buffer for you. If you want to use these APIs, you have to reverse the array before you hand it to them. There's just no way around it.

Also, I do want to note that just because your language is higher level and takes iterators or sequences or whatever abstraction you have on top of "a bunch of elements" doesn't actually mean that reversing an array is never worth it. It is often the case that your API/compiler/language will support passing in an arbitrary "view", but if you actually try to do this you will find that it can only fully reason about the "forward, contiguous" buffer case, which it will optimize well. If you pass it anything funny it will fall back to the element-by-element code which can be an order of magnitude slower, or more (usually this means no vectorization, for example). In this case it's often better to pull out an optimized reverse and then pass a normal array to the API. Even though it would read the data twice this can still be a lot faster.

I see this a lot in graphics, where people will for example say to create a view matrix you first create your camera transform and then invert it. When the better solution is to just directly construct the inverted matrix.

There is almost never a good reason to invert a full 4x4/3x3 transform, yet I see it all the time.