Technical Interview Questions

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

Archive for November, 2006

Singleton Pattern: Part 3 Double Checked Locking

Posted by tekpool on November 27, 2006

Singleton Pattern: Part 3 Double Checked Locking

In the last post on Singleton Patterns, We looked into a thread safe mechanism to create singleton objects. The concept works well enough for most systems. However, when this becomes a hot section (heavily accessed) in your code, we will begin to hit performance problems. Here’s why: Lets say we have a high performant system, with 50-100 threads working around like magic, sharing tasks and running as fast as possible. Lets say that all the threads hit this hot section very often. This will result in the hot section being a real bottle neck, synchronizing and slowing down all the threads. Every thread enters this critical section and blocks every other thread from using this section. But is this really required? The ‘clever’ double locking system ‘tries’ to fix this problem.

Instead of locking down the critical section and blocking all the threads, this technique gives a chance for the threads to asynchronously check, whether or not it needs to enter this section in the first place. If it does (when instance != null), it then locks the section and proceeds in a normal thread safe manner where it does the second check. So the name, Double Checked Locking.

  class Singleton
  {
    private:
    static Singleton instance;

    protected Singleton()
    {
    }

    public static Singleton CreateInstance()
    {

      if(instance == null) //first check
      {
          // Use a mutex locking mechanism
          //  that suits your system
          LockCriticalSection();
          if (instance == null) //second check
          {
            instance = new Singleton();
          }
          UnLockCriticalSection();
       }
       return instance;
   }
}

Note: If you are using Java to implement this, beware that there are issues in Java’s memory model that prevent this technique from working correctly. This issue is however, fixed. So make sure you have the latest JDK if you plan to use this in your code. In a later post, I will go over the bug in JDK, more specifically in Java’s memory model that causes this problem.

Advertisements

Posted in Uncategorized | 2 Comments »

Binary Tree Searching: Improving Search Performance with Sentinels

Posted by tekpool on November 16, 2006

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )
{
    Node *current = this->root;

    while ( current != NULL )
    {
        if (current->data < data)
        {
            current = current->left;
        }
        else if (current->data > data)
        {
            current = current->right;
        }
        else if ( current->data == data )
        {
            return true;
        }
    }

  return false;
}

You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that’s 2500 checks.

Let’s see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;

This is how the search will look like
 
static Node* Leaf;

bool BinaryTree::Search (int data )
{
    Node *current = this->root;

    Leaf->data = data;

    while ( current->data != lead->data )
    {
        if (current->data < data)
        {
            current = current->left;
        }
        else
        {
            current = current->right;
        }
    }

    return (current != Leaf);
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.

This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.

Posted in Algorithms, Binary Trees, C++, Data Structures, General, Microsoft | 14 Comments »

Binary Tree Traversal: Breadth First aka Width First aka Level Order

Posted by tekpool on November 4, 2006

Binary Tree Traversal: Breadth First aka Width First aka Level Order

This is the lesser know of the different kinds of binary tree traversals. Most beginner books and articles only cover the depth first searches. Breadth first traversals are an extremely important tool when working with Binary Trees. The idea is pretty nifty. Basically you work with a Queue, and push the root node into the Queue. Then do the following until you have visited all nodes in the tree.

Visit and Dequeue each element (node) in the queue, and as you visit the node, enqueue it’s left and right child (if present). Continue this until there are no more nodes in the queue. At this point you have finished a breadth order traversal of the binary tree. Let’s work this out with an example.

BinaryTree                             

Here’s a small perfectly balanced tree that I going to be working with. The idea of doing a breadth first traversal is visit the nodes in the following order 1,2,3,4,5,6,7. Initially, you start of with an empty queue and enqueue the root node into the queue. I will display the contents of the queue as we move along.

                           ------------------------------------------- 
                           |  1 
                           -------------------------------------------- 

Visit each element int the queue, enqueue its left and right nodes and dequeue itself. Once the elements are dequeued, I will put them to the left of the queue.

Visit Node 1, enqueue 2 and 3 and dequeue 1

                              ------------------------------------------- 
1                             |  2, 3 
                              --------------------------------------------

Visit Node 2, enqueue 4 and 5 and dequeue 2

                             ------------------------------------------- 
1, 2                         |  3, 4, 5 
                             --------------------------------------------

Visit Node 3, enqueue 6 and 7 and dequeue 3

                            ------------------------------------------- 
1, 2, 3                     |  4, 5, 6, 7 
                            --------------------------------------------

Visit Node 4, dequeue 4 Nothing to enqueue since 4 has no child nodes

                            ------------------------------------------- 
1, 2, 3, 4                 |  5, 6, 7 
                            --------------------------------------------

Visit Node 5, dequeue 5, Nothing to enqueue since 5 has no child nodes

                          ------------------------------------------- 
1, 2, 3, 4, 5             | 6, 7 
                          --------------------------------------------

Visit Node 6, dequeue 6, Nothing to enqueue since 6 has no child nodes

                        ------------------------------------------- 
1, 2, 3, 4, 5, 6        |  7 
                        --------------------------------------------

Visit Node 7, dequeue 7, Nothing to enqueue since 6 has no child nodes

                         ------------------------------------------- 
1, 2, 3, 4, 5, 6, 7     | 
                         --------------------------------------------

We have just finished a breadth order traversal of a binary tree

Here’s a pseudo-code snippet that of the solution.

 
BreadthOrderTraversal(BinaryTree binaryTree) 
{ 
        Queue queue; 
        queue.Enqueue(binaryTree.Root); 
        while(Queue.Size > 0) 
        { 
                Node n = GetFirstNodeInQueue(); 
                queue.Enqueue(n.LeftChild); //Enqueue if exists 
                queue.Enqueue(n.RightChild); //Enqueue if exists 
                queue.Dequeue(); //Visit 
         } 
} 

Posted in Algorithms, Binary Trees, C++, Data Structures, General, Microsoft, Progamming Languages | 11 Comments »