CareerCup

merge backward.

1) As the arrays are sorted we can try this
2) Push the elements of b to the end of the array
3) B[null,null,null,null,null, 2,4,8,10,11,15]
4) Compare a[0] to b[5] i.e. compare 1 and 2
5) 1 is smaller push it into b[0] and increment the winner
6) Compare a[1] and b[5] i.e. compare 3 and 2
7) Of course 2 is smaller add 2 to b[1] and increment the winner to b[6]
8) Compare a[1] and b[6] i.e. compare 3 and 4
9) 3 is smaller copy it to b[2] and increment the winner to a[2]
10) Now compare a[2] and b[6] I e compare 5 and 4
11) Copy 4 to b[3] and increment b
12) Compare 5 and 8 copy 5 to b[4] increment a
13) Compare 7 and 8 copy 7 to b[5]
14) Compare 9 and 8 copy 8 to b[6]
15) Compare 10 and 9 copy 9 to b[7]
16) If array 1 has ended
17) Copy 10 to b[8]
18) Copy 11 to b[9]
19) Copy 15 to b[10]
B[11]={1,2,3,4,7,6,7,8,9,10,11,15}

Its like inserting elements in B from A and doing the second step of insertion sort.

<pre lang="java" line="1" title="CodeMonkey57027" class="run-this">int[] mergeArrays(int[] a, int[] b){
int emptyIndex = b.length-1;
int curB = 0;
int curA = a.length-1;
for(int i=b.length-1;b>=0; b--){//find the first non-empty slots of b from end
if(b[i]!=null){
emptyIndex = i+1;
curB = i;
break;
}
}
while(curA>=0 && curB>=0){
if(a[curA]>b[curB]){
b[emptyIndex--] = a[curA--];
}
else{
b[emptyIndex--] = b[curB--];
}
}

if(curA!=0){
while(curA>=0){
b[emptyIndex--] = a[curA--];
}
}
return b;
}</pre><pre title="CodeMonkey57027" input="yes">
</pre>

public static void main(String[] args) {
String [] inputA = {"1","3","5","7","9"};
String [] inputB = {"2","4","8","10","11","15",null,null,null,null,null};
int[] inputC = new int [inputB.length];
int[] output = new int[inputB.length];

int j = 0, k = 0;

for(int i=0; i<=inputB.length-1; i++){
if (inputB[i] == null) {
inputC[i] = Integer.parseInt(inputA[j]);
j++;
}
else{
inputC[i] = Integer.parseInt(inputB[k]);
k++;
}
}
output = mergeSort(inputC);
System.out.println(Arrays.toString(output));
}

Use that "code template" as a prototype to solve the coding problem:

...
	list< int > ls1;
	list< int > ls2;
	list< int >::iterator li;
	list< int >::reverse_iterator rli;
	ls1.clear();
	ls2.clear();
	li = ls1.begin();
	ls1.insert( li, 11 );
	ls1.insert( li, 11 );
	ls1.insert( li, 12 );
	ls1.insert( li, 12 );
	ls1.insert( li, 13 );
	ls1.insert( li, 13 );
	li = ls2.begin();
	ls2.insert( li, 21 );
	ls2.insert( li, 21 );
	ls2.insert( li, 22 );
	ls2.insert( li, 22 );
	ls2.insert( li, 23 );
	ls2.insert( li, 23 );
	cout << "Unsorted List 1:" << endl << "\t";
	for( li = ls1.begin(); li != ls1.end(); li++ )
		cout << *li << " ";
	cout << endl;
	cout << "Unsorted List 2:" << endl << "\t";
	for( li = ls2.begin(); li != ls2.end(); li++ )
		cout << *li << " ";
	cout << endl;
	ls1.unique();
	ls2.unique();
	ls1.merge( ls2 );
	ls1.reverse();
	ls1.sort();
	cout << "Merged, Sorted, Duplicates removed List 1:" << endl << "\t";
	for( li = ls1.begin(); li != ls1.end(); li++ )
		cout << *li << " ";
	cout << endl;
	ls2 = ls1;
	cout << "Reversed List 2:" << endl << "\t";
	for( rli = ls2.rbegin(); rli != ls2.rend(); rli++ )
		cout << *rli << " ";
	cout << endl;
	ls1.clear();
	size_t i;
	for( li = ls2.begin(), i = 0; li != ls2.end(); li++, i++ )
	{
		if( i % 2 )
			ls1.push_back( *li );
	}
	ls2 = ls1;
	cout << "Collapsed List 2:" << endl << "\t";
	for( li = ls2.begin(); li != ls2.end(); li++ )
		cout << *li << " ";
	cout << endl;
	ls1.clear();
	ls2.clear();
...

Assumption here is that firstArray and secondArray are not null
For simplicity, null in secondArray is replaced with 0

int[] mergeSortedArrays(int[] firstArray, int[] secondArray) {
        if (firstArray == null || secondArray == null) {
            return secondArray;
        }

        int secondIndex = 0;
        int firstIndex = firstArray.length - 1;
        for (secondIndex = secondArray.length - 1; secondIndex >= 0;secondIndex--) {
            if (secondArray[secondIndex] != 0) {
                break;
            }
        }

        int insertIndex = secondArray.length - 1;

        while (secondIndex > -1 && firstIndex > -1) {
            secondArray[insertIndex--] = secondArray[secondIndex] > firstArray[firstIndex] ?
                    secondArray[secondIndex--] : firstArray[firstIndex--];
        }

        while(insertIndex >= 0) {
            secondArray[insertIndex--] = firstArray[firstIndex--];
        }

        return secondArray;
    }