## Expedia Amazon NVIDIA Knoa Software Apple Interview Question for Software Engineer / Developers Interns

Comment hidden because of low score. Click to expand.
4
of 8 vote

O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

// Best solution

function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode = startNode;

while (slowNode && fastNode)
{
if (slowNode == fastNode) return true;
slowNode = slowNode.next();
fastNode = fastNode.next();
if (slowNode == fastNode) return true;
fastNode = fastNode == null? null : fastNode.next();
}
return false;
}

This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

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

The algorithm is the right one, but at least you need to check your written code performs correctly before posting it

Your slowNode and fastNode started as the same node, so it will always return true

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

Pointers moving at different rates:

Pointer b moves 1 step ahead every time that pointer a moves 2 steps ahead. If there is a loop, eventually they will both enter it, and at some point because they are moving at different rates, they will be equal. If they are ever equal, you have a loop.

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

yes using two pointers works well .

other algo may be as follows:

reverse the linked list from .
while reversing if u start from first node.
after starting reversing if u find first node again .
there is loop in linked list.

reverse it again to find original list.

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

plz correct it if i m wrong, the cycle may not involve first node....
the algo by tyler seems correct without any memory overhead....
other approaches can be by using hashmap or by associating flag with each node to keep track if a node is already visited or not, although it involves memory overhead.

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

typedef struct node Node;
struct node {
Node * next;
};

bool is_cyclic(Node * list)
{
if(!list || !list->next) return false;
if(list->next == list) return true; // one element list pointed to himself

Node * first = list;
Node * second = list->next->next;

bool result = false;
while(second) {
if(first == second) {
result = true;
break;
}
first = first->next;
if(second->next == 0) { break; }
second = second->next->next;
}

return result;
}

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

<pre lang="java" line="1" title="CodeMonkey15826" class="run-this">// Here is the C# code.
public bool FindALoop()
{
{
return false;
}

while (slow.Next != null && fast.Next.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
if (slow.Equals(fast))
{
//Found a loop
return true;
}
}
return false;
}</pre><pre title="CodeMonkey15826" input="yes">
</pre>

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

try to travell to NULL
if u reach start again,there is a loop.

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

What if the loop does not contain the head of the list ?

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

Consider a linked list which has a head (reference to the first node) and a current pointer. Traverse the loop and if at any point of time current-> next == head, voilla! you got a loop.

while( current.next != null ) {
if( current.next == head ) {
System.out.println("Loop detected!");
break;
}
current = current.next;
}

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

The above case covers the case where the loop is formed by connecting the last node to the first. In the case where the loop does not connect the end to the head, you could determine it as follows:
Consider two pointers, one traversing at twice the speed of the first. If there is a loop, there will be a point where the two pointers will meet, thus validating that a loop does exist!

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

add an extra flag field to each node..
while traversing the list set the flag bits, if an already set flag is encountered the list has a loop.

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

I don't think they would have let me add a flag, hence they wanted me to do the two pointers trick apparently ...

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

bool DetectLoop(NODE First, NODE Second)
{
if(First == Second) return true;

if(second && second->next && second->next->next)
return DetectLoop(First->next,Second->next->next);

else return false;
}

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

bool DetectLoop(NODE First, NODE Second)
{
if(First == Second) return true;

if(second && second->next)
return DetectLoop(First->next,Second->next->next);

else return false;
}

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

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

use two pointers slow and fast,...
every iteration slow travels 1 node and fast travels two nodes.. eventually fast will be behind slow if there is a loop ..

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

use fast and slow pointer....if fast==slow loop exist otherwise no loop....
but the real challange is how to remove the loop...
I have found it in the folowing...
goursaha<dot>freeoda<dot>com
goursaha<dot>freeoda<dot>com<slash>DataStructure<slash>LoopDetectionInLL<dot>html

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

I am writing only the function, rest is pretty much decoration !!!

int detectloop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while(slow_p && fast_p &&
slow_p->next &&
fast_p->next &&
fast_p->next->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}

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

Use 2 pointers to begin with. Move one pointer at double the speed of the other. if there is a loop, then they would be equal at one some point.

bool checkLoopPresent(Node *list){
Node *p1,*p2;
if (list == NULL) return false;
p1 = list;
p2 = list->nxt;
while((p1 != p2) && (p2 !=NULL) && (p2->nxt!=NULL)){
p1 = p1->nxt;
p2 = p2->nxt->nxt;
}
return p1==p2;
}

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

this is not correct solution... check it out...

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

You are right Danny, the code wont work although the logic is correct.

the while should be -

while((p1 != p2) || (p2 !=NULL) || (p2->nxt!=NULL))

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

Nice solution by Neo above.

One other approach. We can use hash set to keep the distinct nodes.

Set nodeSet = new HashSet();
if(first !=null){
Node ptr = first;
while(ptr !=null){
if(nodeSet.contains(ptr)){
return true;
}
else {
}
ptr= ptr.getNext();
}
}
return false;
}

And Node class is ->

public class Node implements Cloneable{

private String value;

private Node next;

public String getValue() {
return value;
}

public void setValue(String value) {
this.value = value;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public Object clone(){
try {
Node clonnedNode = (Node)super.clone();
clonnedNode.next= (Node)next.clone();
return clonnedNode;
}
catch(CloneNotSupportedException cnse){
return null;
}
}

}

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

hiiiii

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

Agree wid NEO... it will work in all cases..!

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

use two pointers:

bool HasLoop( Node *L )
{
Node *n1, *n2;
if( !L )
{
return false;
}

n1 = L;
n2 = n1->nxt;
while( n2 && n2->nxt )
{
if( n1==n2 || n1==n2->nxt )
{
return true;
}
n1 = n1->nxt;
n2 = n2->nxt->nxt;
}
return false;
}

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

wat about something like this n1->n2->n3->n4->n2. I think this is a loop too

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

correct it is a loop..bt representation should be....
___________
! !
n1->n2->n3->n4-!

becaz two node are same only when their address r same...

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

*diagram.
____________
|..........^
n2->n3->n3-|
^
|
n1

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

Maintain two pointers to traverse through the linked list, pointer1 & pointer2
do
pointer1 = pointer1->next;
pointer2->pointer2->next->next;
while(pointer2 && pointer2->next) //check for null condition, which if hit means no loop

the slower pointer1 will eventually catch up with faster pointer2 if there exists a loop.

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

The code for this problem would be:

boolean isCircular(node root)
{
if (root != null)
{
node slow=root;
node fast=root.next;

while ((fast!=null)&&(fast.next!=null))
{
if (fast==slow)
return true;
slow=slow.next;
fast=fast.next.next;
}
}
return false;
}

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

>while ((fast!=null)&&(fast.next!=null)) <
will turtle into an infinite loop if the LL is cyclic

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

bool FindInList(stList* pList,stList* pList2)
{
bool bReturn = false;
stList* pList1 = pList;
if(pList1 == NULL || pList2 == NULL)
return bReturn;
while(pList1 != pList2)
{
if(pList1 == pList2)
{
bReturn = true;
break;
}
pList1 = pList1->pNList;
}
return bReturn;
}

bool FindLoop(stList* pList)
{
bool bReturn = false;
stList* pTemp = pList;

if(pTemp == NULL)
return bReturn;

while(pTemp != NULL)
{
if(FindInList(pList,pTemp))
{
bReturn = true;
break;
}
pTemp = pTemp->pNList;
}
return bReturn;
}

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

worst case O(n2) right but any body got O(n)solution for find the particular node where the loop starts

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

worst case O(n2) right but any body got O(n)solution for find the particular node where the loop starts

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

the above code wont work please dont put the code before verifying it

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

Am trying to use the length of list
and incrementing the counter to check if its equal to list size
is this correct. thnx

{
counter = 0;
int len =  list.size();
while(cur!=null)
{
cur=cur.next;
counter++;
if(counter == len)
return false;
}
return true;
}

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

This can be done using 3 pointers
1. Take a slow runner(Increase with one ) and a first runner(increment twice) approach to find the linklist is circular or not. If slow runner == fast runner then loop is circular.
2. Once you find the list is circular then loop the slow runner by one and the third pointer(which is now pointed to head) . Where they collide you can reach to the start of loop.

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

I guess it is good know about other algorithms besides Floyd's:

//Algorithm invented by Richard P. Brent and runs in O(n) time.
//Outline: initially rabbit and turtle starts
// off at same position however only rabbit moves by a step
// and checks if it meets the turtle. When it does
// not after a certain number of steps, the stationary
// turtle will be teleported to rabbit's position.
// The step counter as well as the limit of steps will
// will be reset. and rest of the actions just repeats.

//Algorithm starts here:

//we start from 1st element, other wise
//we could have started from head as well

steps_taken = 0
step_limit = 1        //1=2 power 0

forever:
if rabbit == end:
return 'No Loop Found'
end-if

rabbit = rabbit->next
steps_taken += 1

if rabbit == turtle:
return 'Loop found'
end-if

if steps_taken == step_limit:
steps_taken = 0
step_limit *= 2
// teleport the turtle
turtle = rabbit
end-if
end-forever

//Explanation: As we see that the turtle always sits at one position
// and rabbit moves to see if it meets the turtle. If it meets we
// have a cycle otherwise, let's just move the turtle directly to
// the position of rabbit instead of moving the turtle step by step
// as in Floyd's algorithm.
// We can see that such tele-porting of turtle would continue until the
// rabbit hits/enters the cycle. Once in side the circle it may happen
// that the rabbit still doesn't meet the turtle because the turtle is
// outside the loop (in fact haven't hit the loop yet). In such case
// turtle will be teleported again inside the loop skipping all nodes
// in between. Once both of them inside the loop, since turtle just
// sits there and rabbit makes moves, rabbit is bound to meet the turtle.
// If the step_limit is less than the loop size then even starting at inside
// the loop rabbit won't meet the turtle and the turtle will be teleported
// to a new location yet inside the loop. Since after each teleporting the
// step_limit increase (by two fold in this case), at some point of time,
// step_limit will be greater than loop length and then moving rabbit
// will move through the loop to meet the stationary turtle.

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

It's called the turtle and the rabbit algorithm. O(n).

for (p = L, q = L->next; p || q; p = p->next, q = q->next)
if (p == q) {
printf("Loop from %d to %d.\n", p->info, q->info);
break;
}

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

Different Solutions :

1.Floyd Cycle
2.Use a hash table and check whether the element exists or not.
3.Add visited nodes and check whether the current node has already visited or not using that list.

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

you morons!
2 pointer solution is the standard way of solving this problem. i guess you guys had been rejected right after that interview. Oh Jesus! help these poor souls

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.