## NetApp Interview Question

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

Can you use recursion while unwinding? Recursively reach end of both lists. Then when you unwind the recursion check the pointers. At the point where the merge you would get the same pointer.

Comment hidden because of low score. Click to expand.
0

Finding a original question is interviewer problem not the interviewees problem :).
Even if all of them are in internet or not this is what any can think of commonly unless some one is a geek or a weird

1. Methods to finding a duplicate element in an array. geeksforgeeks.org/archives/7953
2. The original efficient solution you suggested.

Comment hidden because of low score. Click to expand.
0

while(currentL1!=NULL&&currentL2!=NULL)
{
1) start from L2 and L1 both find the next and the current->next to NULL
}
we found the joint node!

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

Nice requirement :) most probably impossible to meet, but you can try some not-very clever but working solutions, like get the next item on list-2 and search if this pointer is in list-1 (if found, this is a merging point). Surely works and it is a trivial solution. At least this is what I'd told him/her.

Comment hidden because of low score. Click to expand.
0

Thats what I told him.......He said this is the most general solution.

Comment hidden because of low score. Click to expand.
0

If interviewer was so keen of new solution, why the heck he not asks some new question rather than asking same question which are over internet..

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

This is not a good solution at all, the interviewer did not want this because everybody tells the same, you should have told some other approach. You can even use the HashSet to do this very efficiently, You can use the negation technique, you can use slow and fast pointer technique..!!!

Comment hidden because of low score. Click to expand.
0

Why do you think its not a good solution. in which aspects this solution is defficient than your suggested ways?

Comment hidden because of low score. Click to expand.
0

You can't use the slow and fast pointer technique here, and I don't know what you mean by "negation technique". Using a HashSet is not nearly as efficient as doing it in the way the OP described.

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

traverse the two given linked lists and compare the value of next of two the nodes in both link lists.
{

while(p!=NULL && q!=NULL)
{
if(p==q)
{
break;
}else
{
p = p->next;
q = q->next;
}
}
}
if(p==q)
{
return p->next;
}

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

Memory : O((n1+n2)*sizeof(Node* pointer)) ~ O(n)
Time : O(n1+n2+min(n1,n2)) ~O(n)

``````#include<stack>
int main()
{
stack<Node*> s1,s2;
{
}
{
}
while( !(s1.empty()) && !(s2.empty()) )
{
if(s1.top()  == s2.top())
{  cout<<"Lists intercept";
break;
}
s1.pop();s2.pop();
}

}``````

Does that seem correct ??

Comment hidden because of low score. Click to expand.
0

it obviously & definitely correct

Comment hidden because of low score. Click to expand.
0

This is not correct.

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

->reverse the two linked lists..take two pointers catering to both the linked lists
->start from the last node (which is now the head for both)..
->if both their head values are unequal..simply return (as they have no common intersection point)
->else keep on traversing both the linked lists.also maintain a prev pointer..
->just when you get the data values of both the pointers as different..break out of the loop and return the prev pointer bnode

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

N1--> N2---->N3---+
|
+--->C1----->C2---->C3
|
M1-->M2-------------+

After reverse:
N1<-->N2<----N3---+
|
+---C1<-----C2<----C3
|
M1<--M2<-------------+

How come C1----> can points to L1 and L2. After doing this you will loose L1 or L2.

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

Store the first linked list in hash with key as the value in the linked list..
when traversing the second linked ,chek first with the key matching.
if the key is matching then chek for address.

at the intersection point both the value should match.
ofcourse this method will take o(n) space complexity.
but i guess it is fine to give methods when the interviewer want to check our problem solving in different approach..

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

push the elements of the first linked list in to the stack.
now traverse the second linked list till the end.
when returning from the end pop an element from the stack and compare till the point both are unequal.
if there reach unequal point , ur previous crossed node is the intersection point.
ofcourse this method will take o(n) space , but it will give the interviewer that u r thinking differently i feel.

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

push the elements of the first linked list in to the stack.
now traverse the second linked list till the end.
when returning from the end pop an element from the stack and compare till the point both are unequal.
if there reach unequal point , ur previous crossed node is the intersection point.
ofcourse this method will take o(n) space , but it will give the interviewer that u r thinking differently i feel.

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

1. Find the lengths of each list -> O(n)
2. Find the difference and traverse that many nodes in larger list (p1)
With the other pointer at the beginning of the smaller list (p2), these are at equal distances form the pt of intersection. Increment both till they meet at the intersection (they will surely meet as they are at equal distance from the intersection. -> O(n)

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

The interviewer is a moron.

Comment hidden because of low score. Click to expand.
0

To clarify, this is an easy problem, and doing it based on the length can easily be original, and come up with in 5 minutes.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

It looks interesting but due to the linear structure of the bt. The searching an element is On... And doing so for n elements of list b... The total complexiety is On^2

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.

### 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.