Sort an array according to the order defined by another array
Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order.
Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order.
Input: A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
A2[] = {2, 1, 8, 3}
Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}
The code should handle all cases like number of elements in A2[] may be more or less compared to A1[]. A2[] may have some elements which may not be there in A1[] and vice versa is also possible.
Given Code in: O(m*count + n) Space complexity O(m)
where m=size of A1,n=size of A2 count= maximum occurrence of any element of A1.
where m=size of A1,n=size of A2 count= maximum occurrence of any element of A1.
Company Asked : Amazon
#include <stdio.h>
#include <string.h>
int hash[1001]={0};
int main()
{
//case b>a
//int b[]={1, 3, 2, 8, 7, 1, 9, 3, 6, 8, 8};
//int a[]={2, 1, 1, 3};
//Output : 1 1 3 2
//simple case a>b
int a[]={2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8};
int b[]={2, 1, 8, 3};
//Output : 2 2 1 1 8 8 3 5 7 9 6
int al=sizeof(a)/sizeof(int);
int bl=sizeof(b)/sizeof(int);
int bmax=-1;
int i,j;
for(i=0;i<bl;i++){
hash[b[i]]=1;
bmax = bmax>=b[i]?bmax:b[i];
}//O(m)
for(i=0;i<al;i++){
if(hash[a[i]]>=0) ++hash[a[i]];
}//O(n)
printf("nInput n");
for(i=0;i<al;i++) {printf(" %d ",a[i]);}
printf("nOrder n");
for(i=0;i<bl;i++) {printf(" %d ",b[i]);}
printf("nOutput n");
for(i=0;i<bl;i++){
if(hash[b[i]]>1) {
--hash[b[i]];
while(hash[b[i]]--) printf(" %d ",b[i]);
}
}//O(m*count)
for(i=0;i<al;i++) {if(hash[a[i]]>0)printf(" %d ",a[i]);}
//O(n)
return 0;
}
PS: Instead printing elements we can store it in auxiliary array and finally assign auxiliary array to Input array as required by AMAZON Interviewer.
You can visit Working code at http://ideone.com/4R0Zj4