Expedia Interview Question
Software Engineer / DevelopersYou don't even need the line "while(i>=0) arrayA[x--]=arrayA[i--];" in the end. If all B's elements have been accommodated before, the order of the remaining elements in A is still preserved.
Please correct me if I am wrong. It is assumed that the bigger array is having al the blank spaces in beginning.
Hi, we can merge two sorted arrays using this simple line of code ...
arr1 = Arrays.copyOf(arr1, len1+len2);
int i = len1 - 1;
int j = len2 - 1;
int x = len1 + len2 - 1;
while(i >= 0 && j >= 0) {
System.out.println(Arrays.toString(arr1));
if (arr1[i] >= arr2[j])
arr1[x--] = arr1[i--];
else
arr1[x--] = arr2[j--];
}
** we do not require the last 2 While Loops.. in any situation.
suppose there r two sorted arrays
1.A[n+m] where n elements are sorted and there are m
free spaces.
2.B[m] where m elements are sorted.
algo:
1.In array A there are m free spaces .
shift all the elements of array A
so that m free spaces would be in the biggining of
array A. It takes O(m) time
for(i=m+n-1;i>=n;i--)
A[i]=A[i-n];
2.now merge arrays A and B and store all the elements in A starting from A[0].
merging includes comparing of elements of A and B and putting smaller element in array A starting from A[0]
Ravi came up with the solution which will move the n elements to create space for the first element to capture.
Time = Shifting time + comparison and Moving time
.......= n +m+n
If we start filling from end like neo said, we can remove the shifting time overhead.
Time= comparison and Moving time
.......= n+m
@Neo - You code doesn't handle a case when one array got exahausted.
- When "b" get exhausted, Everything is in place, Exit
- When "a" get exhausted, move entire array from b to a.
My version of java Code
public class MergeTwoSortedArrays {
public static void main(String agrs[]){
//Integer[] array1 = {1, 1, 1, null, null, null};
//Integer[] array2 = {1, 1 , 1};
//Integer[] array1 = {1, 2, 3, null, null, null};
//Integer[] array2 = {4, 5 , 6};
//Integer[] array1 = {4, 5, 6, null, null, null};
//Integer[] array2 = {1, 2 , 3};
//Integer[] array1 = {1, 3, 5, null, null, null};
//Integer[] array2 = {2, 4 , 6};
Integer[] array1 = {2, 4, 6, null, null, null};
Integer[] array2 = {1, 3 , 5};
int array2Count1 = array2.length -1 ;
int array1Count1 = array1.length - array2.length - 1;
int arrayCount = array1.length - 1;
while (arrayCount > -1) {
if (array1Count1 > -1 && array2Count1 > -1) {
if (array1[array1Count1] >= array2[array2Count1]){
array1[arrayCount] = array1[array1Count1];
array1Count1--;
} else {
array1[arrayCount] = array2[array2Count1];
array2Count1--;
}
} else if (array2Count1 > -1){
array1[arrayCount] = array2[array2Count1];
array2Count1--;
}
arrayCount --;
}
for (array1Count1 = 0; array1Count1 < array1.length; array1Count1++ )
System.out.println(array1[array1Count1]);
}
}
My PHP Code :
<?php
$b = array(1,6,8,10,11,12);
$a = array(2,3,4,5,11);
$n = sizeof($a);
$m = sizeof($b);
$finalArray=array();
$j=0;
$k=0;
while($j<$n && $k<$m)
$finalArray[] = ($a[$j]>$b[$k]) ? $b[$k++] : $a[$j++];
//Rest
if($j<$n){
for($i=$j;$i<$n;$i++)
$finalArray[]=$a[$i];
}
if($k<$m){
for($i=$k;$i<$m;$i++)
$finalArray[]=$b[$i];
}
print_r($finalArray);
?>
I agree with Jimmy, here we need an in-place mergesort, which is O(n^2), check the following site for an in-place mergesort implementation:
www.cs.ubc.ca/spider/harrison/Java/MergeSortAlgorithm.java
I think the best soln is to swap the elements between the two arrays. So,
1) for each element in first array,
compare it with the first element in the second array
2) If the element in first array is greater than the first element in second array, swap the two.
3) When all elements in first array are done, copy the second array contents to first
O(n) time & O(1) space complaexity
I think the best soln is to swap the elements between the two arrays. So,
1) for each element in first array,
compare it with the first element in the second array
2) If the element in first array is greater than the first element in second array, swap the two.
3) When all elements in first array are done, copy the second array contents to first
O(n) time & O(1) space complaexity
hi nanmaga,
what if the elements which are being compared are equal? you can't swap in such a case. how can you handle this situation?
this is with regards to aaskkas idea.
int* mergeArrays(int*a, int* b) {
int *first=&a[n-1];
int *second=&b[m-1];
int *third=&a[m+n-1];
for(i=n+m-1; i>=0; i--){
if(*a>*b)
*c--=*a--;
else
*c--=*b--;
}
return(c);
}
can anyone let me if thihs works.
#include<stdio.h>
#define MAX 10
int arr1[2*MAX];
int arr2[MAX];
int main()
{
int i;
int j,temp;
int x;
for(i=0;i<MAX;i++)
{
arr1[i]=2*i+1;
arr2[i]=i*i+1;
printf("\n%d\t%d",arr1[i],arr2[i]);
}
for(i=MAX-1,j=MAX-1,x=2*MAX-1;j>=0 && i>=0; )
if(arr2[i]>arr1[j])
arr1[x--]=arr2[i--];
else
arr1[x--]=arr1[j--];
printf("\n");
for(i=0;i<(2*MAX);i++)
printf("%d ",arr1[i]);
return 0;
}
Java code to merge two sorted arrays where one of the arrays can accommodate the other.
public class MergeSortedArrays {
public static void main(String [] s){
//i have chosen 888 as a special number indicating space to be occupied
int[] a = {1,1,1,888,888,888};
int[] b = {1,1,1};
int i,j =0;
for (i=0;i<a.length;i++) {
while(j<b.length){
if(a[i] <= b[j]) {
i++;
} else {
for(int k=a.length-1;k>i;k--){
a[k] = a[k-1];
}
a[i]= b[j];
i++;
j++;
}
}
}
for (int l : a) {
System.out.print(l);
}
}
}
My version of java Code
public class MergeTwoSortedArrays {
public static void main(String agrs[]){
//Integer[] array1 = {1, 1, 1, null, null, null};
//Integer[] array2 = {1, 1 , 1};
//Integer[] array1 = {1, 2, 3, null, null, null};
//Integer[] array2 = {4, 5 , 6};
//Integer[] array1 = {4, 5, 6, null, null, null};
//Integer[] array2 = {1, 2 , 3};
//Integer[] array1 = {1, 3, 5, null, null, null};
//Integer[] array2 = {2, 4 , 6};
Integer[] array1 = {2, 4, 6, null, null, null};
Integer[] array2 = {1, 3 , 5};
int array2Count1 = array2.length -1 ;
int array1Count1 = array1.length - array2.length - 1;
int arrayCount = array1.length - 1;
while (arrayCount > -1) {
if (array1Count1 > -1 && array2Count1 > -1) {
if (array1[array1Count1] >= array2[array2Count1]){
array1[arrayCount] = array1[array1Count1];
array1Count1--;
} else {
array1[arrayCount] = array2[array2Count1];
array2Count1--;
}
} else if (array2Count1 > -1){
array1[arrayCount] = array2[array2Count1];
array2Count1--;
}
arrayCount --;
}
for (array1Count1 = 0; array1Count1 < array1.length; array1Count1++ )
System.out.println(array1[array1Count1]);
}
}
My version of java Code
public class MergeTwoSortedArrays {
public static void main(String agrs[]){
//Integer[] array1 = {1, 1, 1, null, null, null};
//Integer[] array2 = {1, 1 , 1};
//Integer[] array1 = {1, 2, 3, null, null, null};
//Integer[] array2 = {4, 5 , 6};
//Integer[] array1 = {4, 5, 6, null, null, null};
//Integer[] array2 = {1, 2 , 3};
//Integer[] array1 = {1, 3, 5, null, null, null};
//Integer[] array2 = {2, 4 , 6};
Integer[] array1 = {2, 4, 6, null, null, null};
Integer[] array2 = {1, 3 , 5};
int array2Count1 = array2.length -1 ;
int array1Count1 = array1.length - array2.length - 1;
int arrayCount = array1.length - 1;
while (arrayCount > -1) {
if (array1Count1 > -1 && array2Count1 > -1) {
if (array1[array1Count1] >= array2[array2Count1]){
array1[arrayCount] = array1[array1Count1];
array1Count1--;
} else {
array1[arrayCount] = array2[array2Count1];
array2Count1--;
}
} else if (array2Count1 > -1){
array1[arrayCount] = array2[array2Count1];
array2Count1--;
}
arrayCount --;
}
for (array1Count1 = 0; array1Count1 < array1.length; array1Count1++ )
System.out.println(array1[array1Count1]);
}
}
int i = n - 1, j = m - 1;
- bleh May 16, 2011int x = n + m - 1;
while(i >= 0 && j >= 0) {
if (arrayA[i] >= arrayB[j]) arrayA[x--] = arrayA[i--];
else arrayA[x--] = arrayB[j--];
}
while(i >= 0) arrayA[x--] = arrayA[i--];
while(j >= 0) arrayA[x--] = arrayB[j--];