## Adobe Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

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

``````public 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 )

for( int element: array2 ) {
if( ! unique.add(element) ) {
if( ! intersect.contains(element) )
}

}

System.out.println( "Contents : " + intersect);

}

}``````

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

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

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

@Ramesh BG Hashset contains is O(1)

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

You can solve it in linear time. You need extra space.
Store the elements of array B in hashmap with values as keys.
traverse through array A. If the element is found in the hashmap include it in the output array.

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

With extra hash: Do as kid of kop, time linear, space linear
Without extra memory: Sort both array & merge routing, time nlgn, space const.

{ Output array is always needed so you can't include that as part of space complexity }

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

With extra hash: Do as kid of kop, time linear, space linear
Without extra memory: Sort both array & merge routing, time nlgn, space const.

{ Output array is always needed so you can't include that as part of space complexity }

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

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
}

for (i = 0; i < arr1.Length; i++)
{
if (dic.ContainsKey(arr1[i]))
else
continue;
}

return alsort;``````

}

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

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)

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

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

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

@Kid of Kop: We need not to sort both the arrays. We will sort the array having less number of elements and then will use binary serach to find the elements of unsorted array in the sorted array.

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

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)

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

``````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]))
else
result[array1[i]]++;
}

for (int i = 0; i < array2.Length; i++)
{
if (!result.ContainsKey(array2[i]))
else
result[array2[i]]++;
}
ArrayList t = new ArrayList();
for (int i = 0; i < result.Count; i++)
{
if (result.Values.ElementAt(i) >= 2)
}

foreach (var item in t)
{
Console.WriteLine(item.ToString());
}
}``````

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

if we use an auxillary space size m+n and use merge sort using D&Q and in merging part when we encounter same elements jus' print it out.......

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

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

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

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

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

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

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

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.

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.