Tripadvisor interview question
# Q2: Same as Q1, but now assume there can be duplicates. The output should not have duplicates
# Ex:
# l1 = [1,2,3,4,5,5,5]
# l2 = [1,5,7,11,100]
# result = [1,5]
Interview Answers
In Python:
def intersection(arr0, arr1):
res_intersection = []
idx0 = 0
idx1 = 0
while idx0 0 and res_intersection[-1] != arr0[idx0]:
res_intersection.append(arr0[idx0])
idx0 += 1
idx1 += 1
else:
if arr0[idx0] < arr1[idx1]:
idx0 += 1
else:
idx1 += 1
return res_intersection
intersection(l1, l2)
0
▼
I'm not 100% confident in this answer but I believe it works. Basically you just convert both linked lists to arrayLists then sort them in place. After this you can move through both lists at the same time comparing the smaller values to the higher values:
1,2,3,4,5,46 ii =0
1,4,5,6,17,46 jj =0
1 == 1 ? add to intersection, increment ii and jj
2 == 4 ? increment ii
3 == 4 ? increment ii
4 == 5 ? increment ii
5 == 5 ? add to intersection increment ii and jj
46 == 17 ? increment jj
46 == 46 ? add to intersection increment ii and jj
finished return intersection
One important added conditional here keeps the program from adding copied of a value to the output list. The conditional checks if the new value being inserted is the same as the previous value which was inserted. Because both ArrayLists are in order equal values will be placed in the intersection one after the other. So, once you see a new value you don't have to worry about there ever being a copy again:
public static LinkedList LLIntersect(LinkedList l1, LinkedList l2)
{
LinkedList intersection = new LinkedList();
ArrayList A1 = new ArrayList(l1);
ArrayList A2 = new ArrayList(l2);
quickSort(A1); //use any sort method that you like here
quickSort(A2); //use any sort method that you like here
int jj = 0, lengthA1 = A1.size()-1;
int ii = 0, lengthA2 = A2.size()-1;
float previousIntersectValue = 0.5f;
if(lengthA1 == 0 || lengthA2 == 0)
{
return intersection;
}
while(jj A2.get(ii) )
{
ii++;
}
}
return intersection;
}