## Microsoft Interview Question for Software Engineer / Developers

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

1.Find whether you have the cycle. At the end of it you will have fast ptr = slow ptr
2.Find the length starting from the next node of the slow ptr to the slow ptr = length of loop
3. Find length from head node to slow ptr
4. These are basically two linked lists whose length we just found. Use their lengths to find common node.
4.1 Advance difference number of nodes in longer list and then start one node at a time in both lists till you hit the common node. That way you get the length till the common node.
5.Sum up the two lengths to find length of the entire list.

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

Good solution!

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

Very Nice... Perfect...!!!

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

Can anyone please explain the algo with an example?

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

Awesome sol "my solution"...!!!!

Here I am explaining ur algo. with an ex.
---------------------------------------
As singly link list can point to only one node hence the looping can occur from the "last_node" to "any_node" in the list.

a->b->c->'d'->e->f->g->h->'d'->i->j //this is not possible

so the possible link list is:
a->b->c->d->e->f->g->h->i->j->k->l->m->n->o->p->h

list is entering in loop at node 'h'.
----------------------------------------
Step1: by using slow and fast pointer we got node "k" which must be in loop. "slowPointer=fastPointer=[k]".
//we r assuming [k].Algo is fine with any node in loop [h] to [p].
-----------------------------------
step2: (*length of list=no. of nodes)
the length of loop we can calculate from [l] to [k] is '9'.
-----------------------------------
step3: (*length of list=no. of nodes)
the length from head to "slowPointer=fastPointer=[k]" is '11'
-----------------------------------
step4.1: difference b/w two calculated length = mod(11-9) =|11-9| = '2' //should be always +ve.
now take a pointer ptr which will start from 'b'(In length '2' from head).

slowpointer is still pointing to[k].(slowPointer=fastPointer=[k])

move both of the pointer "slowPointer" and "ptr" one by one until they do not having same node [h] and increase a 'length' variable to count traversed node. we will get the first looping node from where loop is getting start.

calculate the accurate length of linklist.

loopLength=9
length=6

Actual Length

=(11-9)+6+9-1
=2+6+9-1

*(-1)because we have calculated one common [h] node two times.
_________________________________________________________________________________________________

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

Thanks

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

Great Solution....You are hired...:)

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

1. To find the length of loop:
Pointer A advances one node a time. Pointer B advanced two node a time. Start from head, they advanced at the same time until B hit null(no loop) or A and B point to the same node.
Now, has A advances only, A would meet B again. You can find the length of the loop say L.
2. Start from head again, this time have a pointer C advances L note first, followed by pointer D behind it, each advances one node at a time. When they meet, the number of nodes D traveled L0 plus L is equal to the length of the linked list with a loop.

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

Kulang, in 2 if you traverse C and D by one node, how can they meet ? They just can't meet!

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

perfect solution.

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

How about setting up a hash table that would have references of each visited element in the linked list and then simply iterating through the linked list? Each time we are at an element we check if its reference is in our table and if not, we put it there and increment the element count. When we find that one of the elements has already been visited, we break the loop and return the element count.

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

assume linked list length is 1 million. would you still choose hash?

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

Here is one solution. Not sure if anyone can come up with a better solution

node* detectloop(node* first) //Detects the loop in a given linked list
{
node *trav1, *trav2, *loopNode=NULL;
trav1=first;
if(trav1&&trav1->next!=NULL)
trav2=trav1->next->next;

while(trav1!=NULL || trav2!=NULL)
{
if(trav1==trav2)
{
loopNode=trav2;
break;
}
trav1=trav1->next;
if(trav2->next==NULL)
break;
trav2=trav2->next->next;
}
return loopNode;
}

long lengthOfLoop(node* first)
{
node *loopNode=detectLoop(first), *trav;
long count=0;
if(loopNode==NULL)
return count;
trav=loopNode;
while(trav!=loopNode)
{
count++;
trav=trav->next;
}
return count+1;
}

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

you need to return the length of linklist, not the length of circule

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

Is there a way we can format the code in here.

All the code what people post is so tough to read because of no indentation that just makes senseless. I hope Gayle is listening and may be can change the layout of site where we can put [CODE] and [/CODE] for indentation.

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

Comment removed due to profanity.

just know that you can surround your code with "

``" "``

" to format code

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

Anonymous,
Don't ruin the nice environment here, you asshole. If that's your nature, stick to commenting on youtube.

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

I would like to know to how many nodes a node can point to .. ie the number of pointers. if it was singly linked list then it would be a circular one.

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

In Linked list Node can point to only one node.
Example of Linked list with loop is
A=>B=>C=>D=>E=>F=>G=>C

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

Here is an O(n) algorithm.

Detect the start of the cycle using the slow pointer fast pointer method ---> O(n). Store the pointer of the cycle node in a temp.

Initialiaze a flag to 0;

Iterate through the list and check

{
if (head-> next == temp && flag==1)
return count;

flag=1;

count++;

}

Total time complexity is O(n) which is the best you can do in this case.

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

slow-fast pointer method cannot guarantee the node where the two pointers overlap is the "start" of the cycle, isn't it?

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

Here is a solution.

Suppose we have a link list like this: The answer should be 5. So total length of the link list is length visited without loop + length of the loop.

a -> b -> c ->d -> e ->c

1. use slow/fast pointer to find if there is a loop. have slow pointer go around to find the length of the loop. Call it LEN_LOOP.

fast = /*points to the place where slow and fast met */
length = 0;
while(slow->next != fast->next){
slow = slow->next;
fast = fast->next;
length++;
}
return (length + LEN_LOOP;

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

very good solution Daniel.

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

fast = /*points to the place where slow and fast met */
length = 0;
while(slow->next != fast->next){
slow = slow->next;
fast = fast->next;
length++;
}
return (length + LEN_LOOP; "

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

1->2->3->4->5->6->2

slow nd fast will meet at 6

now len_loop = 5

but slow->next = fast->next

so length of list = 5+0 = 5

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

Here is a solution.

Suppose we have a link list like this: The answer should be 5. So total length of the link list is length visited without loop + length of the loop.

a -> b -> c ->d -> e ->c

1. use slow/fast pointer to find if there is a loop. have slow pointer go around to find the length of the loop. Call it LEN_LOOP.

2.

``````slow = head;
fast = /*points to the place where slow and fast met */
length = 0;
while(slow->next != fast->next){
slow = slow->next;
fast = fast->next;
length++;
}
return (length + LEN_LOOP;``````

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

I don't think the slow and fast pointer method give you the exact beginning of the loop. Just a point in the loop, whose location depends on the length of the loop and the length of the first non-loop segment.

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

the slow and fast pointer method gives the solution to the begining of the loop.
check it..

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

@anonymous

You are right. But just continue the slow pointer and count the length until it reaches the beginning of the loop which we have already found using slow-fast pointer method.

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

I think depends on the where the first cycle item is....this algorithm will only worked in some certain cases but not all, consider a case like (a->b->c->d->e->b) this will end up at c and (a->b->c->d->e->a) will end at d, and this algorithm will no longer be suitable.

Also, isn't going to be infinite loop with
slow->next != fast -> next ??

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

small change is required in above algorithm
Steps:
1)Use slow and fast pointer to detect loop and then iterate slow pointer to find the length of the loop(LOOP_LEN).
2) now take two pointers P1 and P2
then start travsing the list. Whenever these two pointers will meet, it will be the starting point of the loop.
3) start from the Head of the list and count the number of nodes till the loop starting point found above(step 2). (COUNT)
total length of the list is COUNT+LOOP_LEN

Thanks

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

small change is required in above algorithm
Steps:
1)Use slow and fast pointer to detect loop and then iterate slow pointer to find the length of the loop(LOOP_LEN).
2) now take two pointers P1 and P2
then start travsing the list. Whenever these two pointers will meet, it will be the starting point of the loop.
3) start from the Head of the list and count the number of nodes till the loop starting point found above(step 2). (COUNT)
total length of the list is COUNT+LOOP_LEN

Thanks

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

small change is required in above algorithm
Steps:
1)Use slow and fast pointer to detect loop and then iterate slow pointer to find the length of the loop(LOOP_LEN).
2) now take two pointers P1 and P2
then start travsing the list. Whenever these two pointers will meet, it will be the starting point of the loop.
3) start from the Head of the list and count the number of nodes till the loop starting point found above(step 2). (COUNT)
total length of the list is COUNT+LOOP_LEN

Thanks

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

small change is required in above algorithm
Steps:
1)Use slow and fast pointer to detect loop and then iterate slow pointer to find the length of the loop(LOOP_LEN).
2) now take two pointers P1 and P2
then start travsing the list. Whenever these two pointers will meet, it will be the starting point of the loop.
3) start from the Head of the list and count the number of nodes till the loop starting point found above(step 2). (COUNT)
total length of the list is COUNT+LOOP_LEN

Thanks

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

The slow and fast pointer meets in some node in the loop. So sum of nodes in loop plus the number of nodes till this node will give a number greater than the original number of nodes.
So, start of the loop is to be found by using one more pointer that moves from the head and is compared every time with all the nodes in the loop. When both are equal, we get the start of the loop. Now count the no of nodes.

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

then you need space to store the references to every node in the loop. The number could be large if the cycle is big. In this case, to use hash table to store every node in the linked-list is better in terms of the complexity of the code.

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

Length of loop can be found out by :
Length of loop ll = FastPtr.length - SlowPtr.length

Since 2 ptrs are meeting at some node that is present int the loop. Once they meet, have 1 more ptr 'lenFinder' starting from HEAD, while slow ptr completing entire round of loop (i.e. it will perform 'next' operation ll times ) and each time compare with 'lenFinder' ptr. If slow ptr doesn't match with 'lenFinder' ptr,perform lenFinder -> next and increase the counter by 1. Continue rotating the slow ptr again and continue the process until there is a match.
Whenever there is a match, break,
length of list = ll + position at which 'lenFinder' met - 1.

``````lenFinder = HEAD;
nonLoopNodeCount = 0;
while(!found) {
int count = length of loop;
while(count != 0) {
if(slowPtr == lenFinder) {
found = true;
break;
}
slowPtr = slowPtr -> next;
}
lenFinder = lenFinder -> next;
nonLoopNodeCount++;
}
Length of list = nonLoopNodeCount + length of loop - 1;``````

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

Good logic mysolution.. works well :)

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

The one way to solve this could be
 keep storing the addresses of the nodes while traversing the list
 Match the next node's address in the stored addresses, if it matches that means the node just previous to it is causing the loop make prev node's next = Null and entries in the address array is the count of the elements

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

Another way Can be I will wrapper the existing node as follows

``````NodeWrap{
Node *node;
bool visited;
};``````

While traversing we will mark the visited node as well as count ,break and return when we find the visited node =1

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

what about keeping the address of first node in some variable say ,"start" and then traverse the list and the same time increment the length and check the address with the "start"

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

sak you and your solution suck ! its vague and is not going anywhere, not even a partial solution, suck ^ N.

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

``````bool FindLengthAndPossibleCycle(Node *head, int *length)
{
return false;
bool hasLoop = false;
*length = 1;
do
{
if(fastPtr)
{
fastPtr = fastPtr->next;
}
else
break;

if(slowPtr == fastPtr)
{
hasLoop = true;
break;
}

if(fastPtr)
{
fastPtr = fastPtr->next;
}
else
break;

if(slowPtr == fastPtr)
{
hasLoop = true;
break;
}

if(slowPtr)
{
(*length)++;
slowPtr = slowPtr->next;
}

}
while(true);
slowPtr = slowPtr->next;
while(slowPtr && slowPtr != fastPtr)
{
slowPtr = slowPtr->next;
(*length)++;
}
return hasLoop;
}``````

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

a -b -c - d
| |
e - |

fastptr = a c e d fastptr pointing to d

slowptr = a b c d e

length = 1 2 3 4 5

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

The answer of my solution is correct. Kindly do not post other solutions which are inefficient.

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

What solution?

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

O(n) solution :

1. Run the slow pointer and fast pointer algorithm. The point where you stop lets call it at node A.
2. Now get the two lengths like below:
2.1 - start from node A->next and come back to node A. Length = X.
2.2 - start from head and come to node A. Length = Y.
3. Now assume X > Y then calculate X-Y. Treat X as Y and v.v. if Y > X
3.1 - start from A->next go (X-Y) nodes further and mark is pointer m.
3.2 - start another pointer n from head and let pointer m and n go together they will meet at the node where the circle starts :) - yes they will. Lets say both of these pointers have traveled Z nodes.
3.3 - now length of the list = X + Y - (Y-Z) = X + Z.

Edit1:
Looks like this solution is already posted by "my solution" ...

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

``````1. run slow and first pointer algorithm and let P1 and P2 stops at a node A.( assuming startOne is the head of the list given)

2. break the list and create a start pointer  startTwo =  A->next; and  A->next = NULL; and keep P1 pointing to A.

3. Now find the lenth of two lists let as say L1 and L2. calcualte |L1-L2|

4. since P2 has no use, take P2 and one more new pointer P3.

5. Now lets say P2 = startOne and P3= startTwo

6. if L1 is greater move P2 to |L1-L2| times else move P3 |L1-L2| times.

6. now move P2 and P3 one one step ahead till both are same.let us say they moved m steps.

7. Now Total number of nodes =  L1+m if L1 is bigger else =L2+m if L2 is bigger.

7. now make P1->next = startTwo to restore the list``````

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

Detect loop point
By (Slow pointer and fast pointer approach), find the loop detection node

Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list
Traverse both the pointers one at a time
Both the pointers meet at the node because of which there is a loop in the linked list
------------
Use the standard fast and slow pointer algorithm find the loop detection point

Take two pointers P1 and P2 at loop detection point. Place pointer P1 at the same place and move P2 forward one step at a time. Repeat until both the pointers meet together. Keep a count variable incremented for every iteration which gives length of the loop. Let say the length is L1

Again take two pointers P1 and P2. P1 at the head of the linked list and P2 at the loop detection point. Forward both the pointers one step at a time. Repeat until both the pointers meet together. This procedure is equivalent to the one we use to calculate node that causes loop in a linked list. Keep a count variable incremented for every iteration which gives the length of the list until the merging point. Let say the length is L2
Now the length of the list that contains loop is L1+ L2

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

This is one way to find length of Linklist , where one reference jumping two place ahead.

public int lengthlist()
{
Node len=start;
int count=0;
if(len==null)
{
return 0;
}
while(len!=null&&len.next!=null)
{
len=len.next.next;
count++;
}
if(len==null)
{
return 2*count; // for even length list
}
else
{
return 2*count +1; // for odd length list
}
}

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.