CareerCup

Use 3 rats

R1 drinks all bottles with right most bit turned on.
R2 drinks all bottles with 2nd bit turned on
R3 drinks all bottles with MSB turned on

7 1 1 1 R3, R2, R1

6 1 1 0 R3, R2,

5 1 0 1 R3, , R1

4 1 0 0 R3, ,

3 0 1 1 , R2, R1

2 0 1 0 , R2,

1 0 0 1 , , R1

0 0 0 0

Now if Bottles 1-7 contain poison, then the killing of rats combination will tell us the answer.
And If no rat gets killed, Bottle 0 has the poison.

Nice solution.
I think (i+1) % N is not reqd.

The idea is to think of an array containing 0, -ve, +ve numbers (formed by A[i] - B[i])

Now keep a running sum that should never go below 0.
When it goes below 0, then make 'k' as the next index.

Working Code:

int FindK(int A[], int B[], int N)
{
    int start_index = 0;
    int sum = 0, i;

    for (i=0; i<N; i++) {
        sum += A[i] - B[i];

        if (sum < 0) 
        {
            sum = 0;
            start_index = i+1; 

        }
    }
    
    return start_index;
}

If you initialize curSum to -INFINITY, it will work with all -ve value as well.

Some ideas to determine the location of a webpage:
- Language
- Phone No.
- Zipcode
- Places mentioned in the webpage
- Location of other URLs on the page
- Location of other webpages hosted on the same website.

/* Write a function that given any node in the Binary Tree, returns
 * the next node in the inorder traversal
 */
Node * getNextInorderNode(Node *in)
{
    if (!in) return in;

    Node *tmp = in->right;
    /* Next Inorder candidate is the leftmost node in the right subtree */
    if(tmp) {
        while(tmp->left) tmp=tmp->left;
        return tmp;
    }

      /* Inorder candidate could be at upper levels */
    tmp=in;
    /* keep going up if tmp is the right child
     * stop only if tmp becomes left child of a parent
     */
    while(tmp->parent && tmp->parent->right == tmp) {
        tmp = tmp->parent;
    } 
    if (tmp->parent == NULL) {
        return NULL;
    } else if(tmp->parent->right != tmp &&
            tmp->parent->left == tmp) {
        return tmp->parent;
    }
}