CIS Planet

Alsalam alikom wa ra7mat Allah wa barakatoh (Peace upon you)

Have you ever got the feeling that you are sitting inside a hedge… in the sense that you are surrounded by noon-sun light but you don’t know the directions… and despite the fact that you are a few inches away from both sides, you are afraid to go either ways because you don’t know which side leads to the sharp edge and which is the safe ground…

What would you do… either wait the sun to set or take your best bet…

I don’t think there is a right answer, if there is one it would be “it depends”…

At least for me, I still can’t figure out what does it depend on! and I’m afraid to death that I won’t know till sunset! …

If I can ask you for one thing, that will be your prayers…

Alsalam alikom wa ra7mat Allah wa barakatoh

by http://haythamalaa.blogspot.com

The Microsoft Web Platform Installer 2.0 (Web PI) is a free tool that makes it simple to download, install and keep up-to-date with the latest components of the Microsoft Web Platform, including Internet Information Services (IIS), SQL Server Express, .NET Framework and Visual Web Developer. In addition, install popular open source ASP.NET and PHP web apps with the Web PI.

Here is the code snippet if you want to spread the word :)

<a href="http://go.microsoft.com/fwlink/?LinkId=146503" title="Get the Microsoft Web Platform">
<img src="http://www.microsoft.com/web/media/badge/get_microsoft_web_platform.png" alt="Get the Microsoft Web Platform" border="0" />
</a>

by http://haythamalaa.blogspot.com

Motivation

A singly linked list is a common data structure familiar to all computer scientists. A singly linked list is made of nodes where each node has a pointer to the next node (or NULL to end the list). A singly linked list is often used as a stack (or last-in-first-out queue (LIFO)) because adding a new fist element, removing the existing first element, and examining the first element are very fast O(1) operations.

When working with singly linked lists, you are typically given a link to the first node. Common operations on a singly linked list are iterating through all the nodes, adding to the list, or deleting from the list. Algorithms for these operations generally require a well formed linked list. That is, a linked list without loops or cycles in it.

If a linked list has a cycle:

• The malformed linked list has no end (no node ever has a NULL next_node pointer)
• The malformed linked list contains two links to some node
• Iterating through the malformed linked list will yield all nodes in the loop multiple times

A malformed linked list with a loop causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list is malformed before trying iteration. This article is a discussion of various algorithms to detect a loop in a singly linked list.

Data Structure

struct Node

{

private:

Node *_next, *_prev;

bool _seen; // Only needed in one solution.

public:

bool getSeen() // Only needed in one solution.

{

return _seen;

}

void setSeen(bool seen) // Only needed in one solution.

{

_seen = seen;

}

Node* getNext()

{

return _next;

}

void setNext(Node* next)

{

_next = next;

}

Node* getPrev()

{

return _prev;

}

void setPrev(Node* prev)

{

_prev = prev;

}

};

Incorrect "Solutions"

Traverse the List until the End

Just look at the entire list to see if it has an end. When it ends, return.

// Incorrect 'solution'

bool hasLoop(Node* startNode)

{

Node* currentNode = startNode;

while (currentNode = currentNode->getNext());

return false;

}

The problem with this solution is that if the linked list does have a loop, the program will never terminate. There is no way for this algorithm to return true when the linked list does have a loop.

Mark Each Node

Traverse the list and mark each node as having been seen. If you come to a node that has already been marked, then you know that the list has a loop.

// Incorrect 'solution'

bool hasLoop(Node* startNode)

{

Node* currentNode = startNode;

do {

if (currentNode->getSeen())

return true;

currentNode->setSeen(true);

} while (currentNode = currentNode->getNext());

return false;

}

The problem with this solution is ensuring that _seen is marked as false for all the nodes before you start. If the linked list has a loop, it isn't possible to iterate over each node to set _seen to false as an initial value for each node. It might be possible to overcome some of this by using an int rather than a bool and using a random integer as your marker. In that case there is a good chance that no node will have your initial value, but a small chance that one would and your algorithm would fail.

Even if you are able to solve the initial value problem, each node in a linked list may not have a field to use for this purpose. Requiring such a field in each node would mean that this is not a generic solution. As we will see later, this field is not needed for a perfectly correct and efficient solution anyway.

Detect Only Full Loops

When asked to come up with a solution, a common pitfall is not detecting all loops, but just a loop where the last node links to the first. A loop could still occur (and not be detected) if the last element linked to (for example) the second element.

// Incorrect 'solution'

bool hasLoop(Node* startNode)

{

Node* currentNode = startNode;

while (currentNode = currentNode->getNext())

if (currentNode == startNode)

return true;

return false;

Inefficient Solutions

Keep a Hash-Set of All Nodes Seen So Far

[O(n) Time Complexity]

[O(n) Space Complexity]

Keeping a set of all the nodes that have been seen so far and testing to see if the next node is in that set would be a perfectly correct solution. It would run fast as well. However it would use enough extra space to make a copy of the linked list. Allocating such much memory is prohibitively expensive for large lists.

// Inefficient solution

bool hasLoop(Node* startNode)

{

map bool > nodesSeen;

Node* currentNode = startNode;

do {

if (nodesSeen.find(currentNode) != nodesSeen.end()) // Node Found

return true;

nodesSeen.insert(pairbool>(currentNode, true));

} while (currentNode = currentNode->getNext());

return false;

Use a Doubly-Linked List

[O(n) Time Complexity]

Doubly linked lists make it easy to tell if there is a loop. If you encounter any node that doesn't link to the last node you visited, you know that there are two nodes linking to that node. Because the back links could be initially messed up in some other way, this algorithm is only correct if you can trust the back links. Otherwise it is just a malformed doubly linked list finder. The singly linked list can even be converted into a doubly linked list with little additional work. Again this will require that we change the structure of the Node to accommodate a second link (something that may not be possible in all cases). Usually a singly linked list is used because the amount of space to allocate for each node is at a premium.

// Inefficient solution

bool hasLoop(Node* startNode)

{

Node* currentNode = startNode;

Node* previousNode = NULL;

do {

if (previousNode && currentNode->getPrev() && previousNode != currentNode->getPrev())

return true;

if (!currentNode->getPrev())

currentNode->setPrev(previousNode);

previousNode = currentNode;

} while (currentNode = currentNode->getNext());

return false;

}

Check the Entire List So Far

[O(n^2) Time Complexity]

For each node, assume that the portion of the list examined so for has no loops and check to see if the next node creates a loop by iterating again over the entire list up to that point.

// Inefficient solution

bool hasLoop(Node* startNode){

Node* currentNode = startNode->getNext();

int i = 0;

do {

Node* checkNode = startNode;

int j = 0;

do {

if (checkNode == currentNode)

return true;

j++;

} while ((i getNext()));

i++;

} while (currentNode = currentNode->getNext());

return false;

}

Reverse the list

O(n) time complexity

If you reverse the list, and remember the initial node, you will know that there is a cycle if you get back to the first node. While efficient, this solution changes the list. Reversing the list twice would put the list back in its initial state; however this solution is not appropriate for multi-threaded applications. In some cases there may not be a way to modify nodes. Since changing the nodes is not needed to get the answer, this solution is not recommended.

// Solution modifies the list

bool hasLoop(Node* startNode)

{

Node *previousNode = NULL, *currentNode = startNode, *nextNode;

if (!currentNode->getNext())

return false;

while (currentNode)

{

nextNode = currentNode->getNext();

currentNode->setNext(previousNode);

previousNode = currentNode;

currentNode = nextNode;

}

return (previousNode == startNode);

}

Credit for this solution goes to Piyush Srivastava.

Use Memory Allocation Information

O(n) time complexity in the amount of memory on the computer

Some programming languages allow you to see meta-information about each node: the memory address at which it is allocated, for example. Because each node has a unique numeric address, it is possible to use this information to detect cycles. For this algorithm, keep track of the minimum memory address seen, the maximum memory address seen, and the number of nodes seen. If more nodes have been seen than can fit in the address space then some node must have been seen twice and there is a cycle.

// Depends on the size of the available computer memory rather than the size of the list.

bool hasLoop(Node* startNode)

{

Node *currentNode = startNode, *minAddress = currentNode, *maxAddress = currentNode;

int nodesSeen = 0;

while(currentNode = currentNode->getNext()){

nodesSeen++;

if (currentNode

minAddress = currentNode;

if (currentNode > maxAddress)

maxAddress = currentNode;

if (maxAddress - minAddress > nodesSeen)

return true;

}

return false;

}

This algorithm relies on being able to see memory address information. This is not possible to implement in some programming languages such as Java that do not make this information available. It is likely that the entire list will be allocated close together in memory. In such a case the implementation will run close to the running time of the length of the list. However, if the nodes in the list are allocated over a large memory space, the runtime of this algorithm could be much greater than some of the best solutions.

Best Solutions

Catch Larger and Larger Loops

[O(n) Time Complexity]

Always store some node to check. Occasionally reset this node to avoid the "Detect Only Full Loops" problem. When resetting it, double the amount of time before resetting it again.

// Good solution

bool hasLoop(Node* startNode)

{

Node *currentNode = startNode, *checkNode = NULL;

int since = 0, sinceScale = 2;

do {

if (checkNode == currentNode)

return true;

if (since >= sinceScale)

{

checkNode = currentNode;

since = 0;

sinceScale = sinceScale * 2;

}

since++;

} while (currentNode = currentNode->getNext());

return false;

}

This solution is O(n) because sinceScale grows linearly with the number of calls to getNext(). Once sinceScale is greater than the size of the loop, another n calls to getNext() may be required to detect the loop. This solution requires up to 3 traversals of the list.

This solution was devised by Stephen Ostermiller and proven O(n) by Daniel Martin.

Catch Loops in Two Passes

[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

bool hasLoop(Node* startNode)

{

Node *slowNode = startNode, *fastNode1 = startNode, *fastNode2 = startNode;

while (slowNode && (fastNode1 = fastNode2->getNext()) && (fastNode2 = fastNode1->getNext()))

{

if (slowNode == fastNode1 || slowNode == fastNode2)

return true;

slowNode = slowNode->getNext();

}

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".

Adopted from this page with recoding in C++.

This is the pdf version of this article.

Check out this URL: http://weblogs.asp.net/scottgu/archive/2009/03/10/free-asp-net-mvc-ebook-tutorial.aspx
Its a free ASP.NET MVC book by Scott Gu :)

"I wrote the first chapter of the book - which is a 185 page end-to-end tutorial that walks-through building a small, but complete, ASP.NET MVC application from scratch.  The agreement I made with Wrox was that I'd write it for free in return for them also making it available as a free PDF download."... Scott Gu

Enjoy ;)

There’s a “category” of questions that is commonly asked in large companies’ interviews that tests your thorough understanding of a certain programming language. I’ll send you an episode each time I remember one of them…

Represent x ? y : z as function int ternary(int x, int y, int z); using only ~, !, ^, &, +, |, << and >>. You’re not allowed to use -, * or if-else.

Solution 1:

int ternary(int x, int y, int z)

{

int ret[2] = {y, z};

return ret[!x];

}

The only comment here is that if x is 0, !x is 1… and if x is NOT 0, which means true in C++ as you probably know; !x is 0 – which is exactly what we want to index the array properly.

Solution 2:

int ternary(int x, int y, int z)

{

int t;

(!x && (t = z)) || (x && (t = y));

return t;

}

This one is actually important. Remember that the expression t = z (or t = y) evaluates to z (or y), and in the same time loads in t the correct value. That’s why we can depend on t in the end.

Thanks to F.M.A.R. who sent me this problem...

This is the pdf version of this article.