Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

Archive for the ‘Linked List’ Category

Linked List: Detect a Cycle in a linked list and Fix the cycle

Posted by tekpool on September 29, 2006

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.

In the Previous posts, we discussed several ways to find cycles in a list, starting from some O (n^2) trival solutions, to the classic Flyod’s Cycle Finding Algorithm (also known as the Hare and Tortoise approach, or the 2 pointer approach) and a asymptotic faster variant, to a list reversal technique (which I havent seen being used anywhere). There are a few O(n lg n) solutions which I did not mentoin here. (If there is enought interest I will post this).

Lets look into a way to fix this cycle. Of Course, there are trivial O(n^2) solutions for this, but I will not go through this. I will discuss an O(n) solution in this post

Sol 6: Fixing the Cycle

A combination of the two O(n) cycle detecting algorithms (2 pointer approach and list reversal methods) will be used for this solution. Let’s look into an illustrative solution

Fig (i) is how the orignal list (with a cycle) will look like. The goal is to fix the cycle. This can be done by finding N3 and setting N3->Next to NULL. The question is how to we find this.

N0 is the head.

Run one of the Two-Pointer cycle finding methods that I disscussed before on this list. The two pointers will meet somewhere inside the loop (3-4-5-……10-11-3). Lets call the node that the

pointers meet as N1. Once the two pointers meet, hold one of the pointers(P1) at N1 and let the other other pointer(P2) traverse the cycle once, while keeping a count of the number of

nodes in the cycle. Let the number of nodes in the cylce be x. Now, point pointer P2 to the head of the list (N0) and run the traverse the list until you find N1 while keeping a count of

the number of nodes from the head N0 to N1. Lets this number be y.


N0            N2
0--->1---->2---->3---->4---->5---->6
                 |                  |
                 |                  |
            N3  111—->2—->310—->9—->8 N1

      Fig (ii)

After reversal get a count of nodes from N0 to N1. Let this number be z.

The idea is to get the number of nodes from N0 to N2. Once we have this, we can get the address of N2 and then traverse the list in the loop, until we find a Node whose next is N2 and then set it to NULL.

To solve this:

Our Variables:
Number of Nodes from N0 to N1 before reversal = y
Number of Nodes from N0 to N1 after reversal = z
Number of Nodes in the loop = x
Numver of Nodes from N0 to N2 = k

We need to solve for k. We have the following equation at hand.
y + z = 2k + x (This equation could differ slightly if the number of nodes caluclated were inclusive of the nodes or not)
k = (y + z – x) / 2

I will put the code in a later post.

Posted in Algorithms, Data Structures, General, Linked List, Progamming Languages | 16 Comments »

Linked List: Detect a Cycle in a linked list – List Reversal

Posted by tekpool on September 29, 2006

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a few soIutions prior to this. Lets look into an easy but not so commonly used solution.

Sol 5: Find Cycle through List Reversal

We’ve looked into some classic approaches of Linked List Cycle Finding Methods (Hare and Tortoise) in the previous posts. Lets see a more easier straightforward approach. I am a bit surprised this is not a usually used method.

The idea is pretty simple. Reverse the list!!. If you meet the head in the process of reversal, you’ve got a cycle. Below is some sample code for this. The exit condition, when you do not find a cycle is when you reach the tail node. Either ways the list needs to be reveresed again, so that we leave the list in its initial state.

void LinkedList::IsLooped1() {
LNode* prev=NULL;
LNode* current=NULL;
LNode* tmp=head;

while(tmp) {
    prev=current;
    current=tmp;
    tmp=tmp->next;
    if(tmp==head)
      cout < < "Found Loopn";
    current->next=prev;
}
head=current;
Reverse(); //Leave list in original state

}

Posted in Algorithms, C++, Data Structures, General, Linked List, Progamming Languages | 14 Comments »

Linked List: Detect a Cycle in a linked list – Two Pointers Approach (Faster)

Posted by tekpool on September 28, 2006

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 4: Two pointer approach (Faster)

In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.

What can you do here to make it faster. In the regular approach, the faster pointer goes 2 nodes at a time and the slower pointer goes 1 node per iteration. You cannot really change the speed of the slower pointer, because you definitely need to check every node at least once. But what about the fast pointer? Why just have it go 2 nodes per iteration? Why not 3 or more? And what improvements can you get here? Well. the faster it goes the lesser, the number of assigments and null checks when you traverse the faster pointer. This will be helpful, especially when the cycle (loop) is large. But how can fast do can you go. Since you don’t really know, you could do an exponential advancement. What this means is that, start with 2 nodes per iteration, and see if the slower pointer meets it. If not, traverse 4 nodes in the next iteration, and then 8, 16, 32…

Here’s some sample code that illustrates this.

void LinkedList::IsLooped2() { 
    LNode* first=head; 
    LNode* second=head;
int i=0; 
int k=1; 
while(first) { 
    first=first->next; 
    i++; 
    if(second==first) { 
            cout < < "Found Loopn"; 
            return; 
    } 
    if(i==k) { 
        second=first; 
        k*=2; 
    } 
} 

}


Posted in Algorithms, C++, Data Structures, General, Linked List, Progamming Languages | 2 Comments »

Linked List: Detect a Cycle in a linked list – Two Pointers Approach (Slow)

Posted by tekpool on September 27, 2006

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 3: Two pointer approach (Slow)

The Trivial solutions either took too long for eat more memory. Here is a classic well known appraoch the does constant space O(1) and 0(n) space. This is based of Floyd’s cycle-finding algorithm published in the Journal of ACM is his paper Non-Deterministic Algorithms in 1967. There are many variants and improvements to this original solution. These alogrithms can be used for finding cycles in different Data Strucutres. I will explain how it works when applied to Linked Lists

The idea is to use 2 pointers P1 and P2 intialized to the head. Then traverse the two pointers starting from the head, with P1 moving 1 node at a time and P2 moving 2 nodes at a time. If there is indeed a cycle, the nodes will meet inside the loop, otherwise they will reach the tail.

The code below is a simple straightforward illustration of this. There are ways to make this more efficient. I will discuss this in the next post.

bool LinkedList::IsLoopedTwoPointer1() {
 LNode* first=head;
 LNode* second=head;

 while(first && second &&
           first->next && second->next &&
           second->next->next)
{
first=first->next;
second=second->next->next;
if(first==second)
{
    cout < < "Found Loop" << endl;
    return true;
}
 }
 return false;

}

Posted in Algorithms, C++, Data Structures, General, Linked List, Progamming Languages | 3 Comments »

Linked List: Detect a Cycle in a linked list – Trival Approaches

Posted by tekpool on September 26, 2006

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.

I will use the following code in all (single) linked list programs:


struct LNode {

    int data; 
    LNode* next; 
    LNode() { 
        next=NULL; 
    }

};

class LinkedList {

    LNode* head;

}

For the sake of simplicity, I have put only an int field ‘data’ in the LNode struct. The LinkedList class currently only has a head pointer. I will add functions to it as we go along.

There are several solutions to this problem. I will discuss all of these in the following few posts. Here’s a couple of them

Sol 1: Trivial Striaghtforward approach – Worst

I am not going to write code for this one, since this is the most trival approach. And this is not a solution that you want to give when you go for an interview. Basically, for this question you are given the head pointer to the linked list and nothing else. The most trivial solution invovles starting from the head and storing all the pointers in a data structure (array, dynaminc array, linked list or a hash table). Then, as you traverse the list, compare with the already visited pointers to see if you have a match. A match indicates a cycle.

This is an O(n) space and O(n^2) time solution.

Sol 2: Trivial Striaghtforward approach – Visited Field

You can use a similar approach but more efficient if you can modify the linked list data structure. Add a boolean field to the data structure indicating whether or not this field has been visited. Set the visited field to false initially. Then, as you traverse from the head, check if the node has been visited. If not set the field to true. A visited node indicates a cycle.
This is a O(n) time solution, but although it looks constant space, it is actally O(n) space (extra field for each node) when you compare it to other algorithms out there

Posted in Algorithms, Data Structures, Linked List | 3 Comments »

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers