## Amazon Interview Question

Developer Program EngineersAbove code does not work. I tried following which works,

void Merge(int a[],int n,int b[],int m)

{

int i,j;

int k=n+m-1;

i=n-1;

j=m-1;

while(k>=0)

{

if(a[i]<b[j])

{

a[k]=b[j];

k--;

j--;

}

else

{

a[k]=a[i];

k--;

i--;

}

}

//Print the array..

for(int i = 0;i<n+m;i++)

{

cout << a[i] << endl;

}

}

Guess the while loop should run until k>0

```
public class MergeArrays {
public static void main(String args[]){
int a[]={1,3,5,0,0,0};
int [] b={2,4,6};
merge (a,3,b,3);
print (a);
}
public static void merge(int[] a,int m,int[] b,int n){
int i=m-1;
int j=n-1;
int k=m+n-1;
while(k>0){
if(a[i]<b[j]){
a[k]=b[j];
k--;
j--;
}
else{
a[k]=a[i];
k--;
i--;
}
}
}
public static void print(int[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+",");
}
}
}
```

All code above have a bug.

ie. a = {1,2,3, , , ,} b ={4,5,6}

j will decrement to -1 while i is still 2

next loop, you are comparing a[2] to b[-1],

the correct code should be

void Merge(int a[],int n,int b[],int m)

{

int i,j;

int k=n+m-1;

i=n-1;

j=m-1;

while(i>=0 && j>=0)

{

if(a[i]<b[j])

{

a[k--]=b[j--];

}

else

{

a[k--]=a[i--];

}

}

while(j>=0) {

a[k--] = b[j--];

}

}

@jigar @geeks

u both coded it correctly. Let me make it more readable.

this code gives u the soln in O(n) complexity

void merge(int a[],int b[], int M)

{

int i=M-1,j=M-1,k=M+M-1;

while(i>=0 && j>=0)

{

if(a[i]>b[i])

a[k--]=a[i--];

while(a[i]<=b[i])

{

a[k--]=b[j--];

if(j<0)

break;

}

}

}

cheers

Treat array a[] as Heap. Insert element from b[] on by one at the end of array a[] and then re-heapify. The complexity is O(log(A+B))

Just an idea...assuming array 'a' has enough space to hold all the elements from array 'a' and 'b'(so 'a' has to be a dynamic array'), first append all the elements from 'b' to 'a' and apply a merge sort. For example

Step 1:

a[] = { 1, 3, 5, 7, 9,...., n}

b[] = { 2, 4, 6, 8, 10,...., m}

Step 2:

now append b to a

a[] { 1, 3, 5, 7, 9,...., n, 2, 4, 6, 8, 19, ...., m}

step 2 takes O(n + m)...for convenience let's say x = n + m i.. O(x)

Step 3:

apply merge sort on the modified array a whose length is "X" now

and we know the merge sort complexity is Xlog(x)

Finally, I think I could say x + xlogx ----> xlogx (ignoring the x)

What do you guys say?

#include<stdio.h>

int main()

{

int a[10]={1,2,4,6,8};

int b[5]={

3,5,7,9,10

};

int i=4;

int j=4;

int k=9;

while(i>-1 || j>-1)

{

if(a[i]>b[j])

{

a[k]=a[i];

i--;

}

else

{

a[k]=b[j];

j--;

}

k--;

}

if(i==-1 && j!=-1)

{

while(j!=-1)

{

a[k]=b[j];

j--;

k--;

}

}

for(i=0;i<10;i++)

{

printf("%d\n",a[i]);

}

}

2-way merge backward...

```
Void MergeSort( int a[], int lena, int b[], int lenb )
{
int a_tail = lena – 1;
int b_tail = lenb – 1;
int ab_tail = lena + lenb – 1;
while( a_tail >= 0 && b_tail >= 0 )
{
if ( a[a_tail] >= b[b_tail] )
a[ab_tail--] = a[a_tail--];
else
a[ab_tail--] = b[b_tail--];
}
// if a[] finished first, copy b[] left to a[]
if (a_tail == -1)
while( b_tail >= 0 )
a[b_tail] = b[b_tail] ;
}
```

```
#include <stdio.h>
#include <string.h>
int main()
{
int a1[5] = {1, 2, 3, 4, 5};
int a2[10] = {2, 4, 6, 8, 10, 0};
int i = 4;
int j = 4;
int k = 9;
while((i >= 0) && (j >= 0))
{
if(a1[i] < a2[j])
{
a2[k] = a2[j];
j--;
}
else
{
a2[k] = a1[i];
i--;
}
k--;
}
while(i >= 0)
{
a2[i] = a1[i];
i--;
}
for(i=0; i<10; i++)
printf("%d\t", a2[i]);
}
```

so i thinks there must be enough space in a for b's elewments to store

- geeks July 25, 2011code if it is what i think

void Merge(int a[],int n,int b[],int m)

{

int i,j;

k=n+m-1;

i=n-1;

j=m-1;

while(i>0 &&j>0)

{

if(a[i]<b[j])

{a[k--]=a[i];

i--;

continue;

}

else

a[k--]=b[j--];

}

}