CareerCup

single scan, logic start from end of arrays and compare

int[] top5LargestNumber(int[] A1,int[] A2,int[] A3)
{
int i,j,k,l=0;
int top5[];
if((A1.length + A2.length +A3.length) < 5)
 return 0;
i = A1.length -1;    // points to end
j = A2.length -1;
k = A3.length -1;

while(top5.length < 5) {
 large = Max(A1[i],A2[j],A3[k]) ;
 i-- if(large == A1[i])                  //decrement large pointer
 j-- if(large == A2[j])
 k-- if(large == A3[k])
 top5[l++] = large;
 }
return top5;
}

This is essentially the "merge" step in merge sort (for the k-merge problem), but which starts from the end of the array instead of the head of the array, and which stops when there are 5 elements already. So the "officially suggested" solution uses a max heap of size 3, and in each step it extracts the maximum, then fill the blank with the next element in the array that extracted max belongs to.

If the arrays are not sorted, the best sorting algo will take O(nlogn) time. and then the linear scan approach posted by venkatesh will work. In all it will take O(nlogn) only.

Use a min-heap of size 5. Insert the last 5 elements of first array into it.

Use the last 5 elements again from each of the remaining arrays. Insert the element into the heap if it is greater than the min-element of the heap by evicting the min-element.

i=size of first array
j=size of second array
k=size of third array
for(l=0;l<5;l++)
{
if(A1[i]>A2[j]&&A1[i]>A3[k])
{
ans[l]=A1[i];
i--;
}
else if(A2[j]>A1[i]&&A2[j]>A3[k])
{
ans[l]=A2[j];
j--;
}
else{
ans[l]=A3[k]
k--;
}
}

private static int[] ReturnMaxFive(int[] arr1, int[] arr2, int[] arr3)
{
int []rArr = new int[5];

if (arr1.Length + arr2.Length + arr3.Length < 5)
{
throw new ArgumentException("Length is less than 5");
}

int iArr1 = arr1.Length - 1;
int iArr2 = arr2.Length - 1;
int iArr3 = arr3.Length - 1;

int irARR = 0;

while (irARR < 5)
{
int max = int.MinValue;
int ArrayNum = 0;

if (iArr1 > 0 && arr1[iArr1] > max)
{
max = arr1[iArr1];
ArrayNum = 1;
}
if (iArr2 > 0 && arr2[iArr2] > max)
{
max = arr2[iArr2];
ArrayNum = 2;
} if (iArr3 > 0 && arr3[iArr3] > max)
{
max = arr3[iArr3];
ArrayNum = 3;
}

switch (ArrayNum)
{
case 1:
rArr[irARR] = arr1[iArr1];
iArr1--;
break;
case 2:
rArr[irARR] = arr2[iArr2];
iArr2--;
break;
case 3:
rArr[irARR] = arr3[iArr3];
iArr3--;
break;
}
irARR++;
}
return rArr;
}

private static int[] ReturnMaxFive(int[] arr1, int[] arr2, int[] arr3)
        {
            int []rArr = new int[5];

            if (arr1.Length + arr2.Length + arr3.Length < 5)
            {
                throw new ArgumentException("Length is less than 5");
            }

            int iArr1 = arr1.Length - 1;
            int iArr2 = arr2.Length - 1;
            int iArr3 = arr3.Length - 1;

            int irARR = 0;

            while (irARR < 5)
            {
                int max = int.MinValue;
                int ArrayNum = 0;

                if (iArr1 > 0 && arr1[iArr1] > max)
                {
                    max = arr1[iArr1];
                    ArrayNum = 1;
                }
                if (iArr2 > 0 && arr2[iArr2] > max)
                {
                    max = arr2[iArr2];
                    ArrayNum = 2;
                } if (iArr3 > 0 && arr3[iArr3] > max)
                {
                    max = arr3[iArr3];
                    ArrayNum = 3;
                }

                switch (ArrayNum)
                {
                    case 1:
                        rArr[irARR] = arr1[iArr1];
                        iArr1--;
                        break;
                    case 2:
                        rArr[irARR] = arr2[iArr2];
                        iArr2--;
                        break;
                    case 3:
                        rArr[irARR] = arr3[iArr3];
                        iArr3--;
                        break;
                }
                irARR++;
            }
           return rArr;
        }

#include <iostream>
#include <stdlib.h>

using namespace std;

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main(int argc, char** argv)
{
	int A1[7] = {2,4,9,16,19,68,78};
	int A2[7] = {4,8,67,106,109,115,120};
	int A3[7] = {9,15,19,108,119,130,190};

	int* tab = new int[21];
	for(unsigned int z=0; z<21; ++z)
	{
		if(z<7)
			tab[z] = A1[z];
		else if(z>=7 && z<14)
			tab[z] = A2[z-7];
		else if(z>=14 && z<21)
			tab[z] = A3[z-14];
	}
	qsort (tab, 21, sizeof(int), compare);

	for(int z=20; z>14; --z)
		cout << tab[z] << endl;
    return 0;
}