NetApp Interview Question


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.

- Noobie September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- R September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about we break the link on the node in both linklists.
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!

- Anonymous December 25, 2013 | Flag
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.

- Selmeczy, P├ęter September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Water September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 18, 2012 | Flag
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..!!!

- Aavesh September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

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.

- Anonymous September 18, 2012 | Flag
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.
node *findMergeNode(node *head1, node *head2)
{
node *p=head1->next;
node *q=head2->next;

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

- Bin December 10, 2012 | Flag Reply
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()
{
    Node * head1 = list1;
    Node * head2 = list2;
    stack<Node*> s1,s2;
    while(head1)
    {
         s1.push(head1);
         head1 = head1->next;
    }
    while(head2)
    {
         s2.push(head2);
         head2 = head2->next;
    }
    while( !(s1.empty()) && !(s2.empty()) )
    {
            if(s1.top()  == s2.top())   
            {  cout<<"Lists intercept";
               break;
             }
            s1.pop();s2.pop();
    }



}

Does that seem correct ??

- Rohit January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it obviously & definitely correct

- ctang January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not correct.

- yuanyuan May 15, 2014 | Flag
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

- Shobhit July 27, 2013 | Flag Reply
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.

- Anonymous August 06, 2013 | Flag
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..

- Anonymous November 12, 2013 | Flag Reply
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.

- Venkat Kiran November 12, 2013 | Flag Reply
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.

- Venkat Kiran November 12, 2013 | Flag Reply
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)

- cl4w December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

The interviewer is a moron.

- Anonymous September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

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

- Ashupriya September 25, 2012 | Flag


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