Adobe Question: Implement doubly link list with only one address field

Instead of storing next and previous pointer, store xor of next and previous pointers. Implementation is given below -

struct Node
{
    int data;
    int xor;
    Node(int d=0, int x=0):data(d), xor(x){}
};

class DList
{
public:
    DList(Node* h=0, Node* t=0):head(h){}
    void insert(int val); //insert at last position
    void traverse();
private:
    Node* head;
};

void DList::insert(int val)
{
    if(!head)
    {
        head = new Node(val);
    }
    else
    {
        Node* prev = head, *temp = (Node*)(head->xor);
        while(temp)
        {
            Node* temp1 = temp;
            temp = (Node*)((int)prev ^ temp->xor);
            prev = temp1;
        }
        temp = new Node(val, (int)prev);
        prev->xor ^= (int)temp;
    }
}

void DList::traverse()
{
    if(!head)
        return;
    Node* prev = head, *temp = (Node*)(head->xor);
    while(temp)
    {
        cout<<prev->data<<'\t';
        Node* temp1 = temp;
        temp = (Node*)((int)prev ^ temp->xor);
        prev = temp1;
    }
    cout<<prev->data<<'\n';
}

* Limitation of this approach is, we can traverse list only from head or tail (if given).

Adobe Question: Print paths from root to all leaves in a Binary Tree

Solution:

Do a preorder traversal and insert elements in vector, While returning from node, remove it from vetcor.
if a leaf is found print all the elements in Vector.


//Public interface
void BSTree::printAllpath()
{
    cout<<"\nAll paths from root to leaves::";
    vect.clear();  // vect is private vector<Node*> of BSTree class
    printAllpath(root);
}


//Actual working, Private member of BSTree class
void BSTree::printAllpath(Node* node)
{
    if(node)
    {
        vect.push_back(node->data);
        if(!(node->left) && !(node->right))
        {
            cout<<'\n';
            for(int i=0; i<vect.size(); ++i)
                cout<<vect[i]<<'\t';
            vect.pop_back();
            return;
        }
        printAllpath(node->left);
        printAllpath(node->right);
        vect.pop_back();
    }
}

Google Question: Given an array, a fall is defined as arr[i] - arr[j] where i <= j. You need to find out the maximum fall in the array given.

int main()
{
    int arr[] = { 1, 7, 3, 2, 9, 10, 7, 4};
    int length = sizeof(arr) / sizeof(*arr), maxFall = 0;
    for(int i =1, elem = arr[0], fall = 0; i<length; ++i)
            ((elem < arr[i]) && (elem = arr[i],1)) || (((fall=elem-arr[i]) > maxFall)
            && (maxFall = fall));
    cout<<"MaxFall = "<<maxFall<<'\n';
    return 0;
}

MicroSoft Question: Given a sequence, find the subsequence with maximum sum.

int main()
{
    int arr[] = { 1, 3, -5, 7, 2 ,-4, 9, -3};
    int length = sizeof(arr) / sizeof(*arr);
    int tempSum = 0, maxSum = 0, tempStartIndex = 0, startIndex = 0, endIndex = 0;
  
    for(int i=0; i<length; ++i)
    {
        tempSum += arr[i];
        if(tempSum < 0)
        {
            tempStartIndex = i+1;
            tempSum = 0;
            continue;
        }

        if(tempSum > maxSum)
        {
            maxSum = tempSum;
            startIndex = tempStartIndex;
            endIndex = i;
        }

    }
    cout<<"Maximum Sum = "<<maxSum<<" Between indices "<<startIndex<<" "<<
   endIndex<<'\n';
    return 0;
}

Adobe Question: Generic Swap in C

void Swap(void* var1, void* var2, int size)
{
    void *temp = malloc(size);
    memcpy(temp,var1,size);
    memcpy(var1, var2, size);
    memcpy(var2, temp, size);
    free (temp);
}

DirectI Question: You are given a large string of characters and a small set of characters. You have to find smallest substring of String which contains all characters in the Set.

int main()
{
    char str[] = "Rajat Grover is a good boy";
    char set[] = "aio";
    int lenStr = strlen(str);
    int lenSet = strlen(set);

    int minDist = 32767; //Some very large value
    int maxInd = lenStr;
    int minInd =  -1;

    bool allFound = false;

    char *hashSet = new char[lenSet];
   
    for(int i=0; i<lenSet; hashSet[i++] = -1);

    for(i=0; i<lenStr; ++i)
    {
        int ind = -1;
        if(-1 != (ind = Index(set, str[i], lenSet)))
        {
            hashSet[ind] = i;

            if(!allFound)
            {
                allFound = true;
                for(int j=0; j<lenSet; ++j)
                {
                    if(hashSet[j] == -1)
                    {
                        allFound = false;
                        break;
                    }
                   
                }
                if(!allFound)
                    continue;
            }

            int tempMax, tempMin;
            int tempDistance = (tempMax = Max(hashSet,lenSet)) - (tempMin =
            Min(hashSet,lenSet));

            if(minDist > ++tempDistance)
            {
                maxInd = tempMax;
                minInd = tempMin;
                if((minDist = tempDistance) == lenSet)
                         break;
            }
               
        }
    }
    cout<<"Minimum Interval: "<<minDist<<". Between index "<<minInd
    <<" and "<<maxInd<<'\n';
    return 0;

}

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

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.