Amazon Interview Question
Software Engineer / Developers<pre lang="" line="1" title="CodeMonkey21388" class="run-this"> public class MergeAandB
{
public int[] Merge(int[] A, int[] B)
{
//Arrange all place holders at the end
int indxStartPh = 0, indxEndPh = 0;
for (; A[indxStartPh] != -1; indxStartPh++) ;
indxEndPh = indxStartPh;
for (; A[indxEndPh] == -1 && indxEndPh < A.Length; indxEndPh++) ;
while (indxEndPh < A.Length-1)
{
if (A[indxEndPh+1] != -1)
{
//swap with indx start place-holder
A[indxStartPh++] = A[indxEndPh + 1];
A[indxEndPh++ + 1] = -1;
}
//find the end of current place holders block
else
{
for (; A[indxEndPh] == -1 && indxEndPh < A.Length; indxEndPh++) ;
}
}
//merge arrays: A and B
int indexA = indxStartPh - 1;
int indexB = B.Length - 1;
int sortIndex = A.Length - 1;
while (indexB>=0 && indexA>=0)
{
//merge A
if (A[indexA] >= B[indexB])
{
A[sortIndex--] = A[indexA];
A[indexA--] = -1;
}
//merge B
else
{
A[sortIndex--] = B[indexB--];
}
}
while (indexB >= 0)
{
A[sortIndex--] = B[indexB--];
}
return A;
}
}</pre><pre title="CodeMonkey21388" input="yes">
</pre>
Here is the most efficient VBA code with test arrays
-----------
Sub Arr2()
Dim l1, l2, l3 As Integer
l1 = 4 'sorted 1
l2 = 3 'sorted 2
l3 = l1 + l2 '
Dim aR1(4) As Integer
Dim aR2(7) As Integer
aR1(0) = -32768
aR1(1) = -3
aR1(2) = 7
aR1(3) = 9
aR2(0) = -2
aR2(1) = 7
aR2(2) = 16
'Compare the largest sorted elemets of arrays and move the largest to the last empty space
'So
'l1 is position of current largest element of array 1
'l2 is position of current largest element of array 2
'l3 is position of empty space for the next largest element
Do While l1 > 0 And l2 > 0
If aR1(l1 - 1) > aR2(l2 - 1) Then
aR2(l3 - 1) = aR1(l1 - 1)
'Move to the next largest position
l1 = l1 - 1
Else
aR2(l3 - 1) = aR2(l2 - 1)
'Move to the next largest position
l2 = l2 - 1
End If
'Move Empty space for the next largest element
l3 = l2 + l1 'same as l3 = l3 - 1
Loop
'If all elements fro Array 1 checked and processed(i.e l1 = 0) we are done
'But if Array 1 has some elements left we need just to move them to beginning of array2 one by one
'Array2 has empty spaces ready for them!!!
Dim i As Integer
For i = 0 To l1 - 1
aR2(i) = aR1(i)
Next
For i = 0 To 6
Debug.Print aR2(i)
Next
'Clean array1 if you wish
ReDim aR2(4)
Exit Sub
1. collapse all the spaces in the first array starting from the end (two indices needed to keep track of start and end of the continuous free space) - takes O(n) time.
- Lumberjack July 14, 20112. merge two arrays - takes O(n) time.