Expedia Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
4
of 4 vote

int i = n - 1, j = m - 1;
int 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--];

- bleh May 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brilliant and elegant code :D

- techG May 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You 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.

- Maggie January 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please correct me if I am wrong. It is assumed that the bigger array is having al the blank spaces in beginning.

- Newbee January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vrajendra April 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 Kant Pandey April 04, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if thr is any problem plz let me know

- Ravi Kant Pandey April 04, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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"
Think about it! If only the second element is space, you need n-1 times. If Every Other element is space, you need 1+2+3+...+(N-1) = N*(N-1)/4 which is O(N*N).

- kulang May 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

won't it be better to merge from the last and store frm the end

- aaskka's hub May 17, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is good to move first then merge from start only (m) moves require, as after merging we need to move (m+n) element, if follow merge from back

- Vishnu May 19, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Irrespective of fron or back the complexity is O(n2)!

- Jimmy December 10, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- YetAnotherCoder October 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
		
	}

}

- Hareesh February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

admin

- admin September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

?>

- Ashraf May 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- sunny December 11, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the arrays are already sorted, so it's not n^2!
merge from the end would be the best solution.

- rockets February 11, 2008 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Wat abt using Insertion Sort.....

- Puranik June 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nanmaga August 10, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nanmaga August 10, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- noviceprog September 02, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- neo September 25, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this swapping doesnt work ..

- Anonymous January 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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;
}

- RAJESH RANJAN September 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);
		}
	}
}

- sriniatiisc July 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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]);
		
	}

}

- Hareesh February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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]);
		
	}

}

- Hareesh February 22, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More