Monday, July 11, 2016

Loop Detection - Cracking Coding Interview

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

First, meeting point of two pointers in a loop

Consider two pointers: a slow pointer S that increments by one node at each step, and a fast pointer F that increments by two nodes at each step (i.e. it is twice as fast as S). Both pointers start at the same time from the beginning of an n-node loop. In the time S covers n nodes. Fwill have covered 2n nodes and they will both meet at the start of the loop.
Now, let us say that the slow pointer S starts at the beginning of the loop, and the fast pointer F starts at node k (where k < n) of the loop. As these two pointers move along the loop, they will meet at node (n-x).
What we really need to do is figure out x, as it will give us the node at which the two pointers meet inside the loop.
1. When S takes n/2 steps, it will be at node n/2. During the same time, F will have taken 2(n/2) = n steps, and it will be at node (k+n). Since the we are inside a loop, F will be effectively back at node k.
2. In order for the two pointers to meet at node (n-x)S needs to take a further (n-x-n/2)=(n/2-x) steps and it will end up at node n-x. During the same time, F will have taken 2*(n/2-x)=(n-2x) steps and will be at node k+(n-2x). Given our assumption that both S and F meet at the same node:
This means that if S starts from the start of the loop, and F starts k nodes into the loop, both of them will meet at node (n-k), i.e k nodes from the end of the loop. This is a key insight.

public static boolean hasLoop(LinkedList linkedList) { if (linkedList == null || linkedList.getHead() == null) { return false; } IntegerNode slow = linkedList.getHead(); IntegerNode fast = linkedList.getHead(); while (true) { slow = slow.getNext(); if (fast.getNext() != null) { fast = fast.getNext().getNext(); } else { return false; } if (slow == null || fast == null) { return false; } if (slow == fast) { return true; } } }

// Find meeting point
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}

// Error check - there is no meeting point, and therefore no loop
if (fast == null || fast.next == null) {
return null;
}

/* Move slow to Head. Keep fast at Meeting Point. Each are k steps
/* from the Loop Start. If they move at the same pace, they must
* meet at Loop Start. */
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}

// Both now point to the start of the loop.
return fast;
}

Why increase pointer by two while finding loop in linked list, why not 3,4,5?

So, the condition here is you cannot change the speed of ptr1, it has to move one node at a time.
but the choice for ptr2 to move can be 2 nodes at a time, 3 nodes at a time or any number of nodes at a time.

More the gap in which both pointers move forward, more the time they might take in worst case to meet.
So the lowest possible iteration in which we can find their meeting points is by moving ptr2 two nodes at a time.