Technical Interview Questions

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

Archive for the ‘Data Structures’ Category

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.

Advertisements

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 »

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 | 21 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 | 10 Comments »

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 »