Reverse a Linked List using one pointer.

void reverse(node* temp)
{
     if(temp->next)
     {
        reverse(temp->next);
        temp->next->next = temp;
        temp->next = NULL;
     }
    else
            head = temp;
}

Note: It is not actually one pointer as we are using recursion.

Given pointers to two Single Linked List find out if they joined in Y shape and also at which node they are joined.

Solution:

To check whether they joined in Y shape or not --

if ( End(List1) = = End(List2) )
    // Merged

To find the node --

count1 = Size ( List1 ) ;
count2 = Size ( List2 ) ;

longList = List1 ;
smallList = List2 ;
count2 > count1 && ( swap( longList, smallList ) ) ;

for ( int i = 0; i < abs(count1 - count2); longList = longList -> next, ++i ) ;

while(longList !- null && longList != smallList )
{
      longList  =  longList -> next ;
      smallList = smallList -> next ;
}

return longList ;

In C# -

        public LinkedListNode GetIntersectionNode(LinkedList list2)

        {

            int count1 = this.Count();

            int count2 = list2.Count();

            LinkedListNode longListNode, shortListNode;

            if (count1 >= count2)

            {

                longListNode = this.Head;

                shortListNode = list2.Head;

            }

            else

            {

                longListNode = list2.Head;

                shortListNode = this.Head;

            }

            for (int i = 0; i < Math.Abs(count1 - count2); longListNode = longListNode.Next, ++i);

            while(longListNode != null && longListNode != shortListNode)

            {

                longListNode = longListNode.Next;

                shortListNode = shortListNode.Next;

            }

            return longListNode;

        }

Remove duplicate characters from a string in O(n).

Solution:
void remove(char *str )
{
    bool hash[256] = {0} ;
    for(int i =0, j=0 ; str[i] != '\0'; ++i)
          hash[str[i]] || (hash[str[i]] = true, str[j++] = str[i]);
    str[j] = '\0';
}

Delete a node from singly linked list when only pointer to node to be deleted is given in O(1).

Solution:
Say node to be deleted is toDelete.
copy ( toDelete->next->element, toDelete->element);
remove( toDelete->next );

* We are not really deleting the node but we are achieving what we want to do ;)
* Problem in this approach when toDelete is the last node, Solution is circular linked list or a temporary tail node

Design a Data Structure which supports push, pop and findMin operation in O(1).

Solution:

Extra Space:

Use two stack say stack1 and stack2. stack2 is used to keep track of Minimum number in the list at each step.

push( n ):    stack1.push(n);
                 stack2.push( Min( n, stack2.top( ) ) );

pop( ):        stack1.pop( );
                 stack2.pop( );

findMin( ):  stack2.top( );

Adobe Question: Multiply two numbers using bitwise operators

Solution:

A =            101
B =              10
                  -------
                    000
                  101x             x here denotes a left shift by 1 bit.
                  -------
Result =      1010

The magic is to check for the last bit of B. If the last bit is 1, then add ‘A’ to result else do nothing. And after every check right shift ‘B’ by 1 bit and left shift ‘A’ by 1 bit.

To add two numbers using bitwise, you need to implement the full adder where you calculate sum and carry as below:
Sum = A xor B (A ^ B)
Carry = A and B (A & B)


Source:
int bitwiseMultiply(int a, int b)
{
int result = 0;
while ( b != 0)
{
if ( b & 1)
{
result = sum( a, result);
}
a = a << 1; b = b >> 1;
}
return result;
}

int sum (int a, int b)
{
int sum = 0;
int carry = 0;
while ( a )
{
carry = a & b;
sum = a ^ b;
carry = carry << 1;
a = carry;
}
return sum;
}

Amazon Question: An array is containing only 0 and 1. Find out the largest subarray in which number of 1s are equal to number of 0s.

Solution: 

1. Replace 0 with -1.
2. Find the cumulative sum at each index.
3. In the cumulative sum array if at some index sum is 0 that means from index 0 to current index number of 0 and 1 are same.
4. If there are duplicates in the cumulative sum array that means the cumulative sum is 0 in between so there are equal number of 0s and 1s.
5. Just find out the longest one and return it.

Source Code:

string longestSubStrWithEqual0and1(int *arr, int size)
{
    string strResult = "";
    map<int, int> mapIntToInt;
    if(arr == NULL || size == 0)
        return strResult;
    int i=1;
    int* cumSumArr = new int[size];
    if(arr[0] == 1)
        cumSumArr[0] = 1;
    else if(arr[0] == 0)
        cumSumArr[0] = -1;
    else
        return strResult; // Error as there is interger other than 0 and 1 in array
    for(; i<size; ++i)
    {
        if(arr[i] == 0)
            cumSumArr[i] = cumSumArr[i-1] + (-1);
        else if(arr[i] == 1)
            cumSumArr[i] = cumSumArr[i-1] + 1;
        else
            return strResult; // Error as there is interger other than 0 and 1 in array
    }
   
    int maxLen =0;
    int startIndex = 0;
    int endIndex = 0;
    for(i=0; i<size; ++i)
    {
        if(mapIntToInt.find(cumSumArr[i]) == mapIntToInt.end())
        {
            mapIntToInt[cumSumArr[i]] = i;
        }
        else
        {
            int len = i - mapIntToInt[cumSumArr[i]];
            if(maxLen < len)
            {
                maxLen = len;
                startIndex = mapIntToInt[cumSumArr[i]] + 1;
                endIndex = i;
            }
        }
        if(cumSumArr[i] == 0)
        {
            maxLen = i + 1;
            startIndex = 0;
            endIndex = i;
        }
       
    }
    if(maxLen > 0)
    {
        for(i = startIndex; i <= endIndex; ++i)
        {
            strResult += ('0' + arr[i]);         }
    }
    delete [] cumSumArr;
    return strResult;
}

Salesforce Question: Spiral Order Traversal of Binary Tree

void BinaryTree::SpiralTraversal(Node* root)
{
    stack<Node*> stack1, stack2;
    stack1.push(root);
    while(!stack1.empty() || !stack2.empty())
    {
        while(!stack1.empty())
        {
            Node* node1 = stack1.top();
            stack1.pop();
            cout<<node1->data<<'\n';
            if(node1->right)
                stack2.push(node1->right);
            if(node1->left)
                stack2.push(node1->left);
        }
        while(!stack2.empty())
        {
            Node* node2 = stack2.top();
            stack2.pop();
            cout<<node2->data<<'\n';
            if(node2->left)
                stack1.push(node2->left);
            if(node2->right)
                stack1.push(node2->right);
        }
    }
}

Amazon Question: Design LRU Cache

It was told that cache will have a key, value pair(int, int).

Solution is to take hash with key as cache key and value is Node where Node is the address of the node in the linked list which contains the same key. Linked list node contains cache key and cache value.


Insert Operation --

1. Make a node "Node" with key and value and put that node at the end of linked list. 
2. if count of nodes are more than cache size then remove head node from linked list , also remove hash[head->key].
3. Update hash as hash[Node->key] = Node

Get Operation --

1. Get operation will return the cache value of given cache key. Also now it will make this key is the most recently used one.
2. Get the Node by hash[key] and move that Node at the end of linked list.
3. Return hash[key]->value.   

Implementation in C#:

    public class LRUCache

    {

        public LRUCache(int capacity)

        {

            this.currentCount = 0;

            this.cacheCapacity = capacity;

            this.list = new LinkedList<KeyValuePair<int, int>>();

            this.hash = new Dictionary<int, LinkedListNode<KeyValuePair<int, int>>>();

        }

        public int Get(int key)

        {

            if (hash.ContainsKey(key))

            {

                list.Remove(hash[key]);

                list.AddLast(hash[key]);

                return hash[key].Value.Value;

            }

            return -1;

        }

        public void Put(int key, int value)

        {

            if (hash.ContainsKey(key))

            {

                hash[key].Value = new KeyValuePair<int, int>(key, value);

                list.Remove(hash[key]);

                list.AddLast(hash[key]);

            }

            else

            {

                if (currentCount + 1 > cacheCapacity)

                {

                    LinkedListNode<KeyValuePair<int, int>> linkedListNode = list.First;

                    list.RemoveFirst();

                    hash.Remove(linkedListNode.Value.Key);

                }

                else

                {

                    ++currentCount;

                }

                LinkedListNode<KeyValuePair<int, int>> newNode = new LinkedListNode<KeyValuePair<int, int>>(new KeyValuePair<int, int>(key, value));

                list.AddLast(newNode);

                hash.Add(key, newNode);

            }

        }

        Dictionary<int, LinkedListNode<KeyValuePair<int, int>>> hash;

        LinkedList<KeyValuePair<int, int>> list;

        private int cacheCapacity;

        private int currentCount;

    }