Pregunta de entrevista de Tripadvisor
# Q1: Write a function to intersect two *sorted* lists (find common elements)
# Write a method taking two lists as input, and returning a new list
# You can assume you have a reasonable array/list class available (ArrayList, vector, python list, etc)
# Ex:
# l1 = [1,2,3,4,5]
# l2 = [1,5,7,11,100]
# result = [1,5]
Respuestas de entrevistas
I found the answer to this question on this website before the interview :)
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
if the length of A1 is m and the length of A2 is n then this will run in average case (mlog(m) + nlog(n))
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;
if(lengthA1 == 0 || lengthA2 == 0)
{
return intersection;
}
while(jj A2.get(ii) )
{
ii++;
}
}
return intersection;
}