Technical Interview Questions

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

Archive for the ‘Microsoft’ Category

const Correctness: Difference between Foo* const ptr, const Foo* ptr, const Foo* const ptr

Posted by tekpool on January 10, 2007

  • Foo* const ptr: ptr is a const pointer to a Foo Object. The Foo object can be changed using the pointer ptr, but you can’t change the pointer ptr itself.
  • const Foo* ptr: ptr points to a Foo object that is const. The Foo object can’t be changed via ptr.
  • const Foo* const ptr: ptr is a const pointer to a const Foo object. Neiher can the pointer ptr be changed, nor can you change the Foo object using ptr.

Reading the declaration right to left is a easy way to remember what they mean.

Posted in C++, General, Microsoft, Progamming Languages, Technical Interview Questions | 9 Comments »

Constructors: Copy Constructors, What, Why, How, When … (C++)

Posted by tekpool on December 22, 2006

As the name suggests, a copy constructor is called whenever an object is copied. This happens in the following cases:

  • When an object is create from another object during initialization (Class a = b)
  • When an object is created from another object as a parameter to a constructor (Class a(b))
  • When an object is passed by value as an argument to a function (function(Class a))
  • When an object is return from a function (Class a; … return a;)
  • When an exception is thrown using this object type (Class a; …. throw a;)

Whenever an object copying scenario like the ones above is encountered, the copy constructor is invoked. A copy constructor can be either user defined or compiler defined. If the user does not define a copy constructor, then the default compiler defined copy constructor will be invoked during object copy scenarios. The default copy constructor is a bit-by-bit (member wise) copy. But often you will encounter situations where this is not desirable since this is just a shallow copy and sometimes you do not want an exact copy or you may want to do some custom resource management. 

 
Class t1; 
Class t2=t1; // Copy Constructor is invoked 
Class t3; 
t3=t1; // Assignment Operator is invoked 

In the Code snippet above, the constructor is invoked twice, during the creation of objects t1 and t3. (Creation of t2 invokes the copy constructor). The destructor is invoked 3 times though. In cases like these, if the constructor allocates memory and the destructor frees it, you will see the t2’s destructor will try to delete already deleted memory, if t1 is destroyed before t2 or vice-versa. Meaning, you are hosed. To prevent this, a user defined copy constructor needs to be provided. which doesn’t do a simple bit-by-bit but rather assigns memory specifically for the object and does a deep copy if required.

To define a copy constructor for a class T, a constructor of the following format needs to be defined.

 
Class T 
{ 
… 
    T(const T& t) 
… 
} 

You need a reference because if it were T(T t), it would end in a infinite recursion. (Was that an oxymoron?). const because you are not changing the object in the constructor, you are just copying its contents

Some Rules of Thumb:

  • Don’t write a copy constructor if a bit-by-bit copy works for the class
  • If you defined your own copy constructor, it probably because you needed a deep copy or some special resource management, in which case, you will need to release these resources at the end, which means you probably need to define a destructor and  you may also want to think of overloading the assignment operator (beware of self-assignment)

Posted in C++, General, Microsoft, Progamming Languages | 22 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 | 13 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 | 10 Comments »

Singleton Pattern: Part 2 Thread-Safe implemenation

Posted by tekpool on October 27, 2006

Singleton Pattern: Part 2 Thread-Safe implemenation

We looked into a trivial implementation of the singleton pattern in the previous post. The implementation was both lazy and non-thread safe. It’s lazy, because the singleton instance is created only when it’s required. The implementation was also not thread safe. So, if several calls were made into this method from a multi-threaded program, you could end up creating multiple instances of the class, and also mess up seriously since the system expects to have only one instance.

The problem is at the place, where you check if the instance is null. This is how it could go all wrong. In a multithread environment, lets say 2 threads T1 and T2 are calling the CreateInstance() function. T1 executes the ‘if’ condition and then loses its time-slice, Meanwhile T2 gets its chance to execute code. At this point the singleton instance is not yet created. T2 then creates the object and returns the caller an instance of the newly created object. When T1 gets back another time-slice, it creates another object and returns that instance to its caller. Since it’s a static instance, T2 will lose it’s the state of the object it acquired and then hell breaks loose.

  class Singleton 
  { 
    private: 
    static Singleton instance; 

    protected Singleton() 
    { 
    } 

    public static Singleton CreateInstance() 
    { 

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

Posted in C++, Design Patterns, General, Microsoft, Progamming Languages | 208 Comments »

Singleton Pattern: Part 1 Trivial implemenation

Posted by tekpool on October 19, 2006

Singleton Pattern: Part 1 Trivial implemenation

The purpose of a singleton pattern is to ensure a unique instance of the class and to provide global access to this. It falls under the Creational patterns category.

The class implementing the singleton pattern will have to do the following items:

  1. Provide an Instance Creation Method to the user.
  2. Maintain the unique instance throughout the life of the program(s) in which this class is created.

To maintain the unique instance, the class will have to remove the normal object creation procedure away from the user. The normal object creation is through the constructor. Taking this away from the user would mean, making the constructor as private or protected. With the absence of a public constructor, the class now can take total control on how its instances are created. The only way to do this, is to provide a static method (say CreateInstance). Why static? Because, the user can actually call this method without creating an object (which is obviously out of the user’s control).

The logic of the CreateInstance method is pretty straightforward. Check, if any instance has already been created, if yes, return the instance, else create and store the instance and return it. It is obvious here again, storing the instance has to be done in a private static variable, static because, you are doing this in a static method, private because, you need to do the maintenance of the singleton instance creation.

Here’s the code sample to demonstrate this. I am going to promote Test Driven Development in my examples.

The TestApp::TestSingleton() method is the test code that I wrote even before writing the actual Singleton class. I will discuss Test Driven Development in detail in another series.

  class TestApp 
  { 
    public: 
    static void TestSingleton() 
    { 

      Singleton s1 = Singleton.Instance(); 
      Singleton s2 = Singleton.Instance(); 

      if (s1 == s2) 
      { 
        printf("PASSED:  
        Objects are of the same instance"); 
      } 
      else 
      { 
        printf("FAILED:  
       Objects do not point to the same instance"); 
      } 

    } 
  } 

// WARNING: DO NOT USE THIS CODE ANYWHERE. 
// THIS IS A VERY TRIVIAL IMPLEMENATION. WE WILL 
// DISCUSS THE ISSUES WITH THIS IN FUTURE POSTS. 

  class Singleton 
  { 
    private: 
    static Singleton instance; 

    protected Singleton() 
    { 
    } 

    public static Singleton CreateInstance() 
    { 

      if (instance == null) 
      { 
        instance = new Singleton(); 
      } 

      return instance; 
    } 
  } 
}

Posted in C++, Design Patterns, General, Microsoft, Progamming Languages | 1 Comment »

String Pattern Matching: Write a function that checks for a given pattern at the end of a given string

Posted by tekpool on October 15, 2006

String Pattern Matching: Write a function that checks for a given pattern at the end of a given string

In other words, Write a function, a variant of strstr that takes in 2 strings str1 and str2 and returns true if str2 occurs at the end of the string str1, and false otherwise.

bool str_str_end(char * str1, char * str2) 
{ 
        // Store the base pointers of both strings 
        char* beginStr1 = str1; 
        char* beingStr2 = str2; 

       // Move to the end of the strings 
        while(*str1++); 

        while(*str2++); 

        for(; *str1 == *str2; str1--, Str2--) 
       { 
       If( str2 == beginStr2 
                          || str1 == beingStr1) 
            { 
            break; 
            } 
       } 
       return    If(*str1 == *str2 
                    && str2 == beginStr2 
                    && *str1 != 0); 
}

Save the base addresses of the strings and then traverse to the end of the stings. To check if the string str2 occurs at the end of the string str1, start comparing characters from the end of the strings and move backwards. The function returns true when

  1. All the characters in str1 match all the characters in str2 from the end.
  2. The pointer str2 reaches back at the beginning of the string, which means there is nothing more to be compared
  3. The strings are not empty.

The above conditions are required so that the loops do not run in an infinite loop.

Posted in Algorithms, C++, General, Microsoft, Pattern Matching, Progamming Languages, Strings | 2 Comments »

Rectangle Intersection – Find the Intersecting Rectangle

Posted by tekpool on October 12, 2006

Q: Rectangle Intersection – Find the Intersecting Rectangle

In the last post, we looked into methods to determine whether or not two given rectangles intersect each other. Lets go one step ahead this time and find the intersecting rectangle.

As in the previous post, I am basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.


bool Intersect(RECT* r3, const RECT * r1, const RECT * r2) 
{ 
    bool fIntersect =  ( r2->left right 
                                && r2->right > r1->left 
                                && r2->top bottom 
                                && r2->bottom > r1->top 
                                ); 

    if(fIntersect) 
    { 
        SetRect(r3, 
                     max(r1->left, r2->left), 
                     max(r1->top, r2->top), 
                     min( r1->right, r2->right), 
                     min(r1->bottom, r2->bottom)); 
    } 
    else 
    { 
        SetRect(r3, 0, 0, 0, 0); 
    } 
    return fIntersect; 
}

First, determine whether or not the two Rectangles intersect each other, Then use the SetRect method (which basically creates a RECT with the given points) and create the intersecting Rectangle

SetRect(r3, 
    max(r1->left, r2->left), 
    max(r1->top, r2->top), 
    min( r1->right, r2->right), 
    min(r1->bottom, r2->bottom));

Since the algorithm is pretty straightforward, I am not going to include more detailed analysis in this post, unless I get enough request comments or email )

NOTE: For all invalid rectangles passed to the function, the return value is always [0,0,0,0]. You can also choose to return error codes after checking for validity.

Posted in Algorithms, C++, General, Graphics, Microsoft, Progamming Languages | 12 Comments »

Rectangle Intersection – Determine if two given rectangles intersect each other or not

Posted by tekpool on October 11, 2006

Q: Rectangle Intersection: Determine if two given rectangles intersect each other or not

Definitions:

Intersect: Two Rectangles intersect each other if the share a common area.

Assumptions:

  • Both the rectangles are aligned with the x and y axes.
  • Rectangles just touching each other are considered as non-intersecting.

First let’s create a data structure for use in our problem. Rectangle Intersection algorithms are usually used in graphics problems. Depending on the precision needed to represent the co-ordinates, you may choose the required data type. In this case, I am going to use a LONG.

I am also basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.

struct 
{ 
    LONG    left; 
    LONG    top; 
    LONG    right; 
    LONG    bottom; 
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2) 
{ 
    return ! ( r2->left > r1->right 
        || r2->right left 
        || r2->top > r1->bottom 
        || r2->bottom top 
        ); 
}

The above algorithm finds the conditions at which the rectangles do not intersect and then negates the values to get the result. There is a straight forward way of doing the same algorithm, but it requires far more conditions than the one above. Consider the diagram below


  S1   |         S2          |   S3 
       |                     | 
    TOP|LEFT                 | 
----------------------------------- 
       |                     | 
       |                     | 
       |                     | 
  S4   |         S5          |   S6 
       |                     | 
       |                     | 
----------------------------------- 
       |                RIGHT|BOTTOM 
       |                     | 
  S7   |         S8          |   S9

This is an illustration of one of the rectangles (R1). The top left corner of R2 can like in any of the 9 segments, S1 through S9. Based on each of these cases, and depending on the position of the other vertices, it can be determined whether the two rectangles R1 and R2 intersect each other. E.g. If R2’s top left corner is in S1, the bottom right corner needs to be in S5 or beyond (S5,S6,S8,S9) for the rectangles to intersect. Or if the top left corner of R2 is in S5, it is an automatic case of intersection. Clearly, in this case there are a lot of cases to consider and therefore and lot of conditions to check.

The conditions where the rectangles do not intersect, is where the bounds of one Rectangle is beyond the bounds of the other. The conditions are pretty straightforward as shown in the code above. Negating this value solves the original problem.

There is one more conditions (negation) that can be avoided by changing the inner condition. I will leave that as an exercise for the reader.

NOTE: For all invalid rectangles passed to the function, the return value is always false. You can also choose to return error codes after checking for validity.

Posted in Algorithms, C++, Data Structures, General, Graphics, Microsoft, Progamming Languages | 18 Comments »

Shuffling – Shuffle a deck of cards – Knuth Shuffle

Posted by tekpool on October 6, 2006

Q: Shuffling – Shuffle a deck of cards – Knuth Shuffle

Shuffling is a process where the order of elements in a data set is randomized to provide an element of chance. One of the most common applications of this is to shuffle a deck of cards.

Mathematically, the shuffling problem, is basically a problem of computing a random permutation of N objects, since shuffling a deck of cards is basically subjecting a deck of cards to a random permutation.

Card shuffling algorithms are used in computer games, casinos, etc. Before we delve into the algorithms, let’s look into what are really trying to solve here. These are the kind of things that an interviewer will be looking into apart from the algorithm itself. The choice of algorithm and data structure chosen for this, needs to be based on where, who and how this is going to be used.

As I just mentioned, this is something used in the gaming industry (Computers, Video Games, Casinos etc…). This purpose of this algorithm is to introduce an element of chance into the data set (deck of cards) and make it impossible for the user to find a pattern and predict the occurrence of un-dealt cards. The size of the data set is small (52 elements), and so the complexity of the algorithm is usually not of high concern. A O(n^2), v/s an O(n lg n) v/s an O(n) for example would be a few milliseconds. Of course, a real bad implementation with O(n^n) would certainly be of concern, although I guess it is going to be difficult to come up with a O(n^n) algorithm in the first place.

It is important to look at problems with this angle. Sometimes, it takes too much time and effort to come up with a faster algorithm, and it the end it could end up providing very less value. The keyword here cost/benefit ratio.

OK, so we’ve learnt that the complexity of the algorithm we choose is not of high priority. What else? Since this is something that will be used in a casino, we need to eliminate the element of predictability. We don’t want people to be able to predict what the next card in the deck might be, even with a low probability.

The problem itself involves randomization, and we are definitely going to deal with random numbers. Some random numbers, have bias on some of bits in a number, e,g rand() has a bias on the upper bits in a number. We want to be avoiding such generators.

There are few basic well known solutions to this problem, the first of this is an O(n lg n) algorithm. I won’t be writing code for this, but I will go over the algorithm. The solution involves simple assigning a random number to each card, and sorting them in order of their assigned number. There is a chance that two of the cards are assigned the same number. This check can be checked each time you assign a number, or even better this can be checked when you sort the cards and redo it all over again, or redo the same problem on the smaller set usually 2 cards, if you have got more than 2 cards, actually even 2 cards, then you’ve chosen a bad random number generator.

The more elegant and faster of the two algorithms is also known as the Knuth Shuffle, popularized by Donald Knuth, in his book , The Art of Computer Programming. The algorithm was originally published by R.A. Fisher and F. Yates [Statitiscal Tables (London 1938, Example 12], in ordinary language, and by R. Durstenfeld [CACM 7 (1964), 420] in computer language. Here’s the algorithm in ordinary language.

Let X1, X2…. XN (In this case N=52) be the set of N numbers to be shuffled.

  1. Set j to N
  2. Generate a random number R. (uniformly distributed between 0 and 1)
  3. Set k to (jR+1). k is now a random integer, between 1 and j.
  4. Exchange Xk and Xj
  5. Decrease j by 1.
  6. If j > 1, return to step 2.

void KnuthShuffle(int* pArr) 
{ 
    int rand; 
    for(int i=51;i>=0;i--) 
    { 
        rand=GenRand(0,i); 
        swap(pArr[i], pArr[rand]); 
    } 
}

GenRand(int min, int max) generates a random number between min and max.

For the mathematically oriented:

Traditional shuffling procedures turn out to be miserable inadequate. Reportedly, expert bridge players make use of this fact when deciding whether or not to finesse. At least seven “riffle shuffles” of a 52-card deck are needed to reach a distribution within 10% of uniform, and 14 random riffles are guaranteed to do so. [Aldous and Diaconis, AMM 93 (1986), 333-348] [Knuth, The Art of Computer Programming, Random Sampling and Shuffling]

Posted in Algorithms, C++, Data Structures, General, Microsoft, Progamming Languages | 9 Comments »

 
Follow

Get every new post delivered to your Inbox.

Join 27 other followers