## Amazon Microsoft Interview Question for Software Engineer / Developers

• 3

Country: India
Interview Type: Phone Interview

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

here we have to parts ...
1)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

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

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.

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

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.

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

Hi Bevan ,
The question is : to find if to linked lists are intersecting ,if yes return the first intersecting node

Understanding question :

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

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

Awesome Man.. Thanks ... Understood the question now..

Did not get the "Y" Shape part of the question..Perfect ans then!! :)

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

Yes this is the same solution I gave and interviewer sounded pretty ok with this.

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

what if diff=0?

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

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

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

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

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;
}

{
int i = 0;
for(i = 1; i< num; i++)
{
}
}

{
{
}
}

{
int diff = 0;
while(temp)
{
temp = temp->next;
diff++;
}

while(temp)
{
temp = temp->next;
diff--;
}

if(diff < 0)
{
while(diff!=0)
{
diff++;
}
}

if(diff > 0)
{
while(diff > 0)
{
diff--;
}
}

{
}

{
printf("\nThese two lists wont intersect!");
}
else
{
printf("\nLists intersect at : %d", head1->data);
}

}

int main()
{
PNODE tail = NULL;
PNODE intersect = NULL;
int i = 0;

for(i = 0; i < 5;i++)
{
intersect = intersect->next;
}

while(tail -> next)
{
tail = tail->next;
}

tail->next = intersect;

clrscr();

getch();
}``````

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

1 2 3 4 5 6 7 8 9
^ ^

``````p1 = head1
while(p1 != p2)
{
p1 = p1 ->next;
}

if(p1 == NULL)
{
while(p2 != p1)
{
p2 = p2->next;
}
}``````

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

What about the case when the two linked lists do not intersect and they have same last element??? Isn't the proposition that if two linked lists have same last node, then they intersect flawed?

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

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

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

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.

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

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.

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

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;
}

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

Isn't this solution iterating over the linked lists more than once though? Or is that not what was meant by "one iteration"?

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

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

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

``````while(d>0)
q=q.next;

The value of "d" isn't getting updated in this loop.This results into infinite loop.``````

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

Also, if(p.data==q.data) is not correct. Here we are comparing nodes by reference and not by values since two different nodes may have the same value.
Rather, it should be: if(p==q)

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

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>

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

Just to update, keep on moving one node at a time and keep on comparing it.

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

1->2->3->4->5->6
9->10->3->4->5->6.
m-n=0;

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

Hey can two linked lists intersect? Two nodes wont have the same memory rite??

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

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.

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

Hi, I posted the original question. Yes, two linked lists can intersect. When that happens, it takes a 'Y' shape. Hence, from the point of intersecting node, all the nodes will point to same address

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

THANKX :)

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

Destructive solution:

 Scan one list, say listA and point every node until end, listA(1..n)->next to a special node called nodeIntersect.
 Now scan listB and see if currentNode->next==nodeIntersect. If so, currentNode of listB is the intersection point

Much less destrcutive, requiring additional space:

 Scan listA and add the nodes (the pointer) to a hashtable
 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.

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

just move till end on both the lists. compare the addresses of the last node. O(m+n)

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

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.

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

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

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

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

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

lol.

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

lulz...

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

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

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

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

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

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

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

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;
}

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

Kindly ignore the above post.This wont work.

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

node *temp, *prev;
while(temp != NULL)
{
stack_a.push(temp);
temp = temp->next;
}
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.

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

please factor in the presence of cycles too which could throw codes into infinite loops

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

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

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

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;

/**
* @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;
}
}
}``````

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

/* I m returning NULL for no common node and next node of *head1 or *head2 if common */
{
return NULL;
{
{
}
return NULL;
}
return NULL;
}

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

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;
}``````

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

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;
}

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

I did not see question completely... this will take O(n) space complexity...

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

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.

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

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.

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

I hope you asked if the lists can be circular.

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

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.

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

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

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

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.

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

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

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

Complexity is more than O(n).

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

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.

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

int main()
{

set < char > set0;
cin >> s ;
cin >> t ;

cout << s << " " << t << endl;

for (int i=0; i<strlen(s); ++i) {
set0.insert(s[i]);
}
for (i=0; i<strlen(t); ++i) {
if (set0.find(t[i]) != set0.end())
{
cout << t[i] << endl;
}
}

return 0;
}

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

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

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

The 2 lists don't necessarily have equal lengths though...

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

If two singly linked lists are intersecting, the last nodes have to be the same. Just check the last nodes of both lists, you are done!

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

``````if(head1 == NULL || head2 == NULL)
return NULL;

while(true)
{

//reached end of both list
return NULL;

}``````

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

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.

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

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

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

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

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

``````boolean intersect(Node head1 , Node head2){
while (current1.next != null)
current1 = current1.next;
while (current2.next != null)
current2 = current2.next;
return (current1 == current2);
}

int d1 , d2;
while (current1 != null){
current1 = current1.next;
d1++;
}
while (current2 != null){
current2 = current2.next;
d2++;
}
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;
}``````

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

{{
{
else
{
}
}
return true;
}
}
}}

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

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.

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

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.

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.