Adobe Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
contains() method of ArrayList again iterates over the array , so how can you say that this algorithm performs O(n) operations . it does O(n^2) operations. please check once again and revert me back
Yes, I implemented the same with additional space, took a hashtable, a dictionary in fact... Below is the working solution (C# version)...
public ArrayList intersection_sorted_lists(int[] arr1, int[] arr2)
{
ArrayList alsort = new ArrayList();
int i=0;
Dictionary<int, bool> dic = new Dictionary<int, bool>();
foreach (int n in arr2)
{
if (dic.ContainsKey(n))
continue;
else
dic.Add(n, true);
}
for (i = 0; i < arr1.Length; i++)
{
if (dic.ContainsKey(arr1[i]))
alsort.Add(arr1[i]);
else
continue;
}
return alsort;
}
This can be done as:
1. Sort the smaller array.
2. Use binary search to find the elements of 2nd array in the first (sorted array).
Overall complexity O(n*log n) + O(m*log n)
If you are going to sort the arrays, you can find the intersection of arrays via 2-way merge instead of going for binary search. It's much simpler than the binary search. It doesn't reduce the complexity by any means but it will be much simpler..
If all numbers are positive we can also use
bitset
in C++. They are very efficient in terms of memory ( consumes ~120MB for +ve numbers upto 10^9 ). For eg.
bitset <1000000000> mSet
// set the num 'th bit
mSet.set( num )
....
// while checking for common element
if(mSet.test( num )
// do something
NOTE: mSet should be declared as global variable (using heap rather than stack memory)
static void Main(string[] args)
{
int[] array1 = { 1, 3, 5, 5, 4, 6, 7, 8, 9 };
int[] array2 = { 2, 3, 5, 10, 5 };
//int t =(array1.Max()>=array2.Max())?array1.Max():array2.Max();
Dictionary<int, int> result = new Dictionary<int, int>();
for (int i = 0; i < array1.Length; i++)
{
if (!result.ContainsKey(array1[i]))
result.Add(array1[i], 1);
else
result[array1[i]]++;
}
for (int i = 0; i < array2.Length; i++)
{
if (!result.ContainsKey(array2[i]))
result.Add(array2[i], 1);
else
result[array2[i]]++;
}
ArrayList t = new ArrayList();
for (int i = 0; i < result.Count; i++)
{
if (result.Values.ElementAt(i) >= 2)
t.Add(result.Keys.ElementAt(i));
}
foreach (var item in t)
{
Console.WriteLine(item.ToString());
}
Console.ReadLine();
}
Solution in C
/*
//Assumption:
1. Max Number in Array = 10000 - use HashFunction to optimize for space
2. No Negative Numbers - Should use a HashFunction to support this.
*/
/* Algorithm
1. COnvert one array to HashTable. with Key as the array elements and value as a magic number
2. Loop through the other array and if the hashTable look up has a magic number, then its an intersection
*/
int getIntersection( int array1[],int length1, int array2[],int length2, int resultArray[])
{
int i;
int hashTable[MAXVALUE] = {0}; //Initialize hashTable
int count = 0 ; //Size of return array
if(length1 == 0 || length2 == 0) return 0; // if either length is 0, return
//Convert one array to HashTable. Preferably smaller one.
//Optimization: You can use a hashFunction on integers is needed to save space.
for( i = 0 ;i < length1 ; i++)
hashTable[array1[i]] = 0xDEAD;
for( i = 0 ; i < length2; i++) {
if( hashTable[array2[i]] == 0xDEAD) {
//Intersection Found
resultArray[count++] = array2[i];
}
}
return count;
}
int main(int argc, char **argv)
{
int arr1[6] = {1,2,3,4,5,6};
int arr2[10] ={4,5,6,7,8,9,0,1,2,3};
int arr3[100];
int length3 = getIntersection(arr1,6, arr2,10, arr3);
printf("Intersection :\n");
for( int i = 0 ; i < length3; i++){
printf(" %d - ",arr3[i]);
}
printf("\n");
return 0;
}
static int[] a1(int[] a, int[] b)
{
int[] temp;
int ResultCount =0;
int count = 0;
if (a.Length > b.Length)
{
temp = new int[b.Length];
for (int i = 0; i < b.Length; i++)
{
count = 0;
for (int j = 0; j < a.Length; j++)
{
if (count > 0)
break;
if (a[i] == b[j])
{
++count;
temp[ResultCount] = a[i];
ResultCount++;
}
}
}
}
else
{
temp = new int[a.Length];
for (int i = 0; i < a.Length; i++)
{
count = 0;
for (int j = 0; j < b.Length; j++)
{
if (count > 0)
break;
if (a[i] == b[j])
{
++count;
temp[ResultCount] = a[i];
ResultCount++;
}
}
}
}
return temp;
}
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int>myset;
int n1,n2;
int a1[1000],a2[1000];
scanf("%d",&n1);
for(int i=0;i<n1;i++)
{
cin>>a1[i];
myset.insert(a1[i]);
}
scanf("%d",&n2);
set<int>::iterator it;
for(int i=0;i<n2;i++)
{
cin>>a2[i];
it=myset.find(a2[i]);
if(it!=myset.end())
cout<<*it;
}
return 0;
}
There are three methods to do this :-
1. Sort both the arrays and then find the intersection by comparing elements linearly.
2. Sort the smaller array, and for each element in the large array find whether the element is present in the array or not. If yes, then print the element.
3. Hashmap based solution :- Store the values of B array in a hashmap, and then check for each value in A, whether it's present or not.
- Kavitha March 20, 2014public class IntersectionOfArrays { public static void main(String[] args) { int[] array1 = { 1, 3, 5, 5, 4, 6, 7, 8, 9 }; int[] array2 = { 2, 3, 5, 10, 5 }; Set<Integer> unique = new HashSet<Integer>(); List<Integer> intersect = new ArrayList<Integer>(); for( int element : array1 ) unique.add(element); for( int element: array2 ) { if( ! unique.add(element) ) { if( ! intersect.contains(element) ) intersect.add(element); } } System.out.println( "Contents : " + intersect); } }