Ebay Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
You are using one hash table for unions, and two for intersections.
Can you use one hash table for both union and intersection?
After giving it a thought I realized we can do it in O(m+n) time. i.e. one traversal of both arrays for both intersection and union.
@JSDUDE Sorry, I've thought about the solution and realized that you don't need 2 hashtables. I've updated the solution above.
@JSDUDE
I'm aware of an O(m+n) approach which works if the arrays are sorted. If your approach works on un-sorted lists as well, please post it.
@arun_lisieux that's t whole point, the hashtable solution works for unsorted arrays and it's O(m+n). Otherwise, this problem is simply processing two arrays _linearly_ like the merge subroutine from the merge sort.
An alternative is to use a BST along with an augmented field called counter at each node. Just keep adding to the BST from both the arrays. If the given element is not present, then add it to the BST with the counter initialized to 1. If the element is already present increment the counter.
To print UNION, print all the nodes of the BST.
To print Intersection, do an inorder traversal and print only those node whose counter > 1
For that matter oOzz's solution can be extended to have one hashtable with counter as value and doing the same thing as I said above. That reduces the number of hash tables from 2 to 1
@Dumbo You do realize that in the worst case, inserting all the elements to a BST will be O((n+m)^2), which is the case where the arrays are sorted. I think you meant a balanced tree such as AVL, Red+Black Tree. Then this will be O((n+m) log (n+m)), with space complexity O(n+m).
Using one hashtable or two does not change the big-O space complexity, which is still O(n), because asymptotically O(2n) = O(n). Therefore, a balanced tree solution has the same space, but worse time complexity than the hashtable solution that I suggested.
I've also been thinking about the first solution that I've requested. It's possible to d it with one hashtable for both union and intersection. I'll update the above original solution, based on your suggestion to use 1 hashtable:
1. Insert elements to the hashtable and keep their counts
2. For union, you iterate the hashtable and print the items
For intersection, iterate the items in the hashtable and print keys, that have count >=2
Sort the two lists first [O(nlogn) time]. Then do a variation of the merge step similar to what is done in merge-sort with two separate pointers for each sorted list.
Python code below.
def lists_union_intersection(listA, listB):
## make a copy and sort the lists
sorted_listA = list(listA)
sorted_listB = list(listB)
sorted_listA.sort()
sorted_listB.sort()
## initialize
union_list = list()
intersection_list = list()
indexA=0;
indexB=0;
## merge step of two sorted arrays
while(True):
if indexA == len(sorted_listA): #check if no more elements in listA
if indexB != len(sorted_listB):
union_list.extend(sorted_listB[indexB:])
break
elif indexB == len(sorted_listB): #check if no more elements in listB
union_list.extend(sorted_listA[indexA:])
break
else:
a = sorted_listA[indexA]
b = sorted_listB[indexB]
if a < b:
union_list.append(a)
indexA += 1
elif a == b:
union_list.append(a)
intersection_list.append(a)
indexA += 1
indexB += 1
else:
union_list.append(b)
indexB += 1
return (union_list, intersection_list)
### MAIN ###
listA = [ 0, 2, 4, 5, 6]
listB = [ 1, 3, 5, 6]
(ulist, ilist) = lists_union_intersection(listA, listB)
print ulist
print ilist
These are three solutions I implemented:
Solution 1 with HashTable:
//Global vairable
Hashtable<int, int> myHasTable = new Hashtable<int, int>();
void PopulateHashTable(int[] array1, int[] array2)
{
foreach(int i in array1)
{
if(myHasTable(i).Value == 10)
continue;
myHasTable(i).Value = 10;
}
foreach(int i in array2)
{
if(myHasTable(i).Value==1 || myHasTable(i).Value==11)
continue;
myHasTable(i).Value++;
}
return;
}
int[] Union(int[] array1, int[] array2)
{
int[] unionArray = new int[array1.length + array2.length];
int index = 0;
foreach(int i in array1)
{
if(myHasTable(i).Value > 1)
{
unionArray[index++] = i;
}
}
foreach(int i in array2)
{
if(myHasTable(i).Value == 1)
{
unionArray[index++] = i;
}
}
return unionArray;
}
int[] Intersection(int[] array1, int[] array2)
{
int[] intersectionArray = new int[array1.length, array2.length];
int index= 0;
foreach(int i in array1)
{
if(myHasTable(i) == 11)
intersectionArray[index++] = i;
}
return intersectionArray;
}
No extra memory O(n^2) Union only:
// No extra memory Union function
int[] Union(int[] array1, int[] array2)
{
int unionArray = new int[array1.length, array2.length];
int index = 0;
int runner = 0;
unionArray[index++] = array1[0];
foreach(int i in array1)
{
runner = 0;
while(runner < index)
{
if(uninoArray[runner] != i)
{
runner++;
}
else
{
break;
}
}
if(runner == index)
{
unionArray[index++] = i;
}
}
// Repeat for array2
// Sorted arrays union
// Sorting takes O(log n) time.
// Assume array1 and array2 are sorted
int[] Union (int[] array1, int[] array2)
{
int unionArray;
index1 = 0;
int index2 = 0;
//unionArray[index++] = array1[0]
foreach(int i = 0; i < array1,length + array2.legnth; ++i)
{
if(array1[index1] == array2[index2])
{
if(index > 0 && array1[index1] != unionArray[index-1])
{
uninoArray[index++] = arra1[index1];
index1++;
index2++;
}
}
else if(array1[index1] < array2[index2])
{
unionArray[index++] = array1[index1++];
}
else
{
unionArray[index++] = array2[index2++];
}
}
}
Test cases:
1. Unsorted array with single value, all duplicates
2. Unsorted array some duplicates
3. Unsorted array no dupes
4. One array, 2nd empty
5. Sorted array, multiple dupes
6. Sorted array no dupes
7. Very large arrays
8. Both are empty arrays
9. 1 valued array(s)
10. Negative value and + values
11. both arrays with exactly same values
12. both arrays with unique values only
13. both large arrays containing only one value, duped
To find the union:
Build a Binary Search Tree (BST1) from A1.
Insert values from A2. Check for equals.
If value already exists in BST1, store it in a second BST(BST2).
All the values from BST2 are intersections.
All the values added to BST1 are union.
public void findUnion(int[] a1, int[] a2, HashSet<Integer> union, HashSet<Integer> inter) {
for (int i = 0; i < a1.length; i++)
if (!union.contains(a1[i]))
union.add(a1[i]);
for (int i = 0; i < a2.length; i++)
if (union.contains(a2[i])
inter.add(a2[i]);
else
union.add(a2[i]);
}
I get the solve by using a HashMap. However, how do we solve for duplicate values present in the two arrays.
Let's say
int[] arr1 = {1,2,3,2,6,7,4,6,6}
int[] arr2 = {1,2,4,5,7,9,4,6,2,6}
int[] result = {1,2,2,4,6,6,7}
Note: '6' is present in arr1 three times, but in arr2 only twice. So the output should have it just twice.
You can use a hashtable and insert the arrays to the hashtable.
- oOZz June 13, 2013For union, after insertion the hashtable will have all unique keys (aka, union) of two arrays, so return the keys in the hashtable.
For intersection, insert both arrays to the hashtable, before inserting each element though check if it's there (containsKey in Java), if it's not there then insert set the count 1, if it's there, then increment count. Then iterate the items on the hashtable and print keys, that has count >=2, which are the elements of the intersection.
O(m+n) time, and O(m+n) space.
You can use a bitvector or a bitset instead of a hashtable and save space with the same approach.