Microsoft Interview Question
Software Engineer / Developersvoid merge(int * a, int na, int *b, int nb, int *c)
{
int i, aindex = 0, bindex = 0;
for(i = 0; i<na+nb;i++)
{
if(aindex<na && bindex < nb)
{
if(a[aindex] < b[bindex])
c[i] = a[aindex++];
else
c[i] = b[bindex++];
}
else
break;
}
if(aindex == na)
for(int j = i; j<na+nb;j++)
c[j] = b[bindex++];
else
for(int j = i; j<na+nb;j++)
c[j] = a[aindex++];
}
In Java (there is no need for an additional array):
public static void main(String[] args) {
int A[] = { 1, 3, 5, 6, 9 };
int B[] = new int[12];
B[0] = 3;
B[1] = 6;
B[2] = 8;
B[3] = 10;
B[4] = 11;
B[5] = 13;
B[6] = 15;
mergeInB(A, B, 7);
for (int n : B)
System.out.print(n + " ");
}
/**
* @param a
* @param b - it will be modified
* @param j = length of b
*/
public static void mergeInB(int[] a, int[] b, int j) {
int i = a.length - 1, k;
j --;
for (k = b.length-1; k >= 0; k--) {
if (i >= 0 && j >= 0) {
if (a[i] > b[j]) {
b[k] = a[i];
i --;
}
else
{
b[k] = b[j];
j --;
}
}
else break;
}
while(i>=0 && k >=0) {
b[k] = a[i];
k --;
i --;
}
while(j>= 0 && k >=0) {
b[k] = b[j];
j--;
k--;
}
}
This can be done in O(n) time using the merge procedure of MergeSort (Introduction to Algorithms)
- axmt December 30, 2006