Saturday, December 10, 2011

Search an element in sorted rotated array

int binarySearch(int arr[], unsigned int low, unsigned int high, int key)
{
    if( low == high && arr[low] != key)
    {
       return -1;
    }

    unsigned int mid = low + (high - low)/2;

    if(key == arr[mid])
    {
       return mid;
    }  
    else if (key > arr[mid])
    {
       return binarySearch(arr, mid + 1, high, key);
    }
    else
    {
       return binarySearch(arr, low, mid - 1, key);
    }
}


int search(int arr[], unsigned int low, unsigned int high, int key)
{
    if( low == high && arr[low] != key)
    {
       return -1;
    }

    unsigned int mid = low + (high - low)/2;

    if(key == arr[mid])
    {
       return mid;
    }
    else if(arr[mid] < arr[low]) // That means that the right half may be sorted
    {
       if((key > arr[mid]) && (key <= arr[high]))
       {
           return binarySearch(arr, mid + 1, high, key);  //Here we know we just need to look
                                                                               //into sorted part of array
       }
       else
       {
           return search(arr, low, mid-1, key);
       }
    }
    else // That means that the Left half may be sorted
    {
       if((key >= arr[low]) && (key < arr[mid]))
       {
           return binarySearch(arr, low, mid - 1, key);  //Here we know we just need to look
                                                                              //into sorted part of array
       }
       else
       {
           return search(arr, mid + 1, high, key);
       }
    }
}

Tuesday, December 6, 2011

5 Pirates and 100 Gold Coins

Question:
Five pirates got a chest containing 100 gold coins. Now they need to think about a distribution strategy. The pirates are ranked  (Pirate 1 to Pirate 5, where Pirate 5 is the most powerful). The most powerful pirate gets to propose a plan and then all the pirates vote on it. If at least half of the pirates agree on the plan, the gold is split according to the proposal. If not, then that pirate will be killed and this process continues with the remaining pirates until a proposal is accepted. The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan? 

Solution:
Reduce this problem to only 2 pirates. So what happens if there are only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates, the proposal has to be accepted.

Now in 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to give one gold coin to Pirate 1 . Pirate 1 knows that one gold coin is better than nothing so he has to back Pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}.
If there are 4 pirates, Pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 knows that if he dies, pirate 2 will get nothing (according to 3 pirates situation) so he will give one gold coin to pirate 2 to get his vote. So the distribution will be {0, 1, 0, 99}.

Now in 5 pirates situation, Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. so he can give one gold coin to Pirates 1 and 3 to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. 

Tuesday, November 29, 2011

ThoughtWorks Question: Game of Life

Game of Life:
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
4. Any dead cell with exactly three live neighbours comes to life.

The initial pattern constitutes the 'seed' of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed - births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. (In other words, each generation is a pure function of the one before.) The rules continue to be applied repeatedly to create further generations.

Problem:
The inputs below represent the cells in the universe as X or - . X is a alive cell. - is a dead cell or no cell. The below inputs provide the provide pattern or initial cells in the universe . The output is the state of the system in the next tick (one run of the application of all the rules) , represented in the same format.
------------------------------------------------------------------------------------------------------------------
Input A:
(Block pattern - Still life)
1, 1
1, 2
2, 1
2, 2
Output A:
1, 1
1, 2
2, 1
2, 2
------------------------------------------------------------------------------------------------------------------
Input B
(Boat pattern - Still life)
0, 1
1, 0
2, 1
0, 2
1, 2
Output B
0, 1
1, 0
2, 1
0, 2
1, 2
------------------------------------------------------------------------------------------------------------------
Input C
(Blinker pattern - oscillator)
1, 1
1, 0
1, 2
Output C
1, 1
0, 1
2, 1
------------------------------------------------------------------------------------------------------------------
Input D
(Toad pattern - two phase oscillator)
1, 1
1, 2
1, 3
2, 2
2, 3
2, 4
Output D
0, 2
1, 1
1, 4
2, 1
2, 4
3, 3
==========


Solution:

http://www.mediafire.com/?jp9jut9c6k8w320


Tuesday, November 1, 2011

Infibeam Question: Reverse Level Order Traversal of Binary Tree

void BSTree::reverseLevelOrderTraversal(Node* node)
{
    queue<Node*> qu;
    stack<int> st;
    qu.push(node);
    while(!qu.empty())
    {
        Node* temp = qu.front();
        st.push(temp->data);
        if(temp->right)
            qu.push(temp->right);
        if(temp->left)
            qu.push(temp->left);
        qu.pop();
    }
    while(!st.empty())
    {
        cout<<st.top()<<'\t';
        st.pop();
    }
}

Infibeam Question: Implement T9 Dictionary

Solution is to take hash with key is the number and the value is the list of words which can be made by pressing the digits in the number. For example 4663 --> good, home

LoadWords Operation --

   1. Read words and their popularity one by one from file.
   2. Get the number corresponding to the word.
   3. Make an object which contains the word and its popularity.
   4. hash[number].insert(wordObject).

DisplayWords Operation --

It was given that most popular 5 words need to be displayed.
  1. Maintain a heap based on popularity of size 5.
  2. Maintain the keys in the hash in string sorted order. ( Map can be used for hash)
  3. Look for the keys which are started with the given number.

Source Code --

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<fstream>
#include<algorithm>

using namespace std;

//Class word
class Word
{
public:
    Word(string w="", int p=0);
    string getWord();
    int getPopularity();
private:
    string word;     //actual word
    int popularity;  //popularity of word
};

Word::Word(string w, int p):word(w), popularity(p)
{
}

string Word::getWord()
{
    return word;
}

int Word::getPopularity()
{
    return popularity;
}

//Comparator function used to sort the vector of Word with key popularity of the word
bool wordCompare(Word a, Word b)
{
    return a.getPopularity() == b.getPopularity() && a.getWord() < b.getWord() || 
    a.getPopularity() > b.getPopularity();
}

//This is helper class to T9Dictionary class. It uses heap to maintain the top 5 i.e. total words to display
class T9DictDisplayHelperHeap
{
public:
    T9DictDisplayHelperHeap(int num = 5);  //num is number of words to display
    void pushHeap(Word word);   //insert word into heap
    void displayWords();        //display the words
private:
    int count;
    vector<Word> vectWord;        //heap
    const short wordsToDisplay;
};

T9DictDisplayHelperHeap::T9DictDisplayHelperHeap(int num):wordsToDisplay(num), count(0)
{
    vectWord.reserve(wordsToDisplay);
}

void T9DictDisplayHelperHeap::pushHeap(Word word)
{
    if(count<wordsToDisplay)
    {
        vectWord.push_back(word);
        count++;
    }
    else if(count == wordsToDisplay)
    {
        make_heap(vectWord.begin(), vectWord.end(), wordCompare);
        if(vectWord.front().getPopularity() < word.getPopularity())
        {
            pop_heap(vectWord.begin(), vectWord.end(), wordCompare);
            vectWord.pop_back();
            vectWord.push_back(word);
            push_heap(vectWord.begin(), vectWord.end(), wordCompare);
        }
        count++;
    }
    else
    {
        if(vectWord.front().getPopularity() < word.getPopularity())
        {
            pop_heap(vectWord.begin(), vectWord.end(), wordCompare);
            vectWord.pop_back();
            vectWord.push_back(word);
            push_heap(vectWord.begin(), vectWord.end(), wordCompare);
        }
    }
}

void T9DictDisplayHelperHeap::displayWords()
{
    if(count < wordsToDisplay)
        sort(vectWord.begin(), vectWord.end(), wordCompare);
    else
    {
        sort_heap(vectWord.begin(), vectWord.end(), wordCompare);
    }
    int size = vectWord.size();
    for(int i = 0; i < size; ++i)
        cout<<vectWord[i].getWord()<<" : "<<vectWord[i].getPopularity()<<'\n';
}

//Dictionary Class. It is using map in which key is the number and the value is vector of corresponding words
class T9Dict
{
public:
    T9Dict(int count = 5);   //count is number of words to display
    bool loadWords(string fileName);   // load words from a file, fileName is the path of the file which contains words to be inserted in dictionary
    void displayWords(string num);       
private:
    const short wordsToDisplay;
    void addWord(string key, Word w);
    map<string, vector<Word> > mapWords;
};

T9Dict::T9Dict(int count):wordsToDisplay(count)
{
}

// For each alphabet it is taking the corresponding number like for a,b,c corresponding number is 2
// For space ' ' number is 0
// For digits number is same as the digit given
// For all other special charcters number is 1

bool T9Dict::loadWords(string fileName)
{
    ifstream in(fileName.c_str());
    if(!in)
    {
        cout<<"File: "<<fileName<<" does not exist or not accessible\n";
        return false;
    }
    int popularity = 0;
    char *temp = new char[256];
    string word;
    while(!in.eof())
    {
        string key = "";
        in>>popularity;
        //in>>word;
        in.getline(temp, 255);
        word.clear();
        word = string(temp);
        word = word.substr(1);
        int len = word.length();
        for(int i=0; i<len; ++i)
        {
            word[i] = tolower(word[i]);
            if(word[i] == ' ')
                key += '0';
            else if(word[i] >= '0' && word[i] <= '9')
            {
                key += word[i];
            }
            else if(word[i] >= 'a' && word[i] <= 'o')
            {
                key += (((word[i] - 'a') / 3) + 2 + '0') ;
            }
            else if(word[i] >= 'p' && word[i] <= 's')
            {
                key += '7';
            }
            else if(word[i] >= 't' && word[i] <= 'v')
            {
                key += '8';
            }
            else if(word[i] >= 'w' && word[i] <= 'z')
            {
                key += '9';
            }
            else
            {
                key += '1';
            }
        }
        addWord(key, Word(word, popularity));
    }

    delete temp;
    for(map<string, vector<Word> >::iterator it = mapWords.begin(); it != mapWords.end(); 
    ++it)
    {
        sort(it->second.begin(), it->second.end(), wordCompare);
    }
    return true;
}

void T9Dict::addWord(string key, Word word)
{
    mapWords[key].push_back(word);
}

void T9Dict::displayWords(string num)
{
    T9DictDisplayHelperHeap heap;
   
    map<string, vector<Word> >::iterator it = mapWords.begin();
    while(it != mapWords.end() && it->first < num)
    {
        it++;
    }
    int len = num.length();
    while(it != mapWords.end() && (it->first.substr(0, len) == num))
    {
        for(unsigned int i=0; i < it->second.size(); ++i)
            heap.pushHeap(it->second[i]);
        it++;
    }

    heap.displayWords();
}

Thursday, October 13, 2011

Informatica Question: Given a transaction log in which each line contains a transaction detail (Customer Id, Customer name, Price), Find out the average price given by a customer.

Solution:

1. Read each line, extract customer id and price.

2. Maintain a hash in which key is customer id and value is pointer to struct defined as below -
    struct details
    {
       long totalPrice;
       int count;
     };

3. For each transaction do
    i.  hash[customerId]->totalPrice += extractedPrice;
    ii. hash[customerId]->count++;

4. Now for given customer, average price = hash[customerId]->totalPrice / hash[customerId]->count;

Wednesday, October 5, 2011

Range Minimum Query

You can find the description and implementation using c++ of Range Minimum Query(RMQ) in the following link -

http://algods-cracker.blogspot.com/p/algorithms.html#RMQ

Knuth-Morris-Pratt Algorithm: String Matching in Linear time

You can find the description and implementation using c++ of Knuth Morris Pratt ( KMP)  in the following link -

http://algods-cracker.blogspot.com/p/algorithms.html#Knuth

Count Sort: Sorting in linear time

You can find the description and implementation using c++ of Count Sort in the following link -

http://algods-cracker.blogspot.com/p/algorithms.html#Count

Tuesday, October 4, 2011

Find Least Common Ancestor of two nodes in a Binary Tree


Node* BSTree::LCA(Node* node, int num1, int num2)
{
if(!node)
return NULL;
else
{
if(node->data == num1 || node->data == num2)
return node;
else
{
Node* leftLCA = LCA(node->left, num1, num2);
Node* rightLCA = LCA(node->right, num1, num2);
if(leftLCA && rightLCA)
return node;
else if(leftLCA)
return leftLCA;
else if(rightLCA)
return rightLCA;
   else
    return NULL;
}
}
}

Amazon Question: Set inorder successor of each node of Binary Tree

Solution:
1. Do reverse inorder traversal.
2. Set inorder successor to the previous node.

Source Code:
// Given node structure -

struct Node
{
int data;
Node* left;
Node* right;
Node* inorderSuccessor;
};


void BSTree::fillInorderSuccessor(Node* node, Node*& prev)
{
if(node)
{
fillInorderSuccessor(node->right, prev);
node->inorderSuccessor = prev;
prev = node;
fillInorderSuccessor(node->left, prev);
}
}

Amazon Question: Find number of vertical lines that can cover whole nodes of Binary Tree

Solution:

1. Do a preorder traversal.
2. Initialize count to 0.
3. Whenever encounter a left node increase count by 1.
4. Whenever encounter a right node decrease count by 1.
5. Return maxCount - minCount + 1.

Source Code:

int BTree::findVerticalLinesToCut(Node* node, int count)
{
static int max = 0, min = 0;
if(node)
{
max = max < count? count : max;
min = min > count ? count : min;

if(node->left)
{
findVerticalLinesToCut(node->left, count+1);
}
if(node->right)
{
findVerticalLinesToCut(node->right, count-1);
}
}
return max - min + 1;
}

Monday, October 3, 2011

Find the maximum sum of sub array within an array.


int maxSum(int *arr, int size)
{
    if(arr == NULL)
        return 0;
   
    int sum = 0, maxSum = 0, maxNo = arr[0];
    for(int i=0; i<size; ++i)
    {
        maxNo = arr[i] > maxNo ? arr[i] : maxNo;   //if all elem of array are negative the maxNo is the max sum
        sum += arr[i];
        if(sum < 0)
            sum = 0;
        else
            maxSum = sum > maxSum ? sum : maxSum;
    }
    if(maxNo < 0)
        return maxNo;
    return maxSum;
}

You are given an array of n+2 elements. All elements in the array are in range 1 to n and all elements occur once except two numbers which occur twice. Find the two repeating numbers.


void findDup(int* arr, int n, int& x, int& y) // x and y will be our result
{
    int xor = 0;
    for(int i=1; i<=n; xor^=i++);
    for(i=0; i<n+2; xor^=arr[i++]);
    int setBit = xor & ~(xor -1);
    for(i=0;i<n+2;++i)
        (arr[i] & setBit) ? (x ^= arr[i]) : (y ^= arr[i]);
    for(i=1; i<=n; ++i)
        (i & setBit) ? (x ^= i) : (y ^= i);   
}

Saturday, October 1, 2011

Sort array which contains only 0, 1 or 2 in O(n)


void Sort(int* arr, int length)
{
    for (int low = 0, mid = 0, high = length-1; mid<=high;)
    {
        switch(arr[mid])
        {
        case 0: Swap(arr[low++], arr[mid++]);
                break;
        case 1: ++mid;
                break;
        case 2: Swap(arr[mid], arr[high--]);
                break;
        }
    }
}

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

Thursday, August 4, 2011

Salesforce Question: Given two arrays A and B, find out elments of B which are not in A

Hash all the elements of A.
if B[i] is not in hash add into the result. 0<=i<sizeof(B)


Salesforce Question: In an unsorted array, find a pair (a, b) such that a+b = k

It was given that pair will be unique.
void FindPair(int* arr, int size, int sum)
{
    for(int i=0; i<size; ++i)
          hash[arr[i]] = 1;
    for(int i=0; i<size; ++i)
    {
           if(hash[sum-arr[i]])
                cout<<"Pair found ( " <<arr[i]<<", "<<sum-arr[i]<<" )";
      }
}


Tuesday, May 3, 2011

Pubmatic Question: Average of the elements of an array

Only Problem in this question is to tackle integer overflow. Instead of doing
(a[0] + a[1] + ....a [n-1])  /  n
do as following --
a[0]  / n + a[1]  /  n + ..... a[n-1]  /  n