Pairwise swap nodes of a given linked list.

void pairWiseSwap(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return;

    Node *prev = head;
    Node *curr = head->next;

    head = curr;

    while (1)
    {
        Node *next = curr->next;
        curr->next = prev;

        if (next == NULL || next->next == NULL)
        {
            prev->next = next;
            break;
        }

        prev->next = next->next;
        prev = next;
        curr = prev->next;
    }
}

Average salary of n people in the room.

Question:

How can n people know the average of their salaries without disclosing their own salaries to each other?

Solution:

Let's say salaries of n people (P1, P2, P3.....Pn) are S1, S2, S3.....Sn respectively. To know the average of the salary i.e. (S1 + S2 + S3 + ..... + Sn) / n, they will follow the following steps -

1. P1 adds a random amount, say R1 to his own salary and gives that to P2 (P2 won't be able to know P1's salary as he has added a random amount known to him only). In this case, P2 will receive the figure (S1 + R1) from P1.
2. P2 does the same and gives the final amount to P3 (without showing that to anyone). Now P3 will get the figure (S1 + R1 + S2 + R2).
3. Rest of the persons (P3, P4, P5.....Pn) do the same. Pn will give the final amount to P1. Now P1 will have (S1 + R1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
4. Now P1 subtracts his random amount (R1) and gives the final figure to P2 (without showing that to anyone). P2 will now receive the figure (S1 + R1 + S2 + R2 + S3 + R3 + .... Sn  + Rn) - R1 = (S1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
5. P2 subtracts his random amount (R2) and gives the final figure to P3 (without showing it to anyone). P3 will receive the amount (S1 + S2 + S3 + R3 + ..... Sn + Rn).
6. In the same way every person remaining except (Pn) will subtract their random amount and give it to the next one. Now Pn will have (S1 + S2 + S3 + ..... Sn + Rn).
7. Now Pn subtracts his random amount (Rn) and then the figure becomes (S1 + S2 + S3 + .... + Sn). Pn will divide this amount by n and get the average i.e. (S1 + S2 + S3 + ..... + Sn) / n and show to every one in the room.

(Puzzle was asked in the Yahoo interview)

MAZ Digital: Implement push, pop, findmin in O(1) without using extraspace

Maintain a variable min which will contain the minimum element.

push(n):     if(n < min)
                 {
                      stack.push( n - (min - n) );
                      min = n
                 }
                 else
                 {
                       stack.push(n)
                 }

pop():        retVal = stack.pop();
                 if( retVal < min)
                 {
                       temp = min;
                       min = min + ( min - retVal);
                       retVal =  temp
                 }
                 return retVal;

findMin():  return min;

Amazon Question: Find the first occurrence of an integer in an array.

Given an array of integers in which the difference between  two adjacent integers is less than or equal to 1. Find the first occurrence of an given integer. Do better than linear search.


int firstOccurence(vector < int > A, int n)
{
    int i = 0;
    int size = A.size();
    while(i < size)
    {
if(A[i] == n)
return i;

i += abs(n - A[i]);
    }
    return -1;
}

Microsoft Question: Find balanced binary sub-tree of size N within a binary tree

void BinaryTree::findBalancedTree(Node* node, int& height, int& size, int N, Node*& out)
{
if(!node)
{
size =0;
height = 0;
return;
}
int lheight = 0, rheight = 0, lsize = 0, rsize = 0;
findBalancedTree(node->left, lheight, lsize, N, out);
findBalancedTree(node->right, rheight, rsize, N, out);

if(abs(lheight - rheight) <= 1 && lsize + rsize + 1 == N)
{
out = node;
}

height = max(lheight, rheight) + 1;
size = lsize + rsize + 1;
}

Check if a binary tree is BST or not

bool BinaryTree::isBST(Node* node)

{
static Node* prev = 0;
if(node)
{
if(!isBST(node->left))
return false;
if(prev && node->data <= prev->data)
return false;
prev = node;
return isBST(node->right);
}
return true;
}

Populate Inorder Successor for all nodes.

Problem: Given a Binary Tree where each node has following structure, write a function to populate next pointer for all nodes. The next pointer for every node should be set to point to in-order successor.


struct Node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
};

Solution:  1. In constructor, made all node's next pointer NULL. 2. Traverse the given tree in reverse inorder traversal and keep track of previously visited node.  3. When a node is being visited, assign previously visited node as next. Implementation: //Public Interface void BTree::populateInOrderSuccessor() {     populateInOrderSuccessor(root);  } //Actual Working void BTree::populateInOrderSuccessor(Node* node) {          Node *tempNext = NULL;     if (node)     {         populateInOrderSuccessor(node->right);         node->next = tempNext;         tempNext = node;         populateInOrderSuccessor(node->left);     } }