CareerCup

Start merging from end.

Start at i=X and j=Y in the first and second array respectively. Whichever number is bigger, store at k=X+Y in the second array.
Repeat above operation till you exhaust one array. If you exhaust 2nd array, copy the contents of 1st array. If you exhaust 2nd array, no need to copy.

#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int a1[4] = {4,5,13,22};
int a2[7] = {12,16,21};

int m = 4, n=3, size=7;

int i=m-1, j=n-1, k=size-1;

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

while(i >= 0)
a2[k--] = a1[i--];

return 0;
}

Good Question!!

same wz asked to me at microsoft interview in seattle (2nd rounds.. ) ;P

public class Program
{
public static int[] x = { 1,4,10 };
public static int[] y = { 2,8,-1,-1,-1}; //assume -1 is not initialized

public static void Main(string[] args)
{
int lastIndex = y.Length-1;
int yElementCount = (y.Length - x.Length);

int xPointer =x.Length-1;
int yPointer= yElementCount -1;

while (xPointer >=0 || yPointer >=0)
{
if (xPointer < 0)
{
y[lastIndex--] = y[yPointer--];
continue;
}

if (yPointer < 0)
{
y[lastIndex--] = x[xPointer--];
continue;
}


if(x[xPointer] >= y[yPointer])
{
y[lastIndex--] = x[xPointer--];
}
else
{
y[lastIndex--] = y[yPointer--];
}
}


Console.WriteLine();

}

}

Start from x and y index respectively.Compare last element of both and which one is greater,put it on a[x+y-1].After it decrease the index of array
x+y=p;
a[x];
b[x+y];
compare a[x-1] and b[y-1]
if(a[x-1]>b[y-1]){
b[p-1]=a[x-1];
x--;
p--;
}
if(a[x-1]<b[y-1]){
b[p-1]=b[y-1];
y--;
p--;
}

There is a better way. We have to do an insertion sort into the bigger array, but we can be clever about finding the slot where to insert. In the solutions given previously, the number of comparisons in the worst case will be O(n^2) considering both the arrays are of length n.

If we use Binary Search to locate the slot to insert, we can reduce the complexity to NLogN.

Use Heap. Complexity O(logn)

good question

//merging to sorted arrays
#include <stdio.h>
#include <conio.h>
int main()
{ int l1=5,l2=8,c=0;
int j=l2-1;
int a[5]={1,3,5,7,8};
int b[13]={0,2,4,6,8,9,10,12};
for(int i=l1-1;i>=0;i--)
{
while(b[j]>=a[i])
{ b[l1+l2-1-c]=b[j];
j--;
c++;
}
b[l1+l2-1-c]=a[i];
c++;
}
for(int i=0;i<l1+l2;i++)
{
printf("%d\n",b[i]);
}
getch();
return 0;
}

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int main()
{

int a[4]={3,4,6,9};
int b[10]={1,2,5,7,10,12,0,0,0,0};

int x=(sizeof(a)/sizeof(int)),y=(sizeof(b)/sizeof(int));
printf("the value of x and y are :%d %d \n",x,y);

int i=x-1,j=5,cnt=0,max=y-1;

while(max>=0)
{

if(b[j] > a[i])
{
b[max]=b[j];
max--;
j--;
}//end of if
else
{
if(i>=0)
{
b[max]=a[i];
max--;
i--;
//j--;
}//end of if
else
break;
}//end of else

}

for(i=0;i<y;i++)
printf("%d\n",b[i]);

getch();
return 0;
}

<pre lang="" line="1" title="CodeMonkey56923" class="run-this">
public class MergeApp {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arrayA[] = {23,47,81,95};
int arrayB[] = {7,14,39,55,62,74};
int arrayC[] = new int[10];

Merge(arrayA,4,arrayB,6,arrayC);
Display(arrayC,10);

}
public static void Merge(int [] arrayA, int sizeA, int [] arrayB, int sizeB, int [] arrayC)
{
int a = 0, b = 0, c = 0;
while(a<sizeA && b<sizeB)
{
if(arrayA[a] < arrayB[b])
arrayC[c++] = arrayA[a++];
else
arrayC[c++] = arrayB[b++];
}

while(a < sizeA)
arrayC[c++] = arrayA[a++];

while(b < sizeB)
arrayC[c++] = arrayB[b++];
}
public static void Display(int[]arrayC, int sizeC)
{
for(int i = 0 ; i < sizeC; ++i)
System.out.println(arrayC[i]);
}

}</pre><pre title="CodeMonkey56923" input="yes">
</pre>

public class Programms
{
private static int[] a = {8, 9,15,20, 0,0,0,0,0};
private static int[] b = {2,4,9, 16,67};

public static void main(String[] args)
{
mergeTwo();

for(int i = 0 ; i < a.length ; i++)
{
System.out.println(a[i] );
}

}
private static void mergeTwo()
{
int m = 3, n =4;
int i = m+n +1;
while(m != -1 && n != -1)
{
if(a[m] <= b[n])
{
a[i] = b[n];
n--;
}
else
{
a[i] = a[m];
m--;
}
i--;
}
if( m == -1 && n !=-1)
{
while(n != -1)
{
a[i] = b[n];
n--;
i--;
}
}

}
}

Note that both arrays are heaps by default. Merge heap 1 into heap2 and do heapsort. Complexity is O(nlogn)

package mirco;

public class MergeArrayXtoArrayXPlusY {

public static void main(String[] args) {

int[] a = { -111, -2, 1, 23, 45, 67, 99 };
int[] b = { -1, 2, 11, 78, 1000, 0, 0, 0, 0, 0, 0 };

merge(a, b);

for (int i : b) {
System.out.println(i);
}

}

public static void merge(int[] arr1, int[] arr2) {

int x = arr1.length - 1;
int y = arr2.length - arr1.length - 1;
int z = arr2.length - 1;

while (x >= 0 && y >= 0 && z >= 0) {

int valx = arr1[x];
int valy = arr2[y];

if (valx >= valy) {
arr2[z] = valx;
x--;
} else {
arr2[z] = valy;
y--;
}
z--;

}

while (x >= 0) {
arr2[z] = arr1[x];
z--;
x--;
}

while (y >= 0) {
arr2[z] = arr2[y];
z--;
y--;
}
}

}