Amazon Interview Question
Software Engineer / DevelopersTeam: 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...