Ebay Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Node.send((id+1)%max,sum);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

I thought the send & receive functions are exactly the ones we are being asked to code?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0

AAARGH ....
the last line should be
send(2*id + 2, sum);
Apologies for the mistake.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0

Whatever data you want to send to the node with the id idTo.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.