Amazon Interview Question
Software Engineer in TestsIn that case the complexity will be O(n+m) because first we put all the elements of array 1 in the hashtable and then we check the second array.
#include <set>
#include <algorithm>
#include <iostream>
using namespace std ;
int main() {
int a[] = {1,2,3,4,5,6} ;
int b[] = {3,4,7,1,9} ;
set<int> mySet(b, b+5) ;
cout << "\n Intersection :\t " << std::endl ;
for(int i=0 ; i<6; ++ i ){
if(std::binary_search(mySet.begin(), mySet.end(),a[i] ) )
std::cout << a[i] << "\t" ;
}
return 0 ;
}
@cacheMachine..I understand in your code is that you are creating a hashmap called map and adding all the arr[] values into it. When you write map.put(arr[i],i); , are the array elements added as keys or values?
And are you checking if the keys are same or the values as you have not mentioned if its is map.containskey() or map.containsvalue().
package practice;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class IntersectionOfArrays {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr = {3,6,7,4,9};
int [] brr = {2,8,1,7,0};
Hashtable ht = new Hashtable();
for(int i=0; i<5; i++)
{
ht.put(arr[i], i);
}
for(int i=0; i<5; i++)
{
int a;
a= brr[i];
if(ht.containsKey(a))
{
System.out.println("the array intersect");
}
else
{
System.out.println("the array does not intersect");
}
}
}
}
Sort one of the arrays with quick sort O(n*Log(n)).
Loop through the other array and if item exists in the other array include it in result(O(n*Log(n))
The algorithm will be O(n*Log(n)
If you loop the other array you have to traverse the full array. That means it is n * nlogn because you will run binary search for each of the item.
the most efficient solution is using hashtable for the 1st array.
- Anonymous July 20, 2011