Apache Design Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
that means listA is [NODES SPECIFIC TO A (x in number)]->[COMMON NODES (c)]
and listB is [NODES SPECIFIC TO B (y)]->[COMMON NODES(c)]
if listB is the longer than listA, then
1) find the x+c node from the tail of listB (O(n))
2) go forward one node at a time from head of smaller list (listA) and x+c node from tail of longer list (listB)
3) the point where you reach a common node is the point of intersection
If length of linked list is known then traverse the smaller list else select any list for traversal and add the node addresses to a hash table. Next traverse the other list and check presence of each node in the hash table. The first node of the other list which is found in the hash table is the node which is common to both the lists. The complexity of the algo will be O(m+n), where m, n are the lengths of each linked list respectively.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
int count(struct node **list)
{
struct node *temp;
int c=0;
temp=*list;
while(temp!=NULL)
{
c++;
temp=temp->next;
}
return c;
}
int main()
{
struct node *n1,*n2,*n3,*n4,*n5,*n6,*n7,*temp1,*temp2,*head1,*head2;
int a,b,c,i;
n1=malloc(sizeof(struct node));
n1->data=1;
n1->next=NULL;
n2=malloc(sizeof(struct node));
n2->data=2;
n1->next=n2;
n2->next=NULL;
n3=malloc(sizeof(struct node));
n3->data=3;
n2->next=n3;
n3->next=NULL;
n4=malloc(sizeof(struct node));
n4->data=4;
n3->next=n4;
n4->next=NULL;
n5=malloc(sizeof(struct node));
n5->data=5;
n4->next=n5;
n5->next=NULL;
n6=malloc(sizeof(struct node));
n6->data=6;
n6->next=NULL;
n7=malloc(sizeof(struct node));
n7->data=7;
n6->next=n7;
n7->next=n5;
head1=n1;
head2=n6;
temp1=head1;
temp2=head2;
while(temp1!=NULL)
{
printf(" %d ->",temp1->data);
temp1=temp1->next;
}
printf(" NULL\n\n");
while(temp2!=NULL)
{
printf(" %d ->",temp2->data);
temp2=temp2->next;
}
printf(" NULL\n\n");
a=count(&n1);
b=count(&n6);
printf("\n\nNO. of nodes in the first list is %d and those in the second one is %d\n\n",a,b);
if(temp1==temp2)
if(a>b)
{
c=a-b;
temp1=head1;
for(i=0;i<c;i++)
temp1=temp1->next;
temp2=head2;
while(temp1!=NULL&&temp2!=NULL)
{
i=c;
if(temp1->next==temp2->next)
{
printf("lists intersect after %d node in the smaller list\n",i);
break;
}
else
{
i++;
temp1=temp1->next;
temp2=temp2->next;
}
}
}
else
{
c=b-a;
temp2=head2;
for(i=0;i<c;i++)
temp2=temp2->next;
temp1=head1;
while(temp1!=NULL&&temp2!=NULL)
{
i=c;
if(temp1->next==temp2->next)
{
printf("lists intersect at %d node\n",i);
}
else
{
i++;
temp1=temp1->next;
temp2=temp2->next;
}
}
}
else
{
printf("\nThe lists donot interset\n");
}
return 0;
}
well i thought we need to create the lists and link them statically............this problem will not arise when we do it dynamically...........so this code finds pt. of inersection wrt shorter list
we could use a technique called reference counting. Assuming single linked list and we only have pointer to the head of each of them. We go through any one list and assign an integer to each node that keeps track of number of pointers to it.
When we traverse the second time, we would hit a node whose count is already one. So, that is the common node. So we end travelling atmost O(n + m) possibly less as it is given that the list continues after they meet.
Logic:
Take first list and while traversing to the end, mark all the nodes as visited. Then start from the other list and as soon as we hit the node where it says that it has already been traversed once, we hit the joining point.
There must be some more interesting solution, this just sounded too simple.
How will you mark the traversal as you are not supposed to do any change in the structure of list...and secondly if you store the lists'node address somewhere, then it will consume a lot of space..
@vineet, as it was not mentioned anywhere that I could not change/add a boolean flag, I chose that way.. but if we cannot have that boolean flag. I will think again. Back to drawing board in this case.
Can we use 2 stacks to store all nodes first and then pop every time to compare the nodes until there is a different, the previous node is the connection point.
- Anonymous March 28, 2012