Microsoft Interview Question
Country: United States
solution 1
sort the two arrays A[],B[],compare every elements Ai,Bj.
i=j=0;
if Ai==Bj ,then add to the result
else if Ai<Bi ,then i++
else j++
vector<int> Intersection(vector<int>& A,vector<int>& B)
{
sort(A.begin(),A.end());
sort(B.begin(),B.end());
int lenA=A.size();
int lenB=B.size();
vector<int> ans;
int i=0;
int j=0;
while(i<lenA && j<lenB)
{
if(A[i]==B[j])ans.push_back(A[i]);
else if(A[i]>B[j])j++;
else i++;
}
return ans;
}
Thanks for the answer, minor fix tho.
if(A[i]==B[j]){ans.push_back(A[i]); i++; j++;}
else if(A[i]>B[j])j++;
else i++;
I exactly did the same. But I used array to store the common elements instead of vectors, which was my blunder. I did not realize it would take away extra memory when there is no common elements or few ones.
You don't need to sort both the arrays. Smarter way of doing this would be to compare the sizes of the array, and sort the array with smaller size, thus yielding less time. Once, and array is sorted, you can traverse through all the elements of the other array and do a binary search on the sorted one. If the element exists, you add it to a vector and return the vector.
We can do better then O(max(n log n,m log m))
Put all the elements from A in a HashMap (key = element, value = 1)
for each element in B if exists in the HashMap (this check is done in O(1)) then added to the returned structure.
Complexity : time :O(max(n,m)) ; space: O(min(n,m)). // we assume ^_^ that A.length < B.length.
I think you can say O (m+n) or O(max(m,n)) because : lets say m > n so m = n + x => m + n = n + n + x = 2 * n + x = > O( m + n ) = O(2*n) + O (x) = O(n) + O (x) = O(n+x) = O(m) and we know m is the max between m and n.
Let me know if I'm wrong
Algo:
Step1 : Sort the first array.(m log m)
Step2 : Then for each elements of second array, do a binary search on the first array, if found print the value.(n log m).
No extra space is required.
import java.util.HashMap;
public class Q1 {
public static void main(String arg[]) {
HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
int a[] = { 2, 3, 6, 42, 6, 43, 2, 3 };
int b[] = { 42, 5, 7, 3, 8, 34, 2, 2};
h.put(2, 2);
h.put(3, 2);
h.put(6, 2);
h.put(42, 1);
h.put(43, 1);
for (int i = 0; i < a.length; i++) {
int temp = b[i];
if (h.containsKey(temp)) {
if (h.get(temp) > 0) {
System.out.print(temp + ", ");
int count = h.get(temp) - 1;
h.put(temp, count);
}
}
}
}
}
int[] first = new int[] { 1, 4, 3, 2, 6, 5, 16, 7 };
int[] second = new int[] { 8, 3, 5, 4, 2, 1 };
Hashtable result = new Hashtable();
foreach (int i in first)
{
result[i] = 1;
}
foreach (int i in second)
{
if (!result.ContainsKey(i))
{
result.Remove(i);
}
}
Well actually hashtable is not pratical...because the key space can be very large. The most general 2 ideas are: 1. sort and check 2. build a binary search tree for one of the array, and go through the other.
- Owensy December 24, 2012