4 ms·
> like "How do your reverse an array without a temporary variable?" You hard-code it using XOR. Note you can't even do a for-loop, as that's using an extra va
by downer 19y ago
> like "How do your reverse an array without a temporary variable?"
You hard-code it using XOR. Note you can't even do a for-loop, as that's using an extra variable. Of course hand-unrolling a loop takes extra memory because it's so many extra lines so there's no point.
a ^= b
b ^= a
a ^= b
This is very unlikely to be something that occurs to programmers who haven't had to XOR recently; if you aren't writing your own hash or crypto or codec functions then you probably haven't used it in a while. Now that you've seen this, you'll remember it and so if anyone asks, you won't be figuring it out again, just recalling.
IMO it's a pretty useless way to weed people out, kind of like testing people on chess by random arrangements of pieces. Chess experts remember actual legal positions that occur in games much better than non-players, but they are no better at remembering positions that never occur -- a bunch of kings on a chessboard, some in adjacent squares, for example.
Likewise, this kind of pattern NEVER occurs in what most people program; it's just implausible.
- neilc 19y agoYou can use a for loop, if you step through the array with pointer arithmetic. On the assumption that you're given the array length (or else that the array is of fixed size), you don't need to hand-unroll the loop, which wouldn't handle a variably-sized array anyway. But I agree that it's a bad interview question.
- downer 19y agoDoing p++, len-- uses two temporary variables.
- neilc 19y agoYou don't need a temporary variable for "p" -- if the task is to write a function, you must have a pointer with the address of the start of the array, not an array variable as such. And yeah, you need some way to tell the length.
- downer 19y ago...and where you are in the array, hence the temp variable. Write it out to see. So it still doesn't work, even if you use a function to "cheat" and get a "free" pointer (which, by the way, wasn't what the task said).
- neilc 19y agoYeah, I suppose you'd need 1 temporary variable. Your solution doesn't work either, though: doing the freshman XOR trick some arbitrary fixed number of times just reduces to the XOR trick, which is plainly not what the task asked.
- downer 19y agoIt does work, you do the 3-step XOR with a[0] and a[last], then a[1] and a[last-1], etc. The 3-step XOR from the OP swaps the data. Here it is with a 4-element array, a[0] through a[3]: a=[100,200,300,400] a[0] ^= a[3] a[3] ^= a[0] a[0] ^= a[3] a[1] ^= a[2] a[2] ^= a[1] a[1] ^= a[2] a [400, 300, 200, 100] (Pretend this list is an array, it's just for illustrative purposes)
- neilc 19y agoWell, obviously the XOR swap works. But how do you use that to reverse an array of variable size? (i.e. where "last" isn't known at compile-time, so the number of swaps isn't known in advance).