Amazon Interview Question
Software Engineer / Developersif the conversation is aloud, then c can know the salary of b.
zdmytriv's solution below sounds more robust.
a, b, c - salaries
For each cases divide salaries into random pieces
a = a1 + a2
b = b1 + b2
c = c1 + c2
first A will tell a1 to B , now b will add b1 to a1 and send [a1+b1] to C
Now C will add c1 to this . Now C have s1=[a1+b1+c1].
Now C will send c2 to B and B will add b2 to this and send [c2+b2] to A, now A will add a2 tho this. So A have s2=[a2+b2+c2]
Now Finally set average by [s1+s2]/3
This can also be solved as follows:
Here x, y and z are random numbers.
A gives a+x to B
B gives a+x+b+y to C
C gives a+x+b+y+c+z to A
Now, A will subtract x from the sum and give it to B. Similarly B will subtract y from the sum and give it to C, C can then subtract z and get the average.
a, b, c - salaries
For each cases divide salaries into random pieces
a = a1 + a2
b = b1 + b2
c = c1 + c2
a and c tells a1 and c1 to b: a1 + b1 + c1 = s1
a and b tells a2 and b2 to c: a2 + b2 + c2 = s2
(s1 + s2)/3 - average
The random number answer sounds great.
Let A, B and C disclose their salaries to D, and D do the calculation and then tell them the average.
A picks 2 random numbers, a1 and a2, such that average(a1, a2)=salary(A). B and C do the same.
A gives a1 to B, who calculates B'=average(a1, b2)
B gives b1 to C, who calculates C'=average(b1, c2)
C gives c1 to A, who calculates A'=average(c1, a2)
Now the A', B' and C' can be revealed and final average calculated.
salary A + random A ( A gives this to B )
salary A + random A
salary B + random B ( B gives this to C )
salary A + random A
salary B + random B
salary C + random C ( C gives this to A )
salary A+
salary B + random B
salary C + random C ( A removes random A & gives the total to B )
salary A+
salary B+
salary C+ random C ( B removes random B & gives the total to C )
salary A+
salary B+
salary C+ ( C removes random C & gives the total to A )
now A has the total of their salaries from which Average can be calculated..
c fixes 2 arbitary nos x and y....he tell x to a and y to b
a adds x to his salary and passes the sum to b..
b adds y to his salary and adds a's pseudo salary to it and passes it to c..
c subtracts x+y from the sum and adds his salary to it and divides it by 3...
now the avg is declared!!!!
Solution for this case is very simple. Just ask the first person to add a random value to his salary and pass it on to the next person. The other person will add his salary value to it and pass it on to the other. Finally, the total sum is passed on to first person. He subtracts his value to get the total sum. Finding the average is then trivial.
- Anonymous February 27, 2008