4 ms·

You 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 o

by neilc 19y ago

You 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 ago
Doing p++, len-- uses two temporary variables.
- neilc 19y ago
  You 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 ago
      Yeah, 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 ago
        It 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 ago
        Well, 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).
        downer 19y ago
        You don't; it's basically, "here's an array, now reverse it" (keep in mind a pointer is not an array). http://www.lysator.liu.se/faq/c-faq/c-2.html http://www.lysator.liu.se/faq/c-faq/c-2.html The general point is that interviews of this type are counterproductive.
        neilc 19y ago
        An array can be variably-sized in C (C99, that is). And thank you, I know the difference between an array and a pointer. You just seem to have arbitrarily interpreted the question to limit it to C89 and a fixed-size array in order to make your solution work.
        downer 19y ago
        This has nothing to do with it being statically sized or variably sized. You have to know what size it is when you are going to reverse it. The solution presented works as long as the programmer knows what the size is. If you want to posit any kind of sane question, then you can have a sane solution.
        neilc 19y ago
        Well, suppose I have an array `A' of size `len'. How would you write an algorithm that reverses that array in place, without using any temporary variables, and that works for arbitrary values of A and len? I think the answer is "you can't". You can't claim to have a solution for the problem if it only works for a fixed input, and if the solution itself would be different for different inputs.

by neilc 19y ago

downer 19y ago

Doing p++, len-- uses two temporary variables.

neilc 19y ago
You 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 ago
    Yeah, 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 ago
      It 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 ago
        Well, 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).
        downer 19y ago
        You don't; it's basically, "here's an array, now reverse it" (keep in mind a pointer is not an array). http://www.lysator.liu.se/faq/c-faq/c-2.html http://www.lysator.liu.se/faq/c-faq/c-2.html The general point is that interviews of this type are counterproductive.
        neilc 19y ago
        An array can be variably-sized in C (C99, that is). And thank you, I know the difference between an array and a pointer. You just seem to have arbitrarily interpreted the question to limit it to C89 and a fixed-size array in order to make your solution work.
        downer 19y ago
        This has nothing to do with it being statically sized or variably sized. You have to know what size it is when you are going to reverse it. The solution presented works as long as the programmer knows what the size is. If you want to posit any kind of sane question, then you can have a sane solution.
        neilc 19y ago
        Well, suppose I have an array `A' of size `len'. How would you write an algorithm that reverses that array in place, without using any temporary variables, and that works for arbitrary values of A and len? I think the answer is "you can't". You can't claim to have a solution for the problem if it only works for a fixed input, and if the solution itself would be different for different inputs.