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