## NetApp Microsoft Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
8
of 12 vote

Consider two linked lists L1 and L2
1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node

Complexity O(n)..

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

That wont work

what if both have similar lengths looking an 'X' not necessarily intersecting at the middle

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

If both have similar length then you just increment heads of both one by one.
And the approach is , if you have an intersection node then the nodes after the intersection are common to both the lists.
So we just have to find the length of the list before the intersection node.
Please explain why this wont work

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

@krishna... think again if it can ever be an X... it can only be a Y.. remember each node can have only one forward link.. once they have a common node, there is only one path to go

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

Its is a linked list , so every node has only one next pointer. So this will work. X is not possible since the intersection node will then have 2 next nodes.

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

There is 1 case where this will not work. What if the 2 linked lists have same elements before the intersection point? In that case this algorithm will not give the correct intersection point. For eg -

``````1->2->3->3->3->4>5->6
10->11->3->3->3->20
Assume that the 2nd list points to the node with 5 in the 1st list``````

It will give the intersection point as 3, where as it is 7th number

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

@codemaniac: you have to compare addresses of pointers not the value in nodes

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

also the complexity of algo will be O(m^2)......where 'm' is the length of shorter list.

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

No. Complexity is O(n+m+ (n-m) ). Worst case is o(3n.)

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

Why can't we just traverse thru both the lists and check whether the values are same if same then that is the intersecting point this will iterate until either of the node's next pointer is null or until it find the values are equal.

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

These are the following steps:-
1)traverse the first list and reach at the end
2)link the end of first list to the head of second list
3) retain the pointers at the head of both list,also at the end of 1st list
4) problem becomes a->b->c->d->e->f->g->h->e
loop in a linked list and now we have to find the start of loop
5)take two pointers move 1st by one node,second by two
6) when they meet after that take back the 1st to head
7)now move both pointers 1st and second also by one node(from the meeting point)
8)where they meet is the intersection of both list
9)break the link from last of 1st list to head of second

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

int check( struct node * list1,struct node * list2)
{
int count1 = countLL(list1);
int count2 = countLL(list2);

while(count1> count2)
{
list1 = list1->next;
count1--;
}
while(count2>count1)
{
list2 = list2->next;
count2--;
}

while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1== null)
{
return 0;/ do not intersect
}
else
return 1; //it intersects

}

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

A lil bit change... updating code of "Y" scenario with "V" scenario.
1."Y" scenario:
! !
! !
! !
!
!
!
1."V" scenario:
!.....!
!...!
!.!
!
struct node * checkstruct( struct node * list1,struct node * list2)
{
struct node * intersect;
int count1 = countLL(list1);
int count2 = countLL(list2);

while(count1> count2)
{
list1 = list1->next;
count1--;
}
while(count2>count1)
{
list2 = list2->next;
count2--;
}

while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1=list2)
{
if(list1->next==NULL)
{
printf("it intersects at the last");
}
else
{
printf("it intersects in mid");
}
intersect=list1;
}

else
{

printf("it do not intersect");
intersect=NULL;
}
return intersect;
}

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

Check your code for two lists,which are not intersecting.
Please tell me,for which case,my code will give wrong result?

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

small correction :)

.....
while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1==list2)//change
{
if(list1->next==NULL)
......

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

this wont work for "the revrese of Y case"..

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

this wont work for "the revrese of Y case"..

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

Another approach :
1. point the last of 1st list to begining of second list.
2. Check if cycle is present (using fast and slow pointer).
3. If cycle is present then these two list merge at some point.
4. to Find the merging point, take two pointers one at the start of 1st list and another at the node where fast and slow pointers meet.
5. increment these two pointers by one each.
6. the node where they meet will be the merging point of two list.

Thanks

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

please can you explain with example?

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

Intersection does not guarantee that they have a cycle!

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

Algo:
- Find lengths of lists with two given heads. Let us say they are m, n.
- Have two pointers each pointing to given head pointers
- Find abs(m - n), and skip abs(m - n) nodes in the long list
- Compare both pointers. If they match, return. Otherwise, move both pointers by one step. Repeat this step till the lists end

Logic:
- Maximum length of common list < minimum of lengths of linked lists
-- Case - 1: One is a sub-list of the other
-- Case - 2: Both lists are same
- That means big list length - small list length nodes can safely be skipped for comparison

Space Complexity : O(1)
Time Complexity: O(m + n)

Thanks,
Laxmi

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

if the address of tail nodes in both linked lists are equal then the linked lists intersect.

to find the intersection..increment a pointer from head of the longer list by L1-L2...where L1 and L2 are lengths of longer and shorter lists. The pointer on L2 starts from its head. Now keep incrementing the pointers of both L1 and L2 till they intersect.

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

not necessarily... tht kind of intersection is just one of the 3 possible intersections.. the other 2 are 1) intersection in the shape of X. 2)same head node but diff tail nodes.

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

Normally when we say, two or more link lists intersect, we mean that they share a SAME node at the point of intersection.
If this is what we mean here, then for two lists, shape will look like Y. It can't be of shape X OR /\ (As suggested by M) because one node can't have two different next pointers. With this assumption, v and rosh above are good and saying same thing.
If we mean intersection of list if two nodes a different (at two different memory addresses) but have same value, then we can think of X ot /\ scenarios. But I believe this is not the case here.

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

@anu: hey awesome logic.
But i think '/\'is possible in case of common last node. Dont u think..?

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

@pkt: anurag is still right because what u implied was actually a 'Y' case with a common last node.

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

Nope intersection in de shape of X is not possible coz if it has to occur de middle node should have 2 next pointers n v's sol is rite

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

Nope intersection in de shape of X is not possible coz if it has to occur de middle node should have 2 next pointers n v's sol is rite

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

intersection of two single link-list always be in Y shape, X shape is not possible in any case.

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

yes it is not possible.You can not have a node which is having a single pointer pointing two different nodes.X is not at all possible.

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

Cudos to M..

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

void check(struct node *list1, struct node *list2)
{

}

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

void check(struct node *list1, struct node *list2)
{
struct node *temp1, *temp2;
temp1=list1->start;
while(temp1!=NULL
{

}

)
}

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

void check(struct node *list1, struct node *list2)
{
struct node *temp1, *temp2;
temp1=list1->start;
while(temp1!=NULL
{
temp2=list2->start;
while(temp2!=NULL)
{
if(temp1==temp2)
{
printf("Intersection found!"); //at temp1 or temp2
break;
}
temp2=temp2->next;
}
temp1=temp1->next;
}
)
}

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

If two linked lists meet then they should end at the same NULL node (or last node). Traverse both lists and if they both end at the same NULL node (or if the last node is same for both), they meet

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

sry didnt read question completely. tulley's solution shud work

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

Just curious, why won't your solution work?

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

It does but it doesn't find where they meet ie this solution answers the question partially

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

Y list problem.
1. Traverse both the list and count nodes.
2. Traverse the bigger one as many nodes as the difference between two.
3. Now traverse both the list simultaneously and keep on checking if both the pointers are pointing to same node.

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

If we have authority to change the linklist node structure,i'll makrk each visited node of 1st list.

now i'll start traversing on 2nd list & when i'll get marked node then i'll get merging point.

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

please dont make assumptions while devising a solution.it would be too easy if u can change the node structure. link list means singly link list unless stated otherwise.

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

while(list1 != null && list2 != null )
{
if(list1 == list2)
return true;
else
{
list1=list1->next;
if(list1==list2)
return true;
else
list2=list2->next;
}
}

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

But I have one question

if the two linked lists meet, the meeting node will have two next pointers pointing to both the linked lists, so while travering in the cycle, how the next pointer will be progressed? I mean towards which linked list?

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

please can you explain with example?

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

1) Assume list 2 to be shorter list, list 1 to be longer one

2) loop x from head:list1 to NULL
loop y from head:list2 to NULL
if ( x == y )
intersection = x;
return;

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

Finding out if they merge is easy, start with 2 pointers and keep iterating until next pointer is null. If the 2 poiters are now equal, then lists merge. Basically if the last elemet of the 2 lists is the same node, they converge, otherwise not.

now finding out where they merge - can we use a hash and add nodes from first list, then from second list. First node where we hit exception is the one where lists merge, since that will be the first common node.

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

not necessarily, as we can have nodes even after the merge point... how do we deal with that?

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

Yes, but if you insert nodes into the hash in order, then the common node will be the first one to throw that it cannot be inserted into the hash.

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

Use hashmap then store element addresses, if key is exists then it is merge point.

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

Using a hashmap to store the addresses of the list elements is working but if the lists are huge this table will be huge.

If memory is the bottleneck and you are willing to pay for time you could do this:
Get the address of the first list item in list-A and search for it in list-B. If found -> bingo. If not get the next item in list-A and repeat. If you cannot find any of the addresses of the items in list-A -> they never merge. (And it does not matter which list you use as list-A and -B)

Actually they always merge in NULL aka the empty list :) but I am not sure all interviewers will love this answer although an empty list is a very nice list and he/she might not like if you ignore this special case on another problem ;)

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

Brute Force and O(n2) The solution above is O(n) use that instead.

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

You are right, I was concentrating so on the memory impact that I missed that point that tails has to be the same length. But usually list do or do not contain their lengths, but still if you have to calculate the length that is better.

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

Just compare tails of each list. If they become equal then they merge.

To find out where do they actually meet we can do the reverse traverse till the node is in both list. Thus we get the node where the lists meet.

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

Consider two linked lists L1 and L2
1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node

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

O(l1 + l2)

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

Consider this example.....
1->2->3->4->5->6->7
2->3->4->5->6->7

here nodes with value 2 and 3 are different nodes in different list...node with value 4 is common node (intersection point) after that 5,6,7 follows.....

In this case your solution will fail....as comparing with node value 2 will result in intersection point but actually it is not.....

The correct solution can be.....

make the next pointer for first list null as we traverse down to the list....
Now traverse other list till null comes...the last node is intersection point.

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

Consider this example.....
1->2->3->4->5->6->7
2->3->4->5->6->7

here nodes with value 2 and 3 are different nodes in different list...node with value 4 is common node (intersection point) after that 5,6,7 follows.....

In this case your solution will fail....as comparing with node value 2 will result in intersection point but actually it is not.....

The correct solution can be.....

make the next pointer for first list null as we traverse down to the list....
Now traverse other list till null comes...the last node is intersection point.

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

How about if the LLs do not intersect at all?
How can you make that check?

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

given these two lists:
1->2->3->4->5->6->7 and
a->b->6->c->d, then the intersection point would be 6 right?
If that's the case, then you can find that point with a hash table and the complexity would be O(n+m) (the number of nodes in both lists).

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

how can you get 7 and c after 6. You have only one next pointer. so, your example is wrong.

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

you can only get y-shaped intersection

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

Yes exactly only y shaped intersection is possible

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

Exactly!
A node can point to only one other node!

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

// junk.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *next;
};

struct node * insert(struct node *, int );
void insertintersection(struct node *,struct node *, int );
void display(struct node *);
int intersection(struct node *,struct node *);

void main()
{
int x=0,p=0;

//1st list

printf("1st list is :=>\n");

// 2nd list

printf("\n2nd list is :=>\n");

printf("\nintersection point is ==>%d",p);
}

int intersection(struct node *t,struct node *r)
{
struct node *temp1,*temp2;
int count1=0,count2=0,diff=0;

temp1=t;
temp2=r;
while(temp1)
{
temp1=temp1->next;
count1++;
}

while(temp2)
{
temp2=temp2->next;
count2++;
}

diff=count2-count1;

for(;diff>0;diff--)
r=r->next;

while(t->data!=r->data)
{
t=t->next;
r=r->next;
}
return (t->data);
}

struct node * insert(struct node *t,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

if(t==NULL)
{
t=temp;
}
else
{
r=t;
while(r->next!=NULL)
{
r=r->next;
}
r->next=temp;
}
return t;
}

void insertintersection(struct node *t,struct node*s,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

while(t->data!=40)
t=t->next;
while(s->next !=NULL)
s=s->next;
s->next=temp;
temp->next=t;

return;

}

void display(struct node *t)
{
struct node *p;
p=t;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
}

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

// junk.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *next;
};

struct node * insert(struct node *, int );
void insertintersection(struct node *,struct node *, int );
void display(struct node *);
int intersection(struct node *,struct node *);

void main()
{
int x=0,p=0;

//1st list

printf("1st list is :=>\n");

// 2nd list

printf("\n2nd list is :=>\n");

printf("\nintersection point is ==>%d",p);
}

int intersection(struct node *t,struct node *r)
{
struct node *temp1,*temp2;
int count1=0,count2=0,diff=0;

temp1=t;
temp2=r;
while(temp1)
{
temp1=temp1->next;
count1++;
}

while(temp2)
{
temp2=temp2->next;
count2++;
}

diff=count2-count1;

for(;diff>0;diff--)
r=r->next;

while(t->data!=r->data)
{
t=t->next;
r=r->next;
}
return (t->data);
}

struct node * insert(struct node *t,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

if(t==NULL)
{
t=temp;
}
else
{
r=t;
while(r->next!=NULL)
{
r=r->next;
}
r->next=temp;
}
return t;
}

void insertintersection(struct node *t,struct node*s,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

while(t->data!=40)
t=t->next;
while(s->next !=NULL)
s=s->next;
s->next=temp;
temp->next=t;

return;

}

void display(struct node *t)
{
struct node *p;
p=t;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
}

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

(Using difference of node counts)
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

``````#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node* next;
};

/* Function to get the counts of node in a linked list */

/* function to get the intersection point of two linked

/* function to get the intersection point of two linked
{
int d;

if(c1 > c2)
{
d = c1 - c2;
}
else
{
d = c2 - c1;
}
}

/* function to get the intersection point of two linked
{
int i;

for(i = 0; i < d; i++)
{
if(current1 == NULL)
{  return -1; }
current1 = current1->next;
}

while(current1 !=  NULL && current2 != NULL)
{
if(current1 == current2)
return current1->data;
current1= current1->next;
current2= current2->next;
}

return -1;
}

returns the count of nodes in the list */
{
int count = 0;

while (current != NULL)
{
count++;
current = current->next;
}

return count;
}``````

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

One solution..
1. Go to the end node of common list.
2. Make it point to the head of longer list.Loop will be created
3 Calculate the length of the loop 'x'.
4. Now take two iterator itr1 and itr2. Give head start of x to itr1.
5. Now move both the itrs toward head with same speed.whereever they meet that will be the intersection node.

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

exactly as what I thought

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

Use 2 stacks to store nodes while traversing 2 linkedlists. Then keep popping until you find 2 nodes that are different.

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

Sort the linklists and then it would be easy to find intersection.

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

may be a crude/immature or an engineering method

1) L1 = length( list1);
2) L2 = length( list2);
now reverse any of the list [ assume List-1 is reversed ]
3) now starting from head of List-2 find the length = L3

intersection point Ie ( From the end ) = ( L1+L2 - L3 )/2;

intersection point from the begining of list 1 is ( L1- Ie)th node

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

a Small correction in the above method

intersection point Ie ( From the end ) = ( L1+L2 - L3-1 )/2;

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

How about Reverse(L1), Reverse(L2) and then check for a diverging node!

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

gives point of intersection

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

import java.util.ArrayList;

public class Intersect
{
ArrayList l1 = new ArrayList<Integer>();
ArrayList l2 = new ArrayList<Integer>();

public Intersect()
{

}
public void findIntersect()
{
int count = 0 ;
for(Object i : l1)
{
if(l2.contains(i))
break;
count++;
}

int l = (l1.size() > l2.size() ? l1.size() : l2.size());

if( count > (l/2) )
System.out.println("Intersection Point is at end");
else if( count < (l/2))
System.out.println("Intersection Point is at start");
else
System.out.println("Intersection Point is at mid");
}
public static void main(String[] args)
{
Intersect i = new Intersect();
i.findIntersect();
}
}

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

{{
import java.util.ArrayList;

public class Intersect
{
ArrayList l1 = new ArrayList<Integer>();
ArrayList l2 = new ArrayList<Integer>();

public Intersect()
{

}
public void findIntersect()
{
int count = 0 ;
for(Object i : l1)
{
if(l2.contains(i))
break;
count++;
}

int l = (l1.size() > l2.size() ? l1.size() : l2.size());

if( count > (l/2) )
System.out.println("Intersection Point is at end");
else if( count < (l/2))
System.out.println("Intersection Point is at start");
else
System.out.println("Intersection Point is at mid");
}
public static void main(String[] args)
{
Intersect i = new Intersect();
i.findIntersect();
}
}
}}

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

(1)take 2pointers initialize to head of the list
(2)increment both pointer till they reach end of the list and calculate list length l1,l2
(3) calculate absolute difference between l1-l2 ie n=|l1-l2|
(4) calculate nth element from end of the list.

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

Doesn't seem to be right to me...
Did you try with more examples?

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

I could only think of using a hashtable

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

a binary search may be useful.

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

how?

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.