Interview Question


Country: India




Comment hidden because of low score. Click to expand.
2
of 2 vote

Traverse each list and push contents into stacks S1 and S2.
Pop each stack until you find dissimilar elements and return the last same element.

- Blahfoo March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please give an example? The way I understand this question is these list will have diff values and one of the memory pointer will be same and that is where it is intersecting.

- Anonymous March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

They meet at a point and after that they are same,means they share common tail.
1->2->3->7->8->9
4->5->6--^

- Punit Jain March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you're technically not traversing the linked lists twice in this approach, but you're traversing the data twice.

- eugene.yarovoi March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have to agree with Eugene and add that data might be Similar Even before the point of intersection. Hence copying and Comparing address in stacks is a better idea.

- Anon April 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Traverse the first list inserting each element into a hash table
- Traverse the second looking up each node in the hash table, if it exists, add it to the result
O(n+m) time - traverse each list once
O(max(n,m)+sizeof_intersection) space - extra hash table + result list
n,m are the sizes of each list

- Jaime March 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep. In fact, this is really the only efficient way to solve the problem if you can't even obtain something as basic as the length of the linked lists before traversing.

- eugene.yarovoi March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes hashing seems to be a right approach. Other approaches traverse the lists more than once.

- Punit Jain March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Although when you use hashing, you're looking at some of the data more than once too...whenever you hash a node for lookup in the table, you're comparing it to hashes of nodes already in that bucket. So you can end up looking at the hashes of the nodes already in a bucket multiple times, which is indirectly a way of making multiple passes over data. It's not really any better than copying the data over to an array and doing a backwards traversal to find the point of divergence, like recommended in the other solution.

- eugene.yarovoi March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are assuming that each node will have distinct values, which may not always be the case.

- :( April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

u can hash the address of the nodes which would always be unique and give the correct answer

- :) April 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use visited flag in each node of the linked list if thats allowed

- Anonymous March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Blahfoo, Good Answer !
I have another approach where I don't need any other memory -
1. count elements of each list,
2. find length diff
3. traverse smaller list from beginning and longer list after diff number of elements from begining.
4. compare both pointer while traversing both together. If equal, that is the merge point.

- ashwini verma March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this case you will traversing more than once. Condition is that you should travers only once.

- Anonymous March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Counting the number of elements in lists will be one traversal each so given the constraint you can't traverse them now.

this approach will need to traverse the lists twice each.

- Punit Jain March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a small doubt, are the 2 list sorted in some sense.(numerically or alphabetically)

- Mohamed Mustafa March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think, Intersection means meeting the 2 linked lists at one point (one node), where the two nodes meeting at one node (having same next pointer of that meeting node).
Lets say, a node having a data & next pointer. Checking the next pointer of List1 with next pointer of List2 are same, while traversing in the two lists. If they are same, that node is called intersection node (intersection point).

- Raja Sekhar March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

meetingpoint(Node* n1, Node*n2)
{
Node *mnode = NULL;
if(!n1->next && !n2->next)
return NULL;
if(!n1->next)
mnode = meetingpoint(n1, n2-.>next);
else if(!n2-.next)
mnode = meetingpoint(n1->next, n2-.>next);
else
mnode = meetingpoint(n1->next, n2->next);
if(mnode)
return mnode;
else if(n1 == n2)
return NULL;
else
return n1->next;
}

- Anonymous March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reverse both the linked list and identify the node which has branch.

- Shashank March 31, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More