Adobe Question: Implement Binary Search using one comparison per iteration.

Solution: 

// Search value in array a of length size
int binarySearch( int* a, int value, int low, int high, int size) 
{
    while (low < high)
    {
        int mid = low + ((high - low) / 2); // Avoid overflow (low + high)
           if (a[mid] < value)
               low = mid + 1;
           else
                //can't be high = mid-1: as a[mid] >= value,
                //so high can't be < mid as a[mid] can be = value
                high = mid;
    }
       // high == low
       if ((low < size) && (a[low] = = value))
           return low; // found
       else
           return -1; // not found
}

Microsoft Question: Find the nearest sibling of a given node in a tree. Nodes on same level are siblings of each other

Solution:

Step 1: Do a preorder traversal of a tree and add sequence number corresponding to each node.

Step 2:  Now do a level order traversal of a tree and if a key appears in a level take the node with minimum difference in the sequence no with respect to the key, that will be the nearest sibling of the key.

Microsoft Question: Reverse words in a sentence.

Solution:
Reverse whole string and then reverse words in the reversed string.

void reverse(char* str, int start, int end)
{
    for(int i=start, j= end; i<j; ++i,--j)
    {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

int wordReverse(char *str)
{
    int len = strlen(str);
    reverse(str,0,len-1);
    for(int i=0,j=0;;)
    {
        while(str[j] != '\0' && str[j++] != ' ');
        if(str[j] == '\0')
        {
            reverse(str, i, j-1);
            break;
        }
        reverse(str,i,j-2);
        i=j;
    }
}

Mirosoft Question: Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the number is divisible by 3 or not.

Solution:

int rem = 0;

while(incomingNextBit)

{

   bool nextBit = getNextBit();

   if(nextBit == 0)

        rem = rem * 2;

   else

        rem = rem *2 + 1;

   rem = rem % 3;

}

At any time when you want to check wether number is divisble by 3 check rem %3.

This solution does not store the value of actual number.

Microsoft Question: There exists 2D char array, We need to find out whether a given string("microsoft") exists in the given matrix. the string can be vertical or horizontal..but NOT diagonal

I think it can be achieved with straight forward recursive programming. Following is my solution --

        public bool Exist(char[][] board, string word)

        {

            for (int i = 0; i < board.Length; ++i)

            {

                for (int j = 0; j < board[0].Length; ++j)

                {

                    if (board[i][j] == word[0])

                    {

                        if (this.Search(board, i, j, word, 0))

                        {

                            return true;

                        }

                    }

                }

            }

            return false;

        }

        private bool Search(char[][] board, int i, int j, string word, int currIndex)

        {

            if (currIndex == word.Length)

            {

                return true;

            }

            if (!this.Check(board, i, j, word[currIndex]))

            {

                return false;

            }

            

            char temp = board[i][j];

            board[i][j] = '#';

            bool result = this.Search(board, i - 1, j, word, currIndex + 1) ||

                this.Search(board, i + 1, j, word, currIndex + 1) ||

                this.Search(board, i, j - 1, word, currIndex + 1) ||

                this.Search(board, i, j + 1, word, currIndex + 1);

            board[i][j] = temp;

            return result;

        }

        private bool Check(char[][] board, int i, int j, char ch)

        {

            if (i >= 0 && i < board.Length && j >= 0 && j < board[0].Length && board[i][j] == ch)

                return true;

            return false;

        }

Microsoft Question: Merge Two linked list without creating any new node

My Solution is in C++ and is as follows --


void list::merge(list& l1)
{
    if(this == &l1)       // same list
        return;
    node *t1 = head;
    node *t2 = l1.head;
    node *temp1 = NULL, *temp2 = NULL;
    if(t1->data > t2->data)
    {
        temp2 = t2->next;
        t2->next = t1;
        head = t2;
        t2 = temp2;
    }
    else
        t1 = t1->next;
    node* prev = head; // prev is must as we need to have previous pointer to insert node at a given position
    while(t1&&t2)
    {
        if(t1->data <= t2->data)
            t1=t1->next;
        else
        {
            temp1 = prev->next;
            temp2 = t2->next;
            prev->next = t2;
            t2->next = temp1;
            t2 = temp2;
        }
        prev = prev->next;
    }

    if(!t1)
        prev->next=t2;
}

Linked List

Well the first data structure that we studied is Linked List and it provides a way to implement various Advance Data Structures. It can be defined in the following way --

                    " A Linked List is a Data Structure that consists of a sequence of Data Records such that in each record there is a field that contains a reference or link to the next record in the sequence."

Above is the Singly Linked List in which each node has data and a link to the next node in the List. Head node is the start of the List. Next of the last node in the List is NULL.

About The Blog

The Blog was started as a way to record some of my thoughts on Data Structure. It has evolved to include occasional guest writers, tutorials and some of my experiences of the interviews in different companies. When I started the blog, I was in my first real computer job as an Intern in Guruji.com.Since then I have finished my masters degree and am currently working as a Developer in Symantec.

The site is divided into three main sections --

•  Basic Data Structure and Algorithms
•  Advance Data Structure and Algorithms
•  Interview questions 

Occasionally, I write about conferences or papers I have presented or attended, sometimes with the slides or links to the paper.