Amazon Interview Question: Write an algorithm to determi... | Glassdoor

Interview Question

Software Development Engineer Interview Seattle, WA

Write an algorithm to determine if 2 linked lists intersect

Answer

Interview Answer

15 Answers

0

The first answer is simply looping through every item in list one checking it against all items in list 2 until you find a match. This is O(n2) and you'll be asked to improve it.
Think about other data structures with faster access to improve this algorithm.

Interview Candidate on Dec 9, 2011
2

^ Use a HashMap? We could traverse and put every node we see in a hashmap

PixelPerfect3 on Dec 12, 2011
1

@PixelPerfect3 Yes, a hashtable would do the job. Just put every node from one of the lists into a hashtable then traverse the other list checking to see if each node exists in the hashmap.
This would then be in O(n) time with the downside of using more memory for the hashtable.

Ja on Dec 12, 2011
13

I don't understand why we would need extra space for this problem. If two linked list intersects, that means their end are the same. Traverse until the end of both list and check if the address of the last nodes are the same.

Anonymous on Dec 17, 2011
1

@Anonymous - you are right. All we need to do is check if the ends are the same. My solution would be useful if we want to find the node they intersect at.

PixelPerfect3 on Dec 19, 2011
4

@PixelPerfect3 & @Anon - Sorry guys, that's not correct. It's not that the end of the lists are the same - intersecting means if any nodes within the linked list are the same.
For example:

List 1 = 1 -> 3 -> 5 -> 6 -> 7 -> 9
List 2 = 2 -> 4 -> 6 -> 8 -> 10

In this case, the 4th element of list 1 and the 3rd element of list 2 are "intesecting". Notice how the ends are different yet still they intersect.

The extra space used by the hashtable is made up for by the speed of lookup O(1) in the hashtable. If space is an issue and speed not, you'd go for the O(n2) solution which is to traverse through List 1 and for every node check it against all the nodes in List 2.

Ja on Dec 20, 2011
2

@Ja, would it be more clear to describe this question as "Check two LinkedLists, to see if they have one node sharing the same value." ?

Ron on Dec 26, 2011
1

@Ron Perhaps, yes. But take a look online for other people who have been asked this question from Amazon/Microsoft/Google. They tend to ask for "intersecting" linked lists, which means the lists share one or more of the same node. In my simple case above it might look as if it's just the value of each node in the list but I think technically intersecting means they share the same node, i.e. the object.
My example was just for illustration but if you were writing this for real you'd want to check the node->next pointer to see if it's the same object in both lists.

Ja on Dec 26, 2011
4

@Ja,

Your example doesn't really make sense: how can the node with value 6 point to a node with value 7 AND a node with value 8? It can only point to one node: either 7 or 8. That's why I think Anonymous' answer is correct.

PixelPerfect3 on Jan 3, 2012
1

@PixelPerfect3 - It's not the nodes value that's important but the actual node itself, i.e. the value of the next pointer will be the same for a node in both lists.

Simply saying "the last node in the list will be the same" is incorrect! Linked lists can intersect at any point in the lists and not share the same last node.

Ja on Jan 5, 2012
1

Actually, you know I think you guys are right after some thought! My only concern was to find the actual node they intersect at but PixelPerfect3 had a point - being that a singly linked list only points to one next node, if at any point they intersect then they must have the same node at the end of the list.
Sorry for adding to the confusion. If you wish to know exactly where they intersect then my solution posted above will work but if you just need to know if they intersect, PixelPerfect3 and Anon solution of the same end element is correct.

Ja on Jan 17, 2012
4

1) len1=find length of linkedlist1
2) len2 =find length of linkedlist2.

3) move the bigger linked list to (len1-len2) position.
4) rightnow both linked lists are equal at distance from last node. that is they are n node away last node.
5) iterate both LL simulatenously and if they have same instance that is their intersection point.

analog76 on Feb 4, 2012
3

I think all of you guys missed one important problem. What if the linked lists have cycles?
I believe this is one of the important points the interviewer want you to think about.

Anonymous on Nov 3, 2012
0

Assumption that if one node intersects, all nodes from there till the end intersect is wrong. For example, my node definition is:

typedef struct NODE
{
   int value;
   NODE *ptr1;
   NODE *ptr2;
} LISTNODE;

If I use ptr1 only for first list and ptr2 only for second list; then I could have an intersection at the middle element but not in the end. Its a different question why one would want to design a node the way I mentioned above; but the assumption is wrong.

Common answers:

a) If lists aren't cyclic; use a visited flag in the NODE definition and traverse first list and mark all nodes visited. Then traverse second and read the flag.

b) Use a hash-map with address as the key. Insert into hash-map while traversing first list. Check the hashmap while traversing second.

c) If the list could have cycles, still b) and a) would work with any modifications.

Shishir on Sep 6, 2015
1

Thats a double linked list. Not a linked list.

Anonymous on Sep 12, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.