## Google Interview Question

Java Developers**Country:**United States

You need to swap 1 by 1, 2 by 2, 4 by 4, 8 by 8 and so on.

If you use shifting strategy it take O(n^2), using this strategy it takes O(n log n).

a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7

(a0) (a1) (a2) (a3) (a4) (a5) (a6) (a7) (b0) (b1) (b2) (b3) (b4) (b5) (b6) (b7)

(a0 b0) (a2 b2) (a4 b4) (a6 b6) (a1 b1) (a3 b3) (a5 b5) (a7 b7)

(a0 b0 a1 b1) (a4 b4 a5 b5) (a2 b2 a3 b3) (a6 b6 a7 b7)

(a0 b0 a1 b1 a2 b2 a3 b3) (a4 b4 a5 b5 a6 b6 a7 b7)

(a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7)

```
public static void changeArray(String[] arr){
if(arr.length ==0)
return;
int index = arr.length / 2;
while(index < arr.length){
String temp = arr[index];
int counter = index -1;
while(counter >= 0 && LessThan(arr[counter],temp)){
arr[counter+1] = arr[counter];
counter--;
}
arr[counter+1] = temp;
index++;
}
}
private static boolean LessThan(String a, String b){
return Integer.valueOf(b.charAt(1)) < Integer.valueOf(a.charAt(1));
}
```

```
public static void changeArray(String[] arr){
if(arr.length ==0)
return;
int index = arr.length / 2;
while(index < arr.length){
String temp = arr[index];
int counter = index -1;
while(counter >= 0 && LessThan(arr[counter],temp)){
arr[counter+1] = arr[counter];
counter--;
}
arr[counter+1] = temp;
index++;
}
}
private static boolean LessThan(String a, String b){
return Integer.valueOf(b.charAt(1)) < Integer.valueOf(a.charAt(1));
}
```

```
public static void rearrange(int[] arr) {
if (arr == null || arr.length % 2 == 1) return;
int currIdx = (arr.length - 1) / 2;
while (currIdx > 0) {
int count = currIdx, swapIdx = currIdx;
while (count-- > 0) {
int temp = arr[swapIdx + 1];
arr[swapIdx + 1] = arr[swapIdx];
arr[swapIdx] = temp;
swapIdx++;
}
currIdx--;
}
}
```

O(n) solution would be something as follows:

for each even element a_i in a, do the following:

index=i

while index <n : index=index*2-1

swap (a_index, b_(i/2))

while index !=i : swap (a_index,a_((index-1)/2)); index=(index+1)/2

Repeat for array b(1..n/2) b(n/2+1)

Total operations: n+n/2+n/4...=O(n)

You need to swap 1 by 1, 2 by 2, 4 by 4, 8 by 8 and so on.

- Nooreddin February 01, 2018If you use shifting strategy it take O(n^2), using this strategy it takes O(n log n).

a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7

(a0) (a1) (a2) (a3) (a4) (a5) (a6) (a7) (b0) (b1) (b2) (b3) (b4) (b5) (b6) (b7)

(a0 b0) (a2 b2) (a4 b4) (a6 b6) (a1 b1) (a3 b3) (a5 b5) (a7 b7)

(a0 b0 a1 b1) (a4 b4 a5 b5) (a2 b2 a3 b3) (a6 b6 a7 b7)

(a0 b0 a1 b1 a2 b2 a3 b3) (a4 b4 a5 b5 a6 b6 a7 b7)

(a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7)