Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
I feel that, here bigArrayIndex and smallArrayIndex should be checked for -1. If it is decremented beyond zero, it will lead to run time error.
thanks, I now see that the problem has to solved starting from the end of the arrays which makes things way easier
The above code will not work as it is, this check is required
if (smallArrayIndex < 0 || bigArrayIndex >= 0 && bigArray[bigArrayIndex] >= smallArray[smallArrayIndex])
These two conditions are missing in the while loop...from the above code... put this in the beginning of the while loop
if(bigArrayIndex<0 && smallArrayIndex>=0)
{
bigArray[currentIndex] = smallArray[smallArrayIndex];
smallArrayIndex=smallArrayIndex-1;
}
else if(smallArrayIndex<0 && bigArrayIndex>=0)
{
bigArray[currentIndex] = bigArray[bigArrayIndex];
bigArrayIndex=bigArrayIndex-1;
}
Merge an array of size n into another array of size m+n
September 5, 2009
Asked by Binod
Question:
There are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.
Input: array with m+n elements (mPlusN[]).
MergemPlusNNA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.
Input: array with n elements (N[]).
MergeN
Output: N[] merged into mPlusN[] (Modified mPlusN[])
MergemPlusN_Res
Algorithm:
Let first array be mPlusN[] and other array be N[]
1) Move m elements of mPlusN[] to end.
2) Start from nth element of mPlusN[] and 0th element of N[] and merge them
into mPlusN[].
Implementation:
/* Assuming -1 is filled for the places where element
is not available */
#define NA -1
/* Function to move m elements at the end of array
mPlusN[] */
void moveToEnd(int mPlusN[], int size)
{
int i = 0, j = size - 1;
for (i = size-1; i >= 0; i--)
if(mPlusN[i] != NA)
{
mPlusN[j] = mPlusN[i];
j--;
}
}
/* Merges array N[] of size n into array mPlusN[]
of size m+n*/
int merge(int mPlusN[], int N[], int m, int n)
{
int i = n; /* Current index of i/p part of mPlusN[]*/
int j = 0; /* Current index of N[]*/
int k = 0; /* Current index of of output mPlusN[]*/
while(k <= (m+n))
{
/* Take the element from mPlusN[] if
a) its value is smaller and we
have not reached end of it
b) We have reached end of N[] */
if((i < (m+n) && mPlusN[i] <= N[j]) || ( j == n))
{
mPlusN[k] = mPlusN[i];
k++;
i++;
}
else
{
mPlusN[k] = N[j];
k++;
j++;
}
}
}
/* Utility that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver function to test above functions */
int main()
{
/* Initialize arrays */
int mPlusN[9] = {2, 8, NA, NA, NA, 13, NA, 15, 20};
int N[] = {5, 7, 9, 25};
int m = 5, n = 4;
/*Move the m elements at the end of mPlusN*/
moveToEnd(mPlusN, 9);
/*Merge N[] into mPlusN[] */
merge(mPlusN, N, 5, 4);
/* Print the resultant mPlusN */
printArray(mPlusN, 9);
getchar();
}
Place 2 pointers at the end of each array and then compare the elements. The bigger one moves at the end of second array and then decrement the pointer which is pointing to big element. Repeat this step till you finish up with all the elements of the array.
Ex: first array 1 2 3 4 5 (n = 5)
Second array 3 5 6 7 8 9 10 (n = 5, m = 2) (As per the question second array size is big enough to hold elements from the first array. Hence size of it is 12)
Now have one pointer to 5 of first array, another pointer to 10.
Compare 5 and 10, move 10 to end of second array (ofcourse have to maintain pointer for this)
Decrement pointer to point to 9 in the second array.
Repeat this step until all the elements are done.
Here when we encounter same element twice while comparing, place that number twice and then decrement pointers of both array to point to prev element
Hope I am clear in explaining the algorithm
int A[m+n], B[n];
size_t i = m - 1, j = n - 1, k = m + n - 1;
while(i >= 0)
{
if(A[i] > B[j])
{
A[k--] = A[i--];
}
else
{
A[k--] = B[j--];
}
}
while(j >= 0)
{
A[k--] = B[j--];
}
public class MergeSortedArrays {
public static void main(String[] args) {
int[] smallArray = {1, 5, 7, 10};
int[] bigArray = {2,3,4,6,8,10,0,0,0,0};
int x = smallArray.length-1;
int y = bigArray.length-smallArray.length-1;
int z = bigArray.length-1;
while(z>=0) {
if(x<0) {
bigArray[z] = bigArray[y];
z--;
y--;
continue;
} else if(y<0) {
bigArray[z] = smallArray[x];
z--;
x--;
continue;
}
if(smallArray[x] > bigArray[y]) {
bigArray[z] = smallArray[x];
x--;
} else {
bigArray[z] = bigArray[y];
y--;
}
z--;
}
for(int i=0;i<bigArray.length;i++) {
System.out.print(bigArray[i]+" ");
}
}
}
Check if this code satisfies all the cases:
main()
{
int A[10],B[20];
int m,n;
printf("Enter the number of elements in A: ");
scanf("%d", &m);
printf("Enter array A: ");
for(int i=0;i<m;i++)
scanf("%d", &A[i]);
printf("Enter the number of elements in B: ");
scanf("%d", &n);
printf("Enter array B: ");
for(int i=0;i<n;i++)
scanf("%d", &B[i]);
int i=m-1,j=n-1;
int k=m+n-1;
while((i>=0)&&(j>=0))
{
if(A[i]>B[j])
{
B[k]=A[i];
i--;
k--;
}
else
{
B[k]=B[j];
j--;
k--;
}
}
if(i<0)
for(int x=j;x>=0;x--)
{
B[k]=B[x];
k--;
}
else if(j<0)
for(int x=i;x>=0;x--)
{
B[k]=A[x];
k--;
}
for(int x=0;x<(m+n);x++)
printf("%d ",B[x]);
}
Assuming m, n are the number of elems in a & b respectively.
void merge(int a[], int b[], int m, int n){
int lenA = m;
int lenB = n-m;
int mergeIndex = m+n-1;
int bIndex = lenB - 1;
int elemsLeftToMerge = lenA -1;
while(elemsLeftToMerge >= 0){
if(a[elemsLeftToMerge] > b[bIndex]){
b[mergeIndex--] = a[elemsLeftToMerge--];
}
else{
b[mergeIndex--] = b[bIndex--];
}
}
}
- Anonymous March 09, 2013