Given sorted arrays of length n and 2n with n elements each, merge first array into second array.

Question

Anónimo · Accepted Answer

Well, I assume that the values in the second array of length 2n is in the first n slots.

void merge(int[] a, int[] b) {
	int i = a.length - 1;
	int j = i;
	int k = b.length - 1;
	
	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			b[k] = a[i];
			i--;
		} else {
			b[k] = b[j];
			j--;
		}
		k--;
	}
	
	while (i >= 0) {
		b[k] = a[i];
		i--;
		k--;
	}
}

Anónimo · Answer

Few things I would do before actually starting up.

Assuming A is the n length array, B is the 2n length array, and the elements in B start at 0 to n-1.

If A[n-1] < B[0] Then move all the elements in B to the end of the array and copy A to the beginning of B.

If B[n-1] < A[0] do the opposite of above

If none of these apply, move up from B[0] to B[n] looking for when B[x] is higher than A[x]... do more stuff like this to have to avoid using Mergesort or any other sort that relies on a completely unsorted array. Use the information given to you and the restrictions put on the data to come up with speed increasing special cases.

Sumer Cip · Answer

Here is the Python implementation:

def m(A, B):
    c1 = len(e1)-1
    c2 = 2*len(e1)-1
    while(c2 > c1):
        B[c2] = max(A[c1], B[c1]) 
        B[c2-1] = min(A[c1], B[c1])
        c1 -= 1
        c2 -= 2

Nitish · Answer

#include
using namespace std;

int main()
{
int a[]={2,3,4,7};
int b[8]= {3,5,6,8};

int i1= 3,i2 =3,k =7,i;

while(k)
{

if(i1 =0 ; i--)
	 b[k--] = b[i];
	 k = 0;
	}
else if (i2 =0 ; i--)
	 b[k--] = a[i];
	k =0;
	}
else if (a[i1] >b[i2])
	{
		b[k--] = a[i1];
		i1--;
	}
else 
	{
		b[k--] = b[i2];
		i2--;
	}

}

for(i=0; i< 8; i++)
cout<

Sumer Cip · Answer

Two cases:
a) 2n array elements start from 0.
b) 2n array elements start from n/2.
Cases are symetric to each other. IMHO, the most beatiful answer to this question is to use the linked-list cycle detection concept where we have two pointers one is incrementing one and other is incrementing two. If those match then we have a cycle. In this example, if the case A is correct we can do following:

# Let A be n array, and B is 2n array
c1 = n-1
c2 = 2n-1
while(c2 > c1):
  if A[c1] > B[c1]: 
    B[c2-1] = B[c1]
    B[c2] = A[c1]
  else:
     B[c2-1] = A[c1] 
     B[c2] = B[c1]
  c1 -= 1 
  c2 -= 2

Implementation may have more specific details but the idea is obvious.

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo