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