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;

}