Interview Questions

We have two sorted array.......

Microsoft Interview Questions and Answers


(Continued from previous question...)

116. We have two sorted array.......

Question:
We have two sorted array. Without using additional memory we need to merge these two arrays(second array is having more space for merging). Output should return through second array

I have gone through Mergesort from back to front and final data will be generated at the end of the second array.

This case second array or resultant array may have some empty spaces in the front. How to cleanup the empty spaces without using additional memory. That is additional question on the same algorithm


maybe an answer:


int A[5] = {1,3,8,9};
int B[9] = {2,4,5,6,7,0,0,0,0}; // last four as place holders for the merge

// start from the end of the larger array;
int idx = 8;
// we also need the indices of the largest elements in both arrays int idx_a = 3, idx_b = 4;

while (idx_a >= 0) { // done when A has been traversed
if (idx_b < 0 || A[idx_a] > B[idx_b]) { // if elements of b are exhausted
B[idx] = A[idx_a];
idx_a--;
}
else {
B[idx] = B[idx_b];
idx_b--;
}
idx--;
}

(Continued on next question...)

Other Interview Questions