NetApp Microsoft Amazon Interview Question
Software Engineer / DevelopersThat wont work
what if both have similar lengths looking an 'X' not necessarily intersecting at the middle
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
@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
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.
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
also the complexity of algo will be O(m^2)......where 'm' is the length of shorter list.
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
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
}
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;
}
Check your code for two lists,which are not intersecting.
Please tell me,for which case,my code will give wrong result?
small correction :)
.....
while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1==list2)//change
{
if(list1->next==NULL)
......
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
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
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.
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.
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.
@anu: hey awesome logic.
But i think '/\'is possible in case of common last node. Dont u think..?
intersection of two single link-list always be in Y shape, X shape is not possible in any case.
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
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.
Thanks Paras for your reply
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?
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.
not necessarily, as we can have nodes even after the merge point... how do we deal with that?
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 ;)
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
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.
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.
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).
how can you get 7 and c after 6. You have only one next pointer. so, your example is wrong.
// 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()
{
struct node *head1,*head2,*top;
int x=0,p=0;
head1=NULL;
head2=NULL;
//1st list
head1=insert(head1,10);
head1=insert(head1,20);
head1=insert(head1,30);
head1=insert(head1,40);
head1=insert(head1,50);
head1=insert(head1,60);
head1=insert(head1,70);
head1=insert(head1,80);
head1=insert(head1,90);
head1=insert(head1,100);
printf("1st list is :=>\n");
display(head1);
// 2nd list
head2=insert(head2,1000);
head2=insert(head2,2000);
head2=insert(head2,4000);
head2=insert(head2,5000);
head2=insert(head2,200);
head2=insert(head2,300);
head2=insert(head2,800);
insertintersection(head1,head2,700);
printf("\n2nd list is :=>\n");
display(head2);
p=intersection(head1,head2);
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;
}
}
// 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()
{
struct node *head1,*head2,*top;
int x=0,p=0;
head1=NULL;
head2=NULL;
//1st list
head1=insert(head1,10);
head1=insert(head1,20);
head1=insert(head1,30);
head1=insert(head1,40);
head1=insert(head1,50);
head1=insert(head1,60);
head1=insert(head1,70);
head1=insert(head1,80);
head1=insert(head1,90);
head1=insert(head1,100);
printf("1st list is :=>\n");
display(head1);
// 2nd list
head2=insert(head2,1000);
head2=insert(head2,2000);
head2=insert(head2,4000);
head2=insert(head2,5000);
head2=insert(head2,200);
head2=insert(head2,300);
head2=insert(head2,800);
insertintersection(head1,head2,700);
printf("\n2nd list is :=>\n");
display(head2);
p=intersection(head1,head2);
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;
}
}
(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>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* Function to get the counts of node in a linked list */
int getCount(struct node* head);
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct node* head1, struct node* head2);
/* function to get the intersection point of two linked
lists head1 and head2 */
int getIntesectionNode(struct node* head1, struct node* head2)
{
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;
if(c1 > c2)
{
d = c1 - c2;
return _getIntesectionNode(d, head1, head2);
}
else
{
d = c2 - c1;
return _getIntesectionNode(d, head2, head1);
}
}
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct node* head1, struct node* head2)
{
int i;
struct node* current1 = head1;
struct node* current2 = head2;
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;
}
/* Takes head pointer of the linked list and
returns the count of nodes in the list */
int getCount(struct node* head)
{
struct node* current = head;
int count = 0;
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
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.
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
import java.util.ArrayList;
public class Intersect
{
ArrayList l1 = new ArrayList<Integer>();
ArrayList l2 = new ArrayList<Integer>();
public Intersect()
{
l1.add(1);
l1.add(2);
l1.add(7);
l1.add(4);
l2.add(5);
l2.add(6);
l2.add(7);
l2.add(9);
}
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();
}
}
{{
import java.util.ArrayList;
public class Intersect
{
ArrayList l1 = new ArrayList<Integer>();
ArrayList l2 = new ArrayList<Integer>();
public Intersect()
{
l1.add(1);
l1.add(2);
l1.add(7);
l1.add(4);
l2.add(5);
l2.add(6);
l2.add(7);
l2.add(9);
}
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();
}
}
}}
(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.
Consider two linked lists L1 and L2
- Yogesh Hande February 19, 20121) 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)..