## Expedia Interview Question for Java Developers

Country: India
Interview Type: Phone Interview

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

Sort the smaller of the two given arrays. O(log n)

Use Binary Search to search each element for the other array in the sorted one.

Total Time complexity O(n*log n + m*logn)

Comment hidden because of low score. Click to expand.
3

Good one. Sorting the smaller one and doing binary search in it is indeed better than sorting the larger and doing binary search in it.

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

With little extra space, it is possible to use hashing algorithms and find results in O(N) time as well.

Store shorter array in a different array using hashing technique, and find the another array's element into it.

Comment hidden because of low score. Click to expand.
0

Set approach is disallowed.

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

1. Sort the both arrays: 2NlogN
2. Search all the elements of an array in the other array using BST: NlogN

Total complexity : 3NlogN ==> NlogN !

Any other methods?

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

If the range of number is given (if they say that numbers lie between 0 to 10k), then we can use bit vector approach to do it with time complexity O(max(n1, n2)) and space complexity of O(min(n1,n2)). With bit vector approach, we would use only one bit (not byte) to mark the presence of an integer. Approach is : put smaller array in bit vector and then check the elements of larger array in bit vector.

Comment hidden because of low score. Click to expand.
0

Set approach is disallowed.

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

The size of the arrays shouldn't matter in this case since each bit represents an integer value. Regardless of the size of the array, you will need 1 bit for each integer in range.

As to the individual complaining that the Set approach is disallowed...see Java Set. What is described here is not a Set as I interpret it.

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.

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