CareerCup

Solution

1 Node with id=0 will send message to next node with it's node value.
2 Next node will receive value from previous node and will add it's value, which it will send to next node.
3 Every node will do the same step 2.
4 After step 2 execution by every node last node will know the sum which it will send to first node.
5 now all the nodes in system will pass this sum to it's next node.

In this approach whole system will transfer 2*n-1 messages.

class Daemon {

public static void main(String[] args) {

int sum=node.val;
if(node.id!=0) //if it's not first node wait to receive message from previous node.
sum+=Node.recv((id-1)%max);

//Send sum to next node.
Node.send((id+1)%max,sum);

//receive final sum from previous node.
sum=Node.recv((id-1)%max);
Sysout.out.println("Sum = "+sum);

//Notify net node about sum.
Node.send((id+1)%max,sum);
}
}

Can you send other code where you mentioned Node and function for send and receive message.

Really stumped me. So I started with O(n^2) solution:

int GetSum()
{
    int sum = 0;
    // Get values from all nodes prior it self
    for(int i = 0; i < id; ++i)
    {
        sum + = recv(i);
    }
    
    // Send self value to all prior to self
    for(int i = 0; i < id; ++i)
    {
        send(i, val);
    }
    
    // Send self value to all after self
    for(int i = id+1; i < N; ++i)
    {
        send(i , val);
    }
    
    // Get values from all after self
    for(int i = id+1; i < N; ++i)
    {
        sum+= recv(i);
    }
    
     return sum+val;   
}

Then I realized it can be done in O(n):

#define SERVER = 0

int GetSum()
{
    int sum =0;
    if(id == SERVER)
    {
        for(int i = 1; i< N; ++i)
        {
            sum + = recv(i);
        }
        
        sum += val;

        for(int i = 1; i < N; ++i)
        {
            send(i, sum);
        }
        
        return sum;
    }
    
    send(SERVER, val);
    return recv(SERVER);
}

But he wanted better. After multiple clues, it was clear that since the IDs of the Nodes are sorted and in sequence from 0 to N-1, we can consider the nodes as tree, with 0 as root and the children of a Node will be (2*ID+1) parent would (ID-1)/2.
And we can take a recursive Binary approach.

int GetSum()
{
    // break condition
    if(2*id + 1 > N-1 )
        {
            send((id-1)/2, val);
            sum = recv((id-1)/2);
            return sum;
         }
    // recurse
    int sum = val + recv(2*id + 1) + recv(2*id + 2);
    
    // send to parent:
    if(id !=0)
    {
        // send partial sum to parent
        send((id-1)/2, sum);    
        
        // receive full sum from parent
        sum = recv((id-1)/2);      
    }    
    
    // Send final sum to children
    send(2*id + 1, sum);
    send(2*id + 1, sum);

}

What is "payload" in the void send(int idTo, int payload)