Microsoft Question: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of |x – y|, |y – z| or |z – x|. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible, among all triplets which triplet has minimum distance.

Take three pointers p1, p2 and p3 respectively to the arrays A[], B[] and C[].

1. Place all of  them at 0th index and minDistance = some very large number

2. Now, find the max and min of the elements pointed to by the pointers.

3. Calculate dist = max - min. if dist is less than minDistance then Store p1,p2 and p3 in index1, index2, index3 and  store dist in minDistance. Now, our job is to minimize this dist.
4. Its obvious that dist will be minimized only if we increment the pointer at the min element. Hence, increment the min pointer and repeat step 2.

Implementation of above logic is as follows --

int max(int i, int j, int k)
{
    return (i > j) ? ( i > k ? i : k) : (j > k ? j : k);
}

int min(int i, int j, int k, int& arr)
{
    int temp = (i < j) ? ( i < k ? i : k) : (j < k ? j : k);
    arr = (temp == i) ? 0 : (temp == j ? 1 : 2);
    return temp;
}

void FindTriplet(int *a, int *b, int *c, int lenA, int lenB, int lenC)
{
    int index[3] = { 0 };
    int minArr = 0;
    int minDistance = 32767;   // Large number
    int minIndex[3] = {0};
    while(index[0] < lenA && index[1] < lenB && index[2] < lenC)
    {
        int distance = max(a[index[0]], b[index[1]], c[index[2]]) -
                            min(a[index[0]], b[index[1]], c[index[2]], minArr);

        if(distance < minDistance)
        {
            for(int i =0; i<3; minIndex[i++] = index[i]);
            if(0 == (minDistance = distance) )
                break;
        }

        index[minArr]++ ;
    }

    cout<<"Minimum Distance :: "<<minDistance<<"\nAt indices\t"<<minIndex[0]<<'\t'
          <<minIndex[1]<<'\t'<<minIndex[2]<<'\n';
}

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;
}