Amazon Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
no, O(1) space doesn't mean 1 variable. It means constant space.
To find the intersecting node start at the head of both lists. Iterate forward the pointer to the head of the longer list, a number of steps equal to the difference in the lengths of the lists. Then compare the nodes pointed by both pointers and move forward both pointers until the match is found.
I am sorry.. But I fail to understand the question and your approach to the problem.
How can u be certain the you WILL find the intersecting element after jumping your pointer to the difference in the length of the two list??
List 1 : Length = 10
List 2: Length = 6
The claim is that you are going to compare
List1(Element 5) with List2(Element 1), then
List1(Element 6) with List2(Element 2) and so on..
Is is not possible for any of the earlier elements from List1 to match up with any element in List 2.
For eg, List1(Element 2) to match up with another List2(Any element of List)
Thanks.
Hi Bevan ,
The question is : to find if to linked lists are intersecting ,if yes return the first intersecting node
Understanding question :
Consider the shape "Y" made of beads ...
Now assume each bead as node and it is pointing to the next bead to for linked list .
I mean if two linked list's are intersecting they form a shape "Y" .
Here we need to find the intersecting point ....
Awesome Man.. Thanks ... Understood the question now..
Did not get the "Y" Shape part of the question..Perfect ans then!! :)
how will you find the end of the list ? like if your two lists are 1,2,3,4,5,6 and 1,2,3 and and they are merging to 1,2,3,4,5,6
I am not sure how to do it in single iteration.
@Ankur : Have a look at program below its working ...
#include <stdio.h>
#include <conio.h>
typedef struct NODE
{
int data;
struct NODE *next;
}*PNODE,NODE;
PNODE getNode(int data)
{
PNODE node = (PNODE)malloc(sizeof(NODE));
node->data = data;
node->next = NULL;
return node;
}
void createList(PNODE head,int num)
{
int i = 0;
for(i = 1; i< num; i++)
{
head->next = getNode(i);
head = head->next;
}
}
void printList(PNODE head)
{
printf("\nLinked list");
while(head)
{
printf(" -> %d", head->data);
head = head->next;
}
}
void findIntersect(PNODE head1, PNODE head2)
{
int diff = 0;
PNODE temp = head1;
while(temp)
{
temp = temp->next;
diff++;
}
temp = head2;
while(temp)
{
temp = temp->next;
diff--;
}
if(diff < 0)
{
while(diff!=0)
{
diff++;
head2 = head2->next;
}
}
if(diff > 0)
{
while(diff > 0)
{
diff--;
head1 = head1->next;
}
}
while(head1 != head2)
{
head1 = head1->next;
head2 = head2->next;
}
if(!(head1 && head2))
{
printf("\nThese two lists wont intersect!");
}
else
{
printf("\nLists intersect at : %d", head1->data);
}
}
int main()
{
PNODE head1 = getNode(0);
PNODE head2 = getNode(0);
PNODE tail = NULL;
PNODE intersect = NULL;
int i = 0;
createList(head1,10);
createList(head2,3);
tail = head2;
intersect = head1;
for(i = 0; i < 5;i++)
{
intersect = intersect->next;
}
while(tail -> next)
{
tail = tail->next;
}
tail->next = intersect;
clrscr();
printList(head1);
printList(head2);
findIntersect(head1,head2);
getch();
}
If the linked list is
1 2 3 4 5 6 7 8 9
^ ^
head1 head 2
p1 = head1
p2 = head 2
while(p1 != p2)
{
p1 = p1 ->next;
}
if(p1 == NULL)
{
while(p2 != p1)
{
p2 = p2->next;
}
}
Count size of List A, B
If one list is larger than the other, move the root of the larger list until the remaining nodes are the same.
Now, while each list.next != null, compare RootA.Next with RootB.Next. If they are equal, return true, else move RootA = RootA.Next, RootB = RootB.Next
Quite nice, and simple. It's equivalent to the HCA (LCA?) Highest Common Ancestor in trees.
There are simpler ways to find /that/ the two are linked but, if it's a singly-linked list, and given that we have to find the point of intersection, this seems simple, and good.
I couldnt understand the part: "...move the root of the larger list until the remaining nodes are the same."
How do you know that? The lists are not supposed to meet at the same indexed node. For ex:
1->2->3->4->5->6->7->8
9->7->8
also intersect. If you are talking about two nested loops, that will be a trivial sln and surely not acceptable.
findIntersectoin(node *p, node *q)
{
int d1=0,d2=0;
node* x=p;
while(x)
{
d1++;
x=x.next;
}
x=q;
while(x)
{
d2++;
x=x.next;
}
int d;
if(d1>d2)
{
d=d1-d2;
while(d>0)
p=p.next;
}
else
{
d=d2-d1;
while(d>0)
q=q.next;
}
while(p && q)
{
if(p.data==q.data)
return p;
p=p.next;
q=q.next;
}
return null;
}
Isn't this solution iterating over the linked lists more than once though? Or is that not what was meant by "one iteration"?
The question has two parts
1) Find if the lists has any intersecting node. This has to be done in single iteration
2) Find the intersecting node. This has to be done in O(n). The solution posted is for this problem which is fine
while(d>0)
q=q.next;
The value of "d" isn't getting updated in this loop.This results into infinite loop.
hi,
I assume that it is a single linked list. Now If the two list is intersecting then they will have the single tail. so just go to boths tail and compare it.
How to find the point of interesection.
1) Find the length of both the list. let us say M and N.
2) now let us say M is bigger one. then find out the difference. d=M-N.
3) mow move d pointer on the bigger list.
now onward both this list has same length and they are going to merge also. So just move one node on both the list and compare nodes value. It will give u the node u are looking for.
thanks,
DD>
The question is not clear but It is possible that
A->next = B, B->next=C; C->next=D and so on.
Later you have another node say,
T->next= C. What would you say to this. It means the second linked list somewhere is going to join another list.
Destructive solution:
[1] Scan one list, say listA and point every node until end, listA(1..n)->next to a special node called nodeIntersect.
[2] Now scan listB and see if currentNode->next==nodeIntersect. If so, currentNode of listB is the intersection point
Much less destrcutive, requiring additional space:
[1] Scan listA and add the nodes (the pointer) to a hashtable
[2] Scab listB and if any of the pointer is same in hashtable, that pointer (or the node) is the point of intersection
There must be a better solution though. I am not aware of one right now.
why is everyone assumming it's Y-shaped ? The question asks for intersection, not merging. And in that case, it could be X-shaped too.
sorry my bad... realised it can never be X-shaped... as it would mean the intersecting node point to 2 separate locations, which is not possible ( a common node in a singly linked list can point to only one next location. )
sorry my bad... realised it can never be X-shaped... as it would mean the intersecting node point to 2 separate locations, which is not possible ( a common node in a singly linked list can point to only one next location. )
two link list A and B..if we can modify link list then it will become quite easy task
add flag value to each node and when we traverse link list A then make flag =1 and second time when we traverse link list B if we already find flag =1 then that will be interaction point
correct me if wrong
node structure is
Node
{
Type value;
Node Next;
}
there is no flag field,dynamically we cant add extra field,possible but costs high,so this is not correct solution...
if node is in the following form
Node
{
Type value;
Node Next;
int flag;
}
then you are correct...:-)
Lets call the two lists a and b.Reverse the two lists.Continue iterating through list until a!=b.If the two lists are entirely different and they dont intersect then the return value would be false.
while(a==b){
commonNode = a;
a=a->next;
b=b->next;
count++;
}
if(a!=b && count==0){
return false;
}
else{
cout<<"List intersects at "<<commonNode->data;
return true;
}
node *temp, *prev;
temp = list_a.head;
while(temp != NULL)
{
stack_a.push(temp);
temp = temp->next;
}
temp = list_b.head;
while(temp != NULL)
{
stack_b.push(temp)
temp = temp->next;
}
prev = NULL;
temp = stack_a.pop();
while(temp == stack_b.pop())
{
prev = temp;
}
return(prev);
Pls correct me if I'm wrong.
Say the input lists are A and B and 6 is the intersection node. Then the list looks like as below.
A==> 1->2->3->4->5->6->7->8->9->10->NULL
B==> 15->13->12->11->6->7->8->9->10->NULL
Now if you will reverse the list B then the whole list architecture will looks like as below
A==> 1-->2-->3-->4-->5-->6<--7<--8<--9<--10 <==B
NULL<--15<--13<--12<--11<--6<--7<--8<--9<--10 <==B
Now if you will try to travers list A you will get something like below
A_New==> 1-->2-->3-->4-->5-->6-->11-->12-->13-->15-->NULL
So in this A_New list, if the last node will be the same of the first node of original B list (node value 15) then we can say that there is a intersection in between list A and list B.
================================================================================
How to find the intersection node ?
say the length of list A is x, list B is y and list A_New is z. And say the length of common part of list A and B is k. (i.e k is the length from intersection node to last node).
Now we can say,
(x-k) + (y-k) = z
or, k = (x+y-z)/2
Make two stacks, one while traversing each list. Then, compare the top two elements. If they're not the same, the lists do not intersect. If they are, keep popping off both stacks until they're no longer the same. The last node that was the same on both stacks is the intersecting node.
import java.util.HashSet;
import java.util.Stack;
import simplelinkedlist.SimpleLinkedList.Node;
public class IntersectingLinkedLists2 {
/**
* @param args
*/
public static void main(String[] args)
{
Node n1 = new Node(1);
Node n2 = new Node(2);
n1.next = n2;
Node n3 = new Node(3);
n2.next = n3;
Node n4 = new Node(4);
n3.next = n4;
Node m1 = new Node(100);
Node m2 = new Node(101);
m1.next = m2;
Node m3 = new Node(102);
m2.next = m3;
m3.next = n2;
Node intersect = getIntersect(makeStack(n1), makeStack(m1));
System.out.println("Intersection is at " + intersect.value);
}
public static Stack <Node> makeStack(Node n)
{
Stack <Node> s = new Stack();
while(n != null)
{
s.push(n);
n = n.next;
}
return s;
}
public static Node getIntersect(Stack <Node> a, Stack <Node> b)
{
if(a.peek() != b.peek())
return null;
else
{
Node intersectNode = a.peek();
while(!a.isEmpty() && !b.isEmpty())
{
if(a.peek() != b.peek())
return intersectNode;
intersectNode = a.peek();
a.pop();
b.pop();
}
return intersectNode;
}
}
}
/* I m returning NULL for no common node and next node of *head1 or *head2 if common */
struct node findcommon_node(struct node *head1,struct node *head2)
{
if(*head1==NUL L&& *head2==NULL)
return NULL;
while(*head1!=NULL && *head2!=NULL)
{
if(*head1->next != *head2->next)
{
Head1=head1->next;
Head2=head2->next;
}
elseif(*head1->next !=NULL && *head2->next !=NULL)
return *head1->next ;
return NULL;
}
return NULL;
}
disregard previous one
findIntersectoin(node *p, node *q)
{
int d1=0,d2=0;
node* x=p;
while(x)
{
d1++;
x=x.next;
}
x=q;
while(x)
{
d2++;
x=x.next;
}
int d;
if(d1>d2)
{
d=d1-d2;
while(d>0)
p=p.next;
}
else
{
d=d2-d1;
while(d>0)
q=q.next;
}
while(p && q)
{
if(p==q)
return p;
p=p.next;
q=q.next;
}
return null;
}
If you want to do in a single scan you need to use stack. As you know 2 stack, you can use reccurssion [ correct me if I am worng ]. Following is the C++ version of the algo :
Node* intersectionPoint( Node* L1, Node* L2)
{
if( (L1 == NULL) || ( L2 == NULL))
return NULL;
Stack* stack1 = new Stack;
Stack* stack2 = new Stack;
while( (L1 != NULL) || (L2 != NULL) )
{
if( L1 != NULL )
{
stack1->push(L1);
L1 = L1->next;
}
if( L2 != NULL )
{
stack2->push(L2);
L2 = L2->next;
}
}
Node* node1, node2, prev = NULL;
while( !stack1->empty() && !stack2->empty())
{
node1 = stack1->pop();
node2 = stack2->pop();
if( node1 == node2 )
{
prev = node1; // you can keep node2 also
}
else
return prev;
}
return prev;
}
1) To find if the lists intersects scan each one till last element. If last element of list1 equals last element of list2 then they intersect. Solution involves one scan of each list.
2) To find the intersection in O(n) and O(1) I would do the following:
a) Count number of elements in each list. This can be done in O(n1+n2).
b) Traverse list#1 and while doing so - reverse it, i.e. each node now points to the previous node instead of next node. This can be done in O(n1).
c) Traverse list #2. What will happen is that once it will reach the intersection it will not "continue" to the shared nodes but will " go back" to the beginning of list #1. This can be done in O(n1+n2). Count the number of elements encountered in this scan. Refer to it as n2*
Suppose list #1 has 100 independent nodes and 20 shared nodes. and suppose list #2 has 5 independent nodes and 20 shared nodes.
The values of n1, n2 and n2* in this case will be:
n1 = 120 [ = 100 + 20]
n2 = 25 [ = 5 + 20 ]
n2' = 5 (the independent nodes) + 1 (the intersection) + 100 (the independent nodes of list 1)
What we're looking for is the number of shared nodes.
We'll get this by calculating:
(n1 + n2 - n2* -1) / 2 =
((20 + 100) + (5 + 20) - (5 + 100 + 1) - 1) / 2 = (20 + 20) / 2 = 20
All we have to do now is to start again from the last node and go back 20 nodes. This will be the intersecting node.
1) To find if the lists intersects scan each one till last element. If last element of list1 equals last element of list2 then they intersect. Solution involves one scan of each list.
2) To find the intersection in O(n) and O(1) I would do the following:
a) Count number of elements in each list. This can be done in O(n1+n2).
b) Traverse list#1 and while doing so - reverse it, i.e. each node now points to the previous node instead of next node. This can be done in O(n1).
c) Traverse list #2. What will happen is that once it will reach the intersection it will not "continue" to the shared nodes but will " go back" to the beginning of list #1. This can be done in O(n1+n2). Count the number of elements encountered in this scan. Refer to it as n2*
Suppose list #1 has 100 independent nodes and 20 shared nodes. and suppose list #2 has 5 independent nodes and 20 shared nodes.
The values of n1, n2 and n2* in this case will be:
n1 = 120 [ = 100 + 20]
n2 = 25 [ = 5 + 20 ]
n2' = 5 (the independent nodes) + 1 (the intersection) + 100 (the independent nodes of list 1)
What we're looking for is the number of shared nodes.
We'll get this by calculating:
(n1 + n2 - n2* -1) / 2 =
((20 + 100) + (5 + 20) - (5 + 100 + 1) - 1) / 2 = (20 + 20) / 2 = 20
All we have to do now is to start again from the last node and go back 20 nodes. This will be the intersecting node.
I think the question is not clear. Intersection does not mean inclusion. According to the question it does not have to be in "Y" shape it can be ">===<" shape. E.g. list1 = [1,2,3,4] and list2 = [0,5,2,3,6,7] so [2,3] is the intersected part and neither they end with the same node nor they start with the diff. And in this case no one can solve the problem with O(n) time and O(1) space complexity. You need to give more constraints.
I also thought like that initially. There can be 2 types. The one you are talking about is by-value. But the one solved above, is by-reference. If it is by reference then it has to be Y-shaped, since at the moment the 2 node reference matches then they will merge since the junction node is actually a single node referenced by 2 lists and then both the list should follow the same path by-reference. If it is by-value, then we need to have a different strategy which cannot be solved in O(n); the best will be sorting both the lists separately and then linear search to find the intersection nodes which will be then O(NlogN).
Two "standard" single lists (i.e. each node has only one "next" pointer) that are non-circular (must ask the interviewer) which instersects must have a Y shape where the upper side of the Y is the beginning of the list, with each node having its independent start, and from the node where they intersect they both must share the same nodes (the bottom part of the "Y") because from the intersection you can only go one way.
Count the number of elements in two lists.
Take the difference of count.
Traverse in longer list till the difference count.
Start traversing both lists & check for common address
It's not. It involves 2 scans on each of the lists. Suppose the number of elements in the two lists is n' = n1+n2 then you traverse each node twice, giving you 2xn' = O(n')
This is a great solution. The solution I suggest was similar but involved reversing one list. This one is much better as it does not require to destroy the list.
if ( (t1->next == NULL ) || (t2->next == NULL ) )
return false;
while (t1->next != t2->next )
{ t1 = t1->next
t2 = t2->next
}
if ( (t1->next == NULL ) && (t2->next == NULL ) )
return false;
else
return true
You could temporarily make one list a circular list and then do cycle detection on the other using either the tortoise and hare or Brent's algorithm. I don't see how it can be done in one iteration with constant space, unless each node already has e.g. a "visited" property but that is neither mentioned nor standard.
Actually after reading the question more closely I think the "one iteration" restriction does not apply to the second part of the question.
So in that case you can compare the tails for part 1 in one iteration; afterwards, if there is an intersection, use the above algorithm for determining its node in O(n) time and O(1) space (but not in one iteration).
1. Make first list circular by connecting last->next = first, also remember first and last node and also remember total nodes in first list.
2. Now iterate through second list and at iteration check whether last and first are matched. If at any point true then lists have an intersection point. Now this solves the problem in single iteration.
3. Now problem is finding loop start point in second list. This is traditinal problem.
4. After that remove loop from first list.
boolean intersect(Node head1 , Node head2){
Node current1 = head1;
Node current2 = head2;
while (current1.next != null)
current1 = current1.next;
while (current2.next != null)
current2 = current2.next;
return (current1 == current2);
}
Node intersect(Node head1 , Node head2){
Node current1 = head1;
Node current2 = head2;
int d1 , d2;
while (current1 != null){
current1 = current1.next;
d1++;
}
while (current2 != null){
current2 = current2.next;
d2++;
}
current2 = head2;
current1 = head1;
while (d2 > d1){
current2 = current2.next;
d2--;
}
while (d1 > d2){
current1 = current1.next;
d1--;
}
while (current1 != null && current2 != null && current1 != current2){
current1 = current1.next;
current2 = current2.next;
}
return current1;
}
{{
bool check(node *head, node *head1)
{
if(head == NULL && head1==NULL) return false;
else if(head == NULL || head1==NULL) return false;
else
{ while(head->next !=head1->next)
{
if(head->next ==NULL || head1->next==NULL) return false;
else { head=head->next;
head1=head1->next;
}
}
return true;
}
}
}}
to find the junction of two list. The solution is:
1. traverse through list1 and mark the data in the nodes with some special value say data multiplied by -1;
2. traverse through the list2 and check if any of the nodes any negative values.
3. if so, then that node itself is junction node.
Hello ,
assume these two link list are two lines.
1. It may corss one point means Shape is "X"
2. y
3. it may not cross ") (" but about to intersect.
The ans provided is wrong.
the question is wrong - Not by value but by reference ? what does it mean.
Some "J" will ask this Q - because he him self does not know what does it mean.
here we have to parts ...
- MVVSK December 05, 20121)Given two singly linked list, find if they are intersecting. Do this in single iteration.
a) traverse list1 and find the last element
b) traverse list2 and find the last element
c) check if last element of list1 == last element of list2 , if equal intersecting else not
here we have parsed the list only once :-)
2) Also find the intersecting node in O(n) time and O(1) space
here they have asked to do it in O(1) space so we need to use only one variable :-)
a) create a variable(int) diff=0
b) parse list1 and increment diff for each node
c) parse list2 and decrement diff for each node
d)if diff is > 0 list1 is bigger so push the pointer of list1 by diff times
else list2 is bigger so push the pointer of list2 by mod(diff) times
e)Now check if both the pointers are equal till we reach end