Tuesday, February 11, 2014

Rotate a Linked List

Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer.

To rotate the linked list, we need to change next of kth node to NULL, next of last node to previous head node, and finally change head to (k+1)th node. So we need to get hold of three nodes: kth node, (k+1)th node and last node.

void rotateList(Node *&head, int k)
     if (k == 0)

    Node* curr = head;

    int count = 1;
    while (count < k && curr != NULL)
        curr = curr->next;

    if (curr == NULL)

    Node *kthNode = curr;

    while (curr->next != NULL)
        curr = curr->next;

    curr->next = head;
    head = kthNode->next;
    kthNode->next = NULL;

Pairwise swap nodes of a given linked list.

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

    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;

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

Average salary of n people in the room.

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

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). B 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 (Sn) 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)