CareerCup

Merge in descending order.

Hint: Start Merging from End

Pseudo-Code:

for( i = A.length, j = A.size, k=B.size; j>=0 && k>=0 ; i--)
{
if( A[j] >= B[k] )
	A[i] = A[j--];
else
	A[i] = B[k--];
}

where size is no of elements in each array
and length is actual length of the array (including the extra space)

/*
Assume the interviewer here expects to also have the merged array to stay sorted, after merge. Else, the problem is pretty straight forward.
*/
private static int[] Merge(int[] A, int[] B)
{
	if(A==null || B==null || A.count==0 || B.count==0)
		return A; // Nothing to do.
	//Assume A has exact no. of empty spaces to Accomodate B, at the end.
	int sizeFullA=A.count;
	int sizeA=A.count - B.count; // A.size - element places for B at the end.
	int sizeB=B.count;
	int ptrA=sizeA-1; // Maintain 2 temporary ptrs for A & B starting from last element
	int ptrB=sizeB-1;
	for(int i=sizeFullA-1;i>=0&& ptrB>=0;i--)
	{
		if(
			ptrA<0  || Copy over the B elements, if A is exhausted.
			B[ptrB]>A[ptrA]) // If B the current element in B is larger, copy the B elemnt to i-index
		{
			A[i}=B[ptrB];
			ptrB--;
		}
		else
		{
			A[i]=A[ptrA];
			ptrA--;
		}			
	}
	return A;
}

1) Start with last element of each array ( A (larger) & B (Smaller))
2) If A[n] > B[n] --> Copy A[n] to A[2n] and decrease index of A .
else
--> Copy B[n] to A[2n] and decrease its index.
3) Repeat step 2 till one of the array gets empty ..... then copy other in reverse fashion.

void mergeArray(int* arr1, int n1, int* arr2, int n2)
{
	int i, j, k;

	i = n1-1;
	j = n2-1;
	k = n1+n2-1;

	while(i>=0 && j>=0 && k >= 0)
	{
		if(arr1[i] >= arr2[j])
		{
			arr1[k] = arr1[i];
			--k; --i;
		}
		else
		{
			arr1[k] = arr2[j];
			--k; --j;
		}
	}
	while(i>=0)
	{
		arr1[k--] = arr1[i--];
	}
	while(j>=0)
	{
		arr1[k--] = arr2[i--];
	}
}

Let:
a = no of elements in the larger array
b = no of elements in the smaller array
m = size of large array
n = size of small array
Initially a pointer p1 points to 1st index of larger array and p2 points to last+1 th index of larger array

1) Transfer the elements of the smaller array into the remaining part of larger array
2) Place the n shortest element of the largest array in the small array. Suppose the second pointer p2 has moved x indices.
3) Shift values in the indices n-x to n (of larger array) downward by x.
4) Move all the contents of small array to 1st n indices of large array. Step 2,3 and 4 took a time of O(n).
5) Repeat Step 2, 3 and 4 until the point p1 reaches a or p2 reaches m
6) The whole operation took a time of O((m/n)*n) = O(m)

public static void Merge(int[] A, int[] B)
        {
            if (A == null || B == null)
                return;
            if (A.Length > B.Length)
            {
                Merge(B, A, B.Length, A.Length - B.Length);
            }
            else
            {
                Merge(A, B, A.Length, B.Length - A.Length);
            }
        }
        private static void Merge(int[] min, int[] max, int minCount, int maxCount)
        {
            int i = minCount - 1, j = maxCount - 1;
            int m = max.Length - 1;
            while (i >= 0 && j >= 0)
            {
                if (min[i] > max[j])
                {
                    max[m] = min[i];
                    i--;
                }
                else
                {
                    max[m] = max[j];
                    j--;
                }
                m--;
            }
            if (j == -1)
                Array.Copy(min, max, i + 1);
        }

MS IDC makes fool of people.
People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.

Do take the feedback from employees before joining MS.

And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.

public int[] MergeArray(int[] a, int[] b)
{
int marker;
marker = a.Length - b.Length;

int x = 0;
int i =0;
for (; i < a.Length-1; i++)
{
if (a[i] >= b[x])
{
int y=marker;
while (y > i)
{
a[y] = a[y - 1];
y--;
}
a[i] = b[x];
x++;
marker++;
}
}

while (x < b.Length)
{
a[marker] = b[x];
x++;
marker++;
}

return a;
}