Amazon Interview Question: Given the head pointers to tw... | Glassdoor

Interview Question

Software Development Engineer Intern Interview Seattle, WA

Given the head pointers to two linked lists of unknown

  length, find the node of intersection if they do intersect.
Answer

Interview Answer

5 Answers

1

Suppose that the pointers are head1 and head2. Move head1 and increment a count1 till head1 reaches null. Move head2 and increment count2 till head2 reaches null. If head1 > head2 or head2 > head1, move the respective pointer to such a position in the linked list so that the length of the linked lists from there are equal. Then, start checking if both pointers point to the same node and incrementing both until that condition is met.

If they do point to the same node at some point, that is the node of intersection. Otherwise, there is no intersection.

Interview Candidate on Jan 6, 2011
1

I don't understand the interview candidate's solution. I don't think I will work properly. If the last 3rd node of List A and last node of List B intersects, this algorithm will not find the answer.
My solutions: Suppose length of List A is m, length of List B is n,
If space cost is more of a concern, do a O(n^2) search because it will cost constant space to find the intersect. (nested for loop)
If time is more of a concern,
1. traverse through both list to figure out the length. Identify the smaller list(suppose it's list A). cost O(m+n).
2. traverse List A, build a binary search tree with the address of pointers of the list as payload O(m log(m)).
3. Traverse through list B and search the tree for each element in list B. if found, then it's the intersection.O(n log(m)).
the general complexity is O(m+n+(m+n)log(m)) = O((m+n)log(m)). If we don't suppose A is the shorter, then the time complexity will be O((m+n)log(min(m,n)))

William on Feb 13, 2011
5

pblm can be solved by making a circular linked list.
Start with head1 and traverse thru the list and modify the lastnode.nxtptr -> head2
Now start with head2 and traverse. If you reach the head2 again then the list do intersect.

Vijay on Mar 10, 2011
0

Vijay has the best solution with linear time.

Anonymous on Mar 14, 2011
0

Vijay's solution works great for finding out whether they intersect, but the question asks for finding the node of intersection.

I think William's solution will work best for finding the node of intersection. The obvious one is an O(n^2) solution by traversing the first list with the nodes of the second list and doing a comparison.

PixelPerfect3 on Nov 1, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.