## Amazon Interview Question

Software Engineer / Developers**Team:**SDE

**Country:**India

**Interview Type:**In-Person

1st take the array as a1a2...b1b2... only dont take c1c2...

then divide the array into 4 parts as

part 1 : a1a2..a(n/2)

part 2 : a(n/2+1)....an

part 3 : b1 b2... b(n/2)

part 4 : b(n/2+1)....bn

now swap p1 p3 and p2 p4 then

repeat from above

so problem is divided into sub problems . Use recursion

think in the same way for a1b1a2b2... with c1c2...

```
public void merge(int[] a, int begin, int n) {
if (n == 1) return;
int p1 = begin;
int p2 = p1 + n;
int p3 = p2 + n;
int b = a[p2];
int c = a[p3];
for (int i = p3-1; i > p2; i--) {
a[i + 1] = a[i];
}
for (int i = p2-1; i > begin; i--) {
a[i + 2] = a[i];
}
a[begin + 1] = b;
a[begin + 2] = c;
merge(a, begin + 3, n - 1);
}
```

1st take the array as a1a2...b1b2... only dont take c1c2...

- kasireddi February 04, 2012then divide the array into 4 parts as

part 1 : a1a2..a(n/2)

part 2 : a(n/2+1)....an

part 3 : b1 b2... b(n/2)

part 4 : b(n/2+1)....bn

now swap p1 p3 and p2 p4 then

repeat from above

so problem is divided into sub problems . Use recursion

think in the same way for a1b1a2b2... with c1c2...