## Harman Kadron Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

``````Node* findLoopNode(Node* LL){
if(!LL) return NULL;

else if(LL->next == LL) return LL;
//the linked list contains only one node which points back to itself

else{

head = fast = slow = LL;

do{
if(!fast->next && !fast->next->next)
fast = fast->next->next;
else return NULL;// there is no loop

slow = slow->next;
}while(fast!=slow);
//there is a loop and the below snippet finds the node pointed back
fast = fast->next;
}

}
}``````

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

Hi Ashish,
first of all, Nice code. But i didn't understand the below code snippet logic.

//there is a loop and the below snippet finds the node pointed back
fast = fast->next;
}

Is it true that "fast" and "head" points move the same distance before reaching the intersection node.
My understanding is that "head' point needs to move it's pointer for each cycle (fast) and check whether head and fast pointers are equal.

Can you explain this code snippet logic ?

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

Yes, it will always be true that "fast" and "head" points move the same distance before reaching the intersection node. You can do a dry run by taking an example which will clear your doubt.

Also I did a mistake in the above code which I have rectified :
this

should be

head = fast = slow = LL;

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

Hi Ashish,
I'm confused with below:
if(!fast->next && !fast->next->next) -- why inverted values?
It'd be good if you can briefly comment how this overall code is working:

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

I think moving one pointer twice at speed of other is self evident, its like two people jogging on a circular track. the faster one will eventually meet the slower one.
Finding the node where the loop begins is interesting.

Lets say fast and slow meet at point p

loopBegin->meetingPoint = y
meetingPoint -> pointingToLoopbegin = z

distance travelled by slow node = x +y
distance travelled by faster one = x + y + z + y

so as t = d/s and t(slower) = t(faster)
(x+y)/s = (x+2y+z)/2s
solving it will give x = z;

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

How will you make sure that this logic will always work.
I mean, is there any mathematic model or anything to proof that this is an impeccable model.

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

``````int Check_Loop(Node head)
{
Node temp,prev,curr;

if(temp==NULL) return 0;
if(temp->next == temp) return 1;

while(curr!=NULL)
{
if(prev->next==cur->next)
return 1;
else {
prev=prev->next;
curr=curr->next->next;
}
}
return 0;
}``````

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

I think we could simply maintain a list of visitedNodes. So during iteration if we find any node thats already part of visited node list then we could say we have loop provided the list does not any duplicates.

If duplicates we need to come up with hashcode for each node and do comparison. Hope that make sense. Anyways following is the java snippet that should tell you loops and the link thats actually causing the loop (for no duplicates scenario)

``````List visitedNodes = new ArrayList();
ListNode prevNode = null;

while(!visitedNodes.contains(tempNode) && tempNode.nextNode != null){
prevNode = tempNode;
tempNode = tempNode.nextNode;
}

if(tempNode.nextNode != null){
System.out.println("Link from "+ prevNode.toString()+ " to " + tempNode.toString() +" causing cycles");
}``````

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

You don't have to use a "visited flag" or additional information, just a slow iterator and a fast iterator. The " The Tortoise and the Hare Algorithm".

``````// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}``````

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

Can be solved using Floyd's Algorithm of Cycle Detection:

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

You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked 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.