## Ebay Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

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

@Mystic

Only the function signature was provided. He didn't provide the function itself.

I had to code the solution without the code for send and receive.

I am curious as to how will it help to know the code for send and receive? Will help me improve my understanding.

Thanks.

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

Solution

- Bajaj June 14, 20131 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);

}

}