With less memory usage need to reorder the array elements

Question

I have a recent interview question, reordering of elements in an array with minimum memory usage. Not to use any additional variable or collections etc.

input:

value   65 7 1 68 90
index    0 1 2  3  4

output:

value   90 68 1 7 65
index    0  1 2 3  4

I'm not seeing the pattern here. Is this sorted in any way or just arbitrary order? — Daniel Kaplan, Aug 20 '13 at 18:41
Luis meant insertion sort - not search: http://en.wikipedia.org/wiki/Insertion_sort and your output is NOT ordered... — Nir Alfasi, Aug 20 '13 at 18:42
here inder 0 is moved to index 4 and index1 is moved to index 3 and vise versa, there followed some pattren — developer, Aug 20 '13 at 18:43
I know this might be too obvious, but why not simply loop through the array and swap values ? Is this "too much memory" ? Am I missing something ? — Dimitar Dimitrov, Aug 20 '13 at 18:44
If you have lets say `int a=1, b=2;` then after `b=a+0*(a=b);` `a=2` and `b=1`. But it is hard to say if that is what you are looking for. — Pshemo, Aug 20 '13 at 18:45
i given answer as , have one more index in the same object and move the values using this extra index, it not impressed. Does my answer is correct — developer, Aug 20 '13 at 18:45
@DimitarDimitrov how do you swap without creating a temp variable? — Daniel Kaplan, Aug 20 '13 at 18:45
@MohammadS. Yeah :) Honestly, if I see this in production I'd rewrite the hell out of it ! :) — Dimitar Dimitrov, Aug 20 '13 at 18:58
@dimitardimitrov I agree with you. This is one of those memory efficient questions that don't consider the readability of code. — But I'm Not A Wrapper Class, Aug 20 '13 at 19:01

score 5 · Accepted Answer · answered Aug 20 '13 at 18:47

You can use XOR to swap between elements (first with last, second with second from the end, etc) as follows:

int [] arr = {65, 7, 1, 68, 90};
for(int i=0; i<arr.length/2; i++){
    // the following 3 lines swap between elements arr[i] and arr[arr.length-i-1]
    arr[i] = arr[i] ^ arr[arr.length-i-1];
    arr[arr.length-i-1] = arr[i] ^ arr[arr.length-i-1];
    arr[i] = arr[i] ^ arr[arr.length-i-1];
}

for(int i=0; i<arr.length; i++){
    System.out.print(arr[i]+" ");
}

OUTPUT

90 68 1 7 65

Well if we are completely strict *i* is a variable. – Jose Da Silva Gomes Mar 12 '18 at 02:09 — Jose Da Silva Gomes, Mar 12 '18 at 02:09

Rohit Jain · Answer 2 · 2013-08-20T19:09:29.283

5

The main issue here is swapping array elements without using temp variable. You can make use of XOR(^) operation like this:

For swapping a and b:

int a = 4;
int b = 5;
a ^= b
b ^= a
a ^= b

Now, you just need to iterate over the array from index = 0 to index = length / 2, and swap elements at beginning and end.

edited Aug 20 '13 at 19:09

answered Aug 20 '13 at 18:48

Rohit Jain

209,639
45
409
525

2

The temporary values have to stored somewhere, so this won't use less memory than using a temporary variable. – Joni Aug 20 '13 at 18:49
1

@FDinoff. How would that make any difference? – Rohit Jain Aug 20 '13 at 18:51
See http://javarevisited.blogspot.cz/2013/02/swap-two-numbers-without-third-temp-variable-java-program-example-tutorial.html – Martin Podval Aug 20 '13 at 18:52
@Joni. I don't think the temporary results will be stored in any temporary variable. The result is directly assigned to existing variable. Check the byte code using `javap`. – Rohit Jain Aug 20 '13 at 18:57
The temporary result of XOR will be stored in a register, just like a temporary variable. You can check this by disassembling the output of the JIT compiler; byte code does not really tell you what the program is going to execute. – Joni Aug 20 '13 at 18:59
@Joni. Can you tell me how to disassemble the output of JIT compiler? I would really like to see what happens behind the scenes. – Rohit Jain Aug 20 '13 at 19:06
Welcome to the rabbit hole :) http://mechanical-sympathy.blogspot.com/2013/06/printing-generated-assembly-code-from.html – Joni Aug 20 '13 at 19:19
@Joni. Thank you so much. That is simply precious. But I see no Windows version there. I guess I need to open my Ubuntu now. :) – Rohit Jain Aug 20 '13 at 19:23
More info here, with a link to download the disassembler plugin for Windows x86: https://wikis.oracle.com/display/HotSpotInternals/PrintAssembly – Joni Aug 20 '13 at 19:37
@Joni. Thanks :) Was going through that link only. – Rohit Jain Aug 20 '13 at 19:41

score 2 · Answer 3 · edited May 23 '17 at 11:58

It looks like the elements are simply reversed. You can do this without additional arrays, with whatever implementation of the swap that you feel like using:

int b = 0, e = array.length-1;
while (b < e) {
    array.swap(b, e);
    b = b + 1;
    e = e - 1;
}

For integers you can use "storageless swap" by computing a sum and subtracting, by XORing, etc. One would never do that in production, though - it's a useless interview trick invented at the time when hardware engineers doubled as programmers more often than they do now (I saw this problem formulated in terms of hardware logical gates some 25 years ago).

"Not to use any additional **variable** or collections etc" – Daniel Kaplan Aug 20 '13 at 18:48 — Daniel Kaplan, Aug 20 '13 at 18:48

With less memory usage need to reorder the array elements

input:

output:

3 Answers3