|
Merge two arrays and sort them in order as specified at runtime ....
Microsoft Interview Questions and Answers
(Continued from previous question...)
91. Merge two arrays and sort them in order as specified at runtime ....
Question:
Merge two arrays and sort them in order as specified at runtime. The two arrays may share common entries between them, but the resultant array must not have duplicates.
Please define this with space and time complexity.
maybe an answer:
int MergeArrays()
{
//Assume inputs, C is destination but might not get filled till x+y and hence we return how much it is filled
A[x] B[y] C[x+y]
i=j=k=0;
while(i < x && j < y)
{
i = skipDupesWithinArray(A, i, x);
j = skipDupesWithinArray(B, j, y);
if(i == x)
{
return AssignRestArray(B, j, y, C, k);
}
if(j == y)
{
return AssignRestArray(A, i, x, C, k);
}
if(A[i] == B[j])
{
j++;
}
else if(A[i] < B[j])
{
C[k++] = A[i++];
}
else
{
C[k++] = B[j++];
}
}
return k;
}
int skipDupesWithinArray(Array H, int currPos, int maxNum)
{
while(currPos + 1 < maxNum)
{
if(H[currPos] == H[currPos] + 1)
currPos++;
}
return currPos;
}
int AssignRestArray(Array H, int currPos, int maxNum, Array X, int xPos)
{
while(currPos < maxNum)
{
X[xPos++] = H[currPos++];
currPos = skipDupesWithinArray(H, currPos, maxNum);
}
return xPos;
}
(Continued on next question...)
Other Interview Questions
| 