## Amazon Interview Question for Developer Program Engineers

• 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

so i thinks there must be enough space in a for b's elewments to store
code 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--];

}

}

Comment hidden because of low score. Click to expand.
0

Above 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;
}
}

Comment hidden because of low score. Click to expand.
0

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]+",");
}
}
}``````

Comment hidden because of low score. Click to expand.
0

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--];
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

Comment hidden because of low score. Click to expand.
0

no need for second while it should be if..

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nonsense you can merge two arrays within the same array unless you got extra space.

Comment hidden because of low score. Click to expand.
0

@wellsaid yes you can................ array a has more space and it can accomodate array b

Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

Comment hidden because of low score. Click to expand.
0

that might work, but heap enforces only weak ordering. so by reheapification you might break the sortedness of the first array?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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]);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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] ;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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]);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.