Interview Question
Country: United States
Merge from backwards... thats it
void merge( int s[] , int size1, int d[] , int size2 )
{
int s_end = size1-1;
int d_end = size2 - size1 -1;
int d_max = size2 -1 ;
while(d_max >= 0 )
{
if ( s_end >= 0 && d_end >=0 )
{
if ( s[s_end] < d[d_end] )
{
d[d_max] = d[d_end];
d_end--;
}
else
{
d[d_max] = s[s_end];
s_end--;
}
d_max--;
}
if(d_end < 0 )
{
while( s_end >= 0)
{
d[d_max] = s[s_end];
s_end --;
d_max--;
}
}
}
}
two arrays:
first 1 2 3 4 5 6 7
second 2 6 7
1. have two pointers first_pointer and second_pointer and it is pointing to first and second respectively.
2. compare them and put it in the longest array.
compare(1, 2) first array[] = 1 first_pointer pointing to 2 now.
compare(2, 2) first array[] = 1 2 2 first_pointer pointing to 3 & second_pointer to 6
compare(3, 6) first array[] = 1 2 2 3 first_pointer pointing to 4 & second_pointer to 6
so on.....
This will take a lot of time, I think O(m^2), because you will be shifting the elements. I gave a similar solution but the interviewer was not satisfied and demanded an optimized solution which will take O(n+m).
#include<iostream>
using namespace std;
#define Size1 7
#define Size2 12
int main(){
int arr1 [] ={-3,-1,4,4,6,11,13};
int arr2[] ={-2,0,11,48,49,0,0,0,0,0,0,0}; // works for -ve as well as +ve integers as well as 0. Also works for duplicate values .
int low1 =0;
int high1 = Size2-Size1-1; // the index of last element in array2 .
int copyLow1= low1;
int copyHigh1 = high1;
for(int i=0; i<Size1;){
int num1 = arr1[i];
low1= copyLow1;
high1= copyHigh1;
while(low1<=high1){ // find the index in the senond array to insert the ith element from first array
int mid = (low1+high1)/2;
if(arr2[mid] > num1)
high1 =mid-1;
else
low1 = mid+1;
}
if(low1>copyHigh1){ // the element in array1 is greater than the last element of array2 so now fill array2 with array1
for(int z = copyHigh1+1;z<Size2;z++)
arr2[z] = arr1[i++];
break;
}
int low2 = i;
int high2 = Size1-1; // last index of 1st array .
int compareWith = arr2[low1];
while(low2<=high2){ // to calculate how many numbers from array1 can be shifted to array2 at once .
int mid = (low2+high2)/2;
if(arr1[mid]>=compareWith)
high2 = mid -1;
else
low2 = mid+1;
}
int noOfShifts = low2 - i ; // noofshifts = number of elements from array1 which will be moved to array2 .
for(int j = copyHigh1;j>=low1;j--){ // shift array2 elements by the noofshift calculated
arr2[j+noOfShifts] = arr2[j];
}
for(int k =0 ;k<noOfShifts;k++){ // insert the array1 elements into array2 .
arr2[low1+k] = arr1[i+k];
}
i = i+noOfShifts;
copyLow1 = copyLow1 + noOfShifts;
copyHigh1 = copyHigh1 + noOfShifts;
}
for(int i =0;i<Size2;i++) // Print the result
cout<<arr2[i]<<" ";
return 0;
}
This can be done by comparing the last elements of both array and place the higher one at the end of the second array. Below is the C code with complexity O(m+n),
- Mehul June 02, 2013