Friday, September 16, 2011

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 != smallList )
{
      longList  =  longList -> next ;
      smallList = smallList -> next ;
}

return longList ;

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

Thursday, September 8, 2011

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

Saturday, September 3, 2011

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 LRUCache

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.   

Source Code:

struct Node
{
    int key;
    int value;
    Node* next;
    Node(int k, int v, Node* ptr=NULL):key(k), value(v), next(ptr){}
};

class List
{
public:
    List();
    Node* insert(int k, int v);
    Node* remove();
    Node* move(Node* node);
    void swap(Node* node1, Node* node2);
private:
    Node* head;
    Node* tail;
};

class LRUCache
{
public:
    LRUCache(int n);                 // cache can contain maximum of "n" elements
    bool put(int key, int value);   // insert the key value pair in cache
    int get(int key);                 // get the value of the given key, also it updates the lru table as it is the recently used item
 
private:
    int count;
    const int size;
    map<int, Node*> hashMap;
    List list;
};

// Function definitions -- .cpp file

List::List():head(0), tail(0)
{
}

Node* List::insert(int k, int v)
{
    Node* temp = new Node(k, v);
    if(!head)
    {
        head = temp;
        tail = temp;
    }
    else
    {
        tail->next = temp;
        tail = temp;
    }
    return temp;
}

Node* List::remove()
{
    Node* temp = head;
    if(temp == NULL)
        return NULL;
    if(temp == tail)
    {
        tail = NULL;
        head = NULL;
    }
    else
    {
        head = head->next;
    }
    return temp;
}

Node* List::move(Node* node)
{
    if(node == NULL)
        return NULL;
    if(node == tail)
        return tail;
    if(node == head)
    {
        Node* temp = head;
        head = head->next;
        tail->next = temp;
        tail = temp;
        tail->next = NULL;
        return tail;
    }
   
    Node* temp = node->next;
   
    swap(node, temp);
   
    if(temp != tail)
    {
        node->next = temp->next;
        tail->next = temp;
        temp->next = NULL;
        tail = temp;
    }

    return tail;
}

void List::swap(Node* node1, Node* node2)
{
    //Swap Keys
    node1->key = (node2->key)^(node1->key);
    node2->key = (node2->key)^(node1->key);
    node1->key = (node2->key)^(node1->key);
   
    //Swap Values
    node1->value = (node2->value)^(node1->value);
    node2->value = (node2->value)^(node1->value);
    node1->value = (node2->value)^(node1->value);
}

LRUCache::LRUCache(int n):size(n), count(0)
{
}

bool LRUCache::put(int key, int value)
{
    if(hashMap.find(key) != hashMap.end())
    {
        return false;
    }
    if(count < size)
    {
        count++;
        Node* temp = list.insert(key, value);
        hashMap[key] = temp;
    }
    else
    {
        Node* temp = list.remove();
        if(temp)
        {
            hashMap.erase(temp->key);
            delete temp;
            temp = list.insert(key, value);
            hashMap[key] = temp;
        }
        else
            return false;
    }
   
    return true;
}

int LRUCache::get(int key)
{
    int ret = -9999; //error value
    if(hashMap.find(key) != hashMap.end())
    {
        Node* temp1 = hashMap[key];
        ret = temp1->value;
        Node* temp2 = list.move(temp1);
        hashMap[key] = temp2;
        hashMap[temp1->key] = temp1;
    }
    return ret;
}