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