Technical Interview Questions

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

Archive for September, 2006

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.

Advertisements

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 »

Bit Count: Parallel Counting – MIT HAKMEM

Posted by tekpool on September 25, 2006

Q: Find the number of set bits in a given integer

Sol: Parallel Counting: MIT HAKMEM Count

HAKMEM (Hacks Memo) is a legendary collection of neat mathematical and programming hacks contributed mostly by people at MIT and some elsewhere. This source is from the MIT AI LABS and this brilliant piece of code orginally in assembly was probably conceived in the late 70’s.

 int BitCount(unsigned int u)
 {
         unsigned int uCount;

         uCount = u
                  - ((u >> 1) & 033333333333)
                  - ((u >> 2) & 011111111111);
         return
           ((uCount + (uCount >> 3))
            & 030707070707) % 63;
 }

Lets take a look at the theory behind this idea.

Take a 32bit number n;
n = a31 * 231 + a30 * 230 +.....+ ak * 2k +....+ a1 * 2 + a0;

Here a0 through a31 are the values of bits (0 or 1) in a 32 bit number. Since the problem at hand is to count the number of set bits in the number, simply summing up these co-efficients would yeild the solution. (a0 + a1 +..+ a31 ).

How do we do this programmatically?

Take the original number n and store in the count variable.
count=n;

Shift the orignal number 1 bit to the right and subtract from the orignal.
count = n - (n >>1);

Now Shift the original number 2 bits to the right and subtract from count;
count = n - (n>>1) - (n>>2);

Keep doing this until you reach the end.
count = n - (n>>1) - (n>>2) - ... -( n>>31);

Let analyze and see what count holds now.
n = a31 * 231 + a30 * 230 +.....+ ak * 2k +....+ a1 * 2 + a0;
n >> 1 = a31 * 230 + a30 * 229 +.....+ ak * 2k-1 +....+ a1;
n >> 2 = a31 * 229 + a30 * 228 +.....+ ak* 2k-2 +....+ a2

;
..
n >> k = a31 * 2(31-k) + a30 * 2(30-k) +…..+ ak * 2k;

..
n>>31 = a31;

You can quickly see that: (Hint: 2k - 2k-1 = 2k-1; )
count = n - (n>>1) - (n>>2) - ... -( n>>31) =a31+ a30 +..+a0;
which is what we are looking for;

int BitCount(unsigned int u)
{
       unsigned int uCount=u;
       do
       {
             u=u>>1;
             uCount -= u;
       }
       while(u);
}

This certainaly is an interesting way to solve this problem. But how do you make this brilliant? Run this in constant time with constant memory!!.

int BitCount(unsigned int u)
{
         unsigned int uCount;

         uCount = u
                       - ((u >> 1) & 033333333333)
                       - ((u >> 2) & 011111111111);
         return
               ((uCount + (uCount >> 3))
               & 030707070707) % 63;
 }

For those of you who are still wondering whats going? Basically use the same idea, but instead of looping over the entire number, sum up the number in blocks of 3 (octal) and count them in parallel.

After this statement uCount = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
uCount has the sum of bits in each octal block spread out through itself.

So if you can a block of 3 bits

u = a222 + a12+ a0;
u>>1 = a2*2 + a1;
u>>2 = a2;

u - (u>>1) - (u>>2) is a2+a1+a0 which is the sum of bits in each block of 3 bits.

The nexe step is to grab all these and sum them up:

((uCount + (uCount >> 3)) will re-arrange them in blocks of 6 bits and sum them up in such a way the every other block of 3 has the sum of number of set bits in the original number plus the preceding block of 3. The only expection here is the first block of 3. The idea is not to spill over the bits to adjacent blocks while summing them up. How is that made possible. Well, the maximum number of set bits in a block of 3 is 3, in a block of 6 is 6. and 3 bits can represent upto 7. This way you make sure you dont spill the bits over. To mask out the junk while doing a uCount>>3. Do and AND with 030707070707. THe only expection is the first block as I just mentioned.

What does ((uCount + (uCount >> 3)) & 030707070707) hold now?
Its 2^0 * (2^6 - 1) * sum0 + 2^1 * (2^6 - 1) * sum1 + 2^2 * (2^6 - 1) * sum2 + 2^3 * (2^6 - 1) * sum3 + 2^4 * (2^6 - 1) * sum4 + 2^5 * (2^3 - 1) * sum5
where sum0 is the sum of number of set bits in every block of 6 bits starting from the ‘low’ position.
What we need is sum0 + sum1 + sum2 + sum3 + sum4 + sum5;
2^6-1

Posted in Algorithms, Bit Count, Bit Fiddling, C++, General, Progamming Languages | 9 Comments »

Bit Count: Unset Bit Iterator

Posted by tekpool on September 24, 2006

Q: Find the number of set bits in a given integerSol: Unset Bit (0’s) Iterator

This is similar to the Set Bit Iterator method, expect that all bits are toggled before iteration, and uCount is decremented whenever a set bit (originally unset) is encountered.

int BitCount (unsigned int u) 
{ 
        //number of bits in unsigned int 
        unsigned int uCount= 8 * sizeof(unsigned int); 

        // Toggle bits 
        u ~= (unsigned int) -1 ; 
        for(; u; u&=(u-1)) 
            uCount--; 

        return uCount ; 
}

Running time is proportional to the number set bits, Useful when there are less number of unset bits in the number

Posted in Algorithms, Bit Count, Bit Fiddling, C++, General, Progamming Languages | Leave a Comment »

Bit Count: Set Bit Iterator

Posted by tekpool on September 24, 2006

Q: Find the number of set bits in a given integer

Sol: Set Bit (1’s) Iterator

Here, the line u &= u-1 flips the highest set bit in each iteration, until there are no more set bits.

int BitCount (unsigned int u)
{
         unsigned int uCount=0 ;

         for(; u; u&=(u-1))
            uCount++;

         return uCount ;
}

Running time is proportional to the number set bits, Useful when there are less number of set bits in the number

Posted in Algorithms, Bit Count, Bit Fiddling, C++, General, Progamming Languages | 1 Comment »

Bit Count: Looping through the Bits

Posted by tekpool on September 22, 2006

Q: Find the number of set bits in a given integer

Sol: Looping through all the bits

In this approach, the number is looped through all its bits one by one using a right shift, and checking if the low bit is set, in every iteration by AND’ing with 0×1u

int BitCount(unsigned int u)
{
           unsigned int uCount = 0;
       for(; u; u>>=1)
            uCount += u & 0x1u;    

return uCount;

}

This algorithm will iterate through every bit, until there are not more set bits. Worst case performance occurs when the high bits is set.

Posted in Algorithms, Bit Count, Bit Fiddling, C++, General, Progamming Languages | 3 Comments »

Bit Count: Pre-Computing Bits

Posted by tekpool on September 21, 2006

Q: Find the number of set bits in a given integer?

Sol: Pre-Computing Bits

static unsigned int NumBits8Bit[256] ;

//Precompute this array of size 256, each element in the array denoting the number of bits in a char (0×00 to 0xff). Then separate divide the number of interest into 4 blocks of 8 bits each by masking the last 8 bits (ANDing it with 0xffU) and right shifting by 8 bits each time. Sum up the count and return


int BitCount (unsigned int u)
{

    return NumBits8Bit [u & 0xffU]
           +  NumBits8Bit [(u>> 8 ) & 0xffU]
           +  NumBits8Bit [(u>>16) & 0xffU]
           +  NumBits8Bit [(u>>24) & 0xffU] ;

}


The fastest ways to solve this problem is through look-up tables. But, like everything else, it comes with a cost. Here, you pay for memory.

You can write several variations to this algorithm, basically changing the amount of bits you want to pre-compute. But, remember that the more bits you pre-compute, the lesser the number of look-ups. In most common cases you can precompute 4,8,16 bits. Doing a 32-bit lookup will take up quite some memory.

Posted in Algorithms, Bit Count, Bit Fiddling, C++, General, Progamming Languages | 3 Comments »