Microsoft Interview Question Software Engineer / Developers
What you need:
two ptrs - a fast ptr and a slow ptr
fast ptr is always one node ahead of the slow ptr
Whenever the slow ptr leaves a node it marks that node - say alters the data such that if data=5 it makes it 5000.
Whenever the fast ptr arrives at a node it checks if the node is marked -- say checks if data/1000 is an integer.
So if your linked list is like this:
O---O----O-----O-----O---O
....|____________________|
Step(1):
f,s
.O---O----O-----O-----O---O
.....|____________________|
Step(2):
.....s....f
.@---O----O-----O-----O---O
.....|____________________|
Step(3):
..........s.....f
.@---@----O-----O-----O---O
.....|____________________|
Step(4):
................s.....f
.@---@----@-----O-----O---O
.....|____________________|
Step(5):
......................s...f
.@---@----@-----@-----O---O
.....|____________________|
Step(6):
.....f....................s
.@---@----@-----@-----@---O
.....|____________________|
Here f checks if @/1000 = O and it is true so we found the last node in the list which is pointed to by 's' which is the slow ptr
Only thing is how to mark the nodes properly. obviously multiplying by 1000 might not work in all cases. Need some unique function.
There is no solution! Where do a circle end or begin? Which comes first the Chicken or the egg?
step 1: Do slow pointer and fast pointer stuff. Start counter M when they start traversing. and stop the counter when they meet ( Mth node from list head)
step 2: Now from meeting point. Start another counter C and move slow pointer until it meets fast pointer ( C is the size of the loop)
step 3: (C - (M - C) )th node from the meeting place is the node you want.
You can also do it with o(1) space and o(n^2) time.
I'll post an algorithm if no one else comes up with it.
Hi,
if there is O(n) space then
following solution works
store the node's ptrs in an array of linked list while reversing u will end up where u started.
again reverse it comparing with the ptr stored in array . first time when it doesnt match. the ptr stored in last index which matches is the start of the loop.this time u will end up with original linked list.
ravi_cdotd@yahoo.co.in
//loop is detected by reversing the link list now to regain original list it has been reversed once more.
#include<stdio.h>
struct lnlst{
int info;
struct lnlst *next;
};
struct lnlst* reverse(struct lnlst* ,struct lnlst * []);
void main()
{
struct lnlst *ls,*temp,*ptr;
struct lnlst *a[100],*b[100];
int i;
//Preparing a linked list with loop
ls=(struct lnlst*)malloc(sizeof(struct lnlst));
ls->info=15;
temp=ls;
for(int i=0;i<10;i++)
{
temp->next=(struct lnlst*)malloc(sizeof(struct lnlst));
temp=temp->next;
if(i==5)
ptr=temp;
temp->info=i;
}
temp->next=ptr;
// temp->next=NULL;
// link list preparation completed.
//printing link list
temp=ls;
printf("\nData with index:");
for(int i=0;i<30 && temp !=NULL;i++){//15 elements are displayed to include loop
printf("\t(%d)%d",i,temp->info);
temp=temp->next;
}
//printing completed
temp=0;
//reversing first time.
temp=reverse(ls,a);
if(temp==ls)
printf("\nNOTE:There is Loop in the link list");
ls =temp; //it is included to cater if there is no loop.
//reversing second time.
ls=reverse(ls,b);
//printing addresses
printf("\ni a[i] b[i] ");
i=0;
while(a[i] && b[i]){
printf("\n%d %ld %ld\n",i,a[i],b[i]);
i++;
}
//printing addresses completed
//comparing addressed
i=0;
while(a[i]==b[i])
i++;
printf("\n\nLoop starts from node address: %ld at index %d\n",a[i-1],i-1);
}
struct lnlst* reverse(struct lnlst *ls ,struct lnlst* ar[])
{
struct lnlst *temp,*prev,*current;
int i=0;
prev=0;
temp=0;
current=ls;
ar[i++]=current;
while(current->next)
{
temp=current->next;
current->next=prev;
prev=current;
current=temp;
ar[i++]=current;
}
ar[i]=NULL;
current->next=prev;
return(current);
}
To find the node which forms the start of the loop:
1. use the double pointer (p and q) technique to establish that a loop exists. If a loop does exist, then the pointers meet on a node forming the loop.
2. if a loop does exist, then for each node (use a third pointer here, r) starting from the head, we check if it forms the start of the loop by using p to loop around and checking on each iteration if it meets r. If it meets then node r is the one, else increment r and repeat step 2
Step 1 requires O(n) time, while step 2 requires O(n^2) time. However, it requires O(1) space.
Is it possible in O(n) time and O(1) space??
struct Node{
bool fVisited; // initialized to false before calling FindBrokenLink
Node *pNext;
};
Node* FindBrokenLink(Node* pStart)
{
Node* pCurrent = pStart;
while(pCurrent)
{
Node* pNext = pCurrent->pNext;
if(pNext->fVisited)
return pCurrent; // this is where the last node pointing somewhere in the middle
pCurrent = pNext;
pCurrent->fVisited = true;
}
}
Oops one correction
struct Node{
bool fVisited; // initialized to false before calling FindBrokenLink
Node *pNext;
};
// return_value == NULL : no circular refs
// return_value != NULL : pointer to the circular reference
Node* FindBrokenLink(Node* pStart)
{
Node* pCurrent = pStart;
while(pCurrent)
{
Node* pNext = pCurrent->pNext;
if(pNext->fVisited)
return pCurrent; // this is where the last node pointing somewhere in the middle
pCurrent = pNext;
pCurrent->fVisited = true;
}
return NULL; // no broken links
}
I feel this should work...
fast=head;
slow=head;
fast -> intially incremented by two. fast=fast->next->next
slow -> incremented by one. slow=slow->next;
while(true){
if(fast==null || fast->next==null)
return null;
if(fast==slow || fast->next==slow)
break;
fast=fast->next->next;
slow=slow->next;
}
thirdPtr=head;
while(true){
if(thirdPtr==fast || thirdPtr == slow)
break;
thirdPtr=thirdPtr->next;
}
return thirdPtr;
}
The idea is that by this method either fast or slow would end up pointing to the start node. To find which is first we need a third ptr. The ptr tht the third ptr meets is the start. Anyone can prove me wrong?
I think i missed one case where the last pointer points to the first node, then when the cycle is detected the slow will be always at the tail ptr. Hence when fast is incremented everytime, it needs to be checked if it passes through the head, if true then return the head ptr. I guess only this case is special, for the rest it hold good --> where the tailptr points to a node other than the head.
IMHO, the circularity can be found by having two ptrs both starting at the head, with ptr1 incrementing by one while ptr2 incrementing by 2. We can detect circularity when ptr1==ptr2. If we have counters for each of the ptrs say c1, c2, respectively; we have this simultatneous eaqution :
p + k = c1 //where p is prefix length before the start of the cycle
p + 2k = c2 // k is the lenght of the cycle.
If we solve for p we get p = 2c1 - c2; and thats how far the cycle starts from the head of the original list.
Slow pointer and fast pointer works ... .but it tells that there is a cycle ... to find where the cycle starts..
Initially save the position where the slow and fast meet ( they always meet within the cycle)
Now from the head count the number of nodes in between the head and the saved node.
Now do it again till the next node of the saved node(save the node i.e.,(savednode->next) inplace of the saved node) ...do this process it untill the counter decrements.
Once the counter decrements the savednode is the last node of the cycle.
I believe my aglo works in O(n) time and O(1) space
p1 and p2 are two pointers
p1 travels 2 times faster than p2 and will meet because of the loop.
then from this point we can get the number of nodes in the loop by walking around the loop once again. and also we can get the number of nodes in the list by walking from header and stop when meeting p1 twice.
from the diffrence between those two numbers, finding the starting node of the loop is easy.
Can anybody really come up with a O(n) time and O(1) space algo?
To sum up the above algos, a typical 2-phase algo is:
-----------------------------------------------------
step1: find the loop. O(n) time and O(1) space.
-------------------------------------------------------
step2: find the meeting node. I can think of two ways:
algo 1. use 2 stacks, stack 1 is used to record all the nodes starting from head. stack 2 is used to record all the nodes starting from step1. And then pop the nodes from the 2 stacks to see if they match. This algo use O(n) space.
algo 2. use recursion method. This should be O(1) space. But I am not sure if this is doable.
Just figured out the algo posted by Anonymous on Saturday March 22, 2008. His algo should be O(n) time and O(1) space. I'd like to elaborate his algo:
see the length of the list (L1) starting from head is 10, and the length of the list (L2) starting from where the circle is found is 15, then start from L2[5], and L1[0], and compare the two nodes. so on and so forth, until find the first node that are equal.
after 1 month and I came back to see my post again, I am confused by myself. And it took me half an hour to figure out what I said. Let me try to explain it more clearly:
=================================
1. p1 and p2 meet at Node K.
2. calculate the size of the loop: starting from Node K, do iteration, i++, until it comes back to Node K again, and the size of the loop=i;
3. find where the loop start. use 2 pointers p1 and p2.
Initialization:
p1=List[0],
p2=List[i],
p1 and p2 step 1 node each time. and compare if p1==p2. If at Node N p1==p2, then loop starts at Node N.
package myLinkedList;
public class findCycle {
private class Node {
int data;
Node next;
}
Node head = null;
private void createList() {
if (head == null) {
head = new Node();
head.data = 15;
}
Node cur = head;
Node cycPtr = null;
for (int i = 0; i < 10; i++) {
Node temp = new Node();
temp.data = i;
cur.next = temp;
cur = cur.next;
if (i == 5) {
cycPtr = temp;
}
temp.next = cycPtr;
}
}
private void display() {
Node cur = head;
for (int i = 0; i < 25; i++) {
System.out.println(i + " " + cur.data);
cur = cur.next;
}
}
public Node reverse(Node a[]) {
Node cur, prev = null, temp;
cur = head;
int i = 0;
while (cur.next != null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
a[i++] = cur;
}
a[i] = null;
cur.next = prev;
return (cur);
}
public void checkCycle() {
Node a[] = new Node[20];
Node revHead = reverse(a);
if (revHead == head) {
System.out.println("Cycle Detected!");
}
}
public void checkCycleStart() {
Node a[] = new Node[20];
Node b[] = new Node[20];
Node revHead1 = reverse(a);
Node revHead2 = reverse(b);
int i = 0;
System.out.print("A : ");
displayArray(a);
System.out.print("B : ");
displayArray(b);
while (a[i] == b[i]) {
i++;
}
System.out.println("The cycle starts from " + i
+ "th node which is node " + a[i - 1].data);
}
public void displayArray(Node a[]) {
for (int i = 0; i < 20; i++) {
if (a[i] != null)
System.out.print(a[i].data + " ");
}
System.out.println("");
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
findCycle myObj = new findCycle();
myObj.createList();
myObj.display();
myObj.checkCycle();
myObj.checkCycleStart();
}
}
/* Output
0 15
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 5
12 6
13 7
14 8
15 9
16 5
17 6
18 7
19 8
20 9
21 5
22 6
23 7
24 8
Cycle Detected!
A : 0 1 2 3 4 5 9 8 7 6 5 4 3 2 1 0 15
B : 0 1 2 3 4 5 6 7 8 9 5 4 3 2 1 0 15
The cycle starts from 6th node which is 5
*/
struct node{
int data;
int flag=0;
node* next;
}
node* findStart(node* head){
node* curr=head;
while(curr!=NULL){
(curr->flag)++;
if(curr->flag==2)
return (node);
curr=curr->next;
}
return;
}
<pre lang="" line="1" title="CodeMonkey72781" class="run-this"> SingleLinkedListNode<int> normalNode = head;
SingleLinkedListNode<int> twoWayFasterNode = head;
while (twoWayFasterNode != null)
{
normalNode = normalNode.Next;
twoWayFasterNode = twoWayFasterNode.Next.Next;
if (normalNode == twoWayFasterNode)
{
normalNode = head;
while (normalNode != twoWayFasterNode)
{
normalNode = normalNode.Next;
twoWayFasterNode = twoWayFasterNode.Next;
}
break;
}
}
return twoWayFasterNode;
</pre><pre title="CodeMonkey72781" input="yes">
</pre>
Use the two pointer approach to detect cycles in a linked list (tekpool.wordpress.com/2006/09/27/linked-list-detect-a-cycle-in-a-linked-list-two-pointers-approach-slow/) and when ptr_first == ptr_second, print the node where this happens.
The link above only helps in detecting cycles, but does not help in finding where circular linked list starts.
as per this logic, 5 would be the output of where the circular linked list starts which is incorrect. The node should be 3.
1---2----3----4---5---6
| |
| |
--------------
Step 1 2 3 4 5 6 7 8
p 1 2 3 4 5
q 1 3 5 3 5
1. Save the position where the Slow and Fast pointers meet. (Say the point is 'A')
- N March 03, 20082. Find the loop count (i.e number of elements in the loop) - do this by keeping the Fast pointer at point 'A' and moving the Slow pointer one position at a time and incrementing the a counter. Say the counter reads 'S' when the Slow pointer meets the Fast pointer. This means the loop size/count is 'C'.
3. Now the point in the link list where the loop starts is the 'C'th node from the end of the link list. Now use the algo to find the 'n' node from the end of the link list and you have the answer.