Adobe Abs india pvt. ltd. Interview Question Software Engineer / Developers Interns
Team: Lifecycle
Country: India
That works fine if there's a fourth person trusted by everyone else. What if there's not?
Cool, but consider the following scenario: after the second person has told his answer to the third person .... the third person gives a high five to the first person and yells "Gotcha" to the second person ;).
Just kidding....excellent solution by the way!
The point you bring up is quite interesting.
In this particular problem with just 3 people, it's not possible to avoid the threat you mentioned. If everyone is informed of the result of the computation, it doesn't take anything fancy for two conspirators to figure out the salary of the third person. Really, they need not even consider the algorithm being used. They can just multiply the average by 3, subtract out their salaries, and they'll be left with the salary of the third person.
However, here's an interesting question. Say we have k people. You can see how the algorithm described can generalize to k people. But...if the third person tells the first person what he heard from the second person, the second person's salary can be compromised. For k > 3, this might be preventable if we use a different algorithm. For k > 3, if two people conspire together, only their knowing the sum of the remaining k-2 people's salaries is unavoidable. If k=100, there's still a lot of anonimity to be had in that. However, the simple algorithm that I described does not grant any such protection.
In fact, we might ask whether it's possible to design an algorithm that given k people, x of which are working together, ensures that these x people can learn absolutely nothing more than the sum of the remaining k-x salaries, which they could have obtained via a simple calculation anyway. This is, in fact, possible via a very beautiful algorithm.
How about this:
Let the individuals be labeled as A, B, C. Let's suppose that we place them in a circular queue, each person subtracts some undisclosed portion from his salary and tells it to the next person in the ordering. Each individual receives this value and "adds" it to his own salary. Then we go through and add up the values, and divide by 3.
A will whisper a random number in B's ears. B will add his salary to this random number and whisper the sum in C's ears. C will add his salary to the sum and whisper in A's ears. A will substract the random number and add his salary to the final sum. Then he will divide the total with 3 and announce the average
The solution by dn is assuming that there is a fourth person, correct? Because wont they figure out the others salary when they subtract their random number from the total sum.
Wait, when person 1 is asked ot subtract their random number, if each salaray is Sa, Sb, Sb, and the random numbers are Ra, Rb, Rc, then the sum of all is Sa+Sb+Sb + Ra+Rb+Rc, so first person subtracts their random number, leaving Sa+Sb+Sc + (Rb+Rc) so he doensnt know Sb or Sc since they are obscured by Rb+Rc and are summed together anyway. B then pulls out Rb, C pulls out his own Rc, so aren't we are left with Sa+Sb+Sc?
@cdonthini:
first person real salary:20k
second person real salary:10k
third person real salary:5k
first person says his salary is: 20+3(random number) = 23
second person says his salary is: 10+7(random number) = 17
third person says his salary is: 5+4(random number) = 9
total sum = 23+17+9=49
Now anyone from 3 people ask the first person to subtract his random number=49-3=46 (at this point he knows only 46 and he doesn't know how 46 is divided among all of the three guys)
same is done for second person=46-7=39
same is done for third person=39-4=35
In the end 35/3 will give the result and no body know the exact salary of anyone else :)
Nice approach, I think this is the approach magicians use when they ask you to do mental calculations and in the end they tell you "your number is x" but before that "abra ka dabra".
So for instance, firstPerson says (100+3)103, secondPerson says (200+5)205 and the thirdPerson says (300+22)322. We add them up to become 630. Now, when we ask the first person to subtract his random number, he ll say 627. Because, he said 103 initially and now says 627, we can make out that his original salary was 100?
It cant be 50 because he originally said 103 and only subtracted 3 from the total. I m sorry. I do think I m missing something. Sounds like a very good solution.
This is one of the simplest problems in a field called Secure Multi-Party Computation. There's a whole research area around these sorts of algorithms where some group of untrusted parties, each having some portion of the input necessary for computing a function, compute the function without revealing their inputs to each other.
How about this:
Let the individuals be labeled as A, B, C. Let's suppose that we place them in a circular queue, each person subtracts some undisclosed portion from his salary and tells it to the next person in the ordering. Each individual receives this value and "adds" it to his own salary. Then we go through and add up the values, and divide by 3.
Have each engineer pick a random number and add that random number to their salary and then reveal that sum and add all 3 of these sums together. Now ask first engineer to subtract his random number from the sum, have second do the same, and then have the third do the same and divide by 3.
Let 3 engineers are A B C
Let A's salary is 15L
He told randomly 20 L
like wise B and C told Salary and sum is 50L
now A is subtracting 5L and now sum is 45 L
B and C both knows below two points:
---A told 20 L initially
---previous sum = 50 L and after A's correction it is 45 L
Is A's salary still hidden from B and C ????
In PKTs example, B does not know that the total sum the first time around is 50L .. only C and A know that. So. As salary is still hidden from B.
@eugene.yarovoi @whatevva' @PKT:
PKT is right in pointing out that A salary will not be hidden from B and C, if and only if we follow the dn's algorithm verbatim .Reason shown below:
Initial state:
A salary: 5, he told 5+5=10
50=A_sal+A_random+B_sal+B_random+C_sal+C_random
50=5+5+B_sal+B_random+C_sal+C_random
40=B_sal+B_random+C_sal+C_random ----- i
After he deducted his random number
45=A_sal + B_sal+B_random+C_sal+C_random
A_sal = 45-(B_sal+B_random+C_sal+C_random) ----ii
Using both (i) and (ii) B&C can easily find out A salary can't they?
So let's tweak this algorithm as below:
A should be told to tell his salary to only B
B should be told to tell his salary to only C
C should tell the sum to A.
A should now remove his random number and tell left out sum to only B.
B should now remove his random number and tell left out sum to only C.
C should just divide by 3 after removing his random number and announce
the average to everyone.
Dry Run:
A salary-5, Tells to B 5+1
B salary-10 Tells to C 10+2
C salary-15 Tells to A 15+3
So now A has the sum(6+12+18) and A removes his random no (6+12+18-1)
So now B has the sum(35) and B removes his random no (35-2)
So now C has the sum(33) and C removes his random no (33-3)=30
30/3=10 is average.
Here no one can deduce the actual salary of anyone :)
Have them pick "two" random numbers and reveal the sum of two random numbers and their salary, then sum them all up. Each developer now exchanges one of their random numbers. Now, when they subtract random numbers from the total, none of them can guess each other's salary.
Once the random numbers are subtracted, divide it by 3, which is the average salary of three developer.
Example:
Dev A: Salary 10, Random#: 3,4 => 10 + 3 + 4 = 17
Dev B: Salary 12, Random#: 6,1 => 12 + 6 + 1 = 19
Dev C: Salary 9, Random#: 9,8 => 9 + 9 + 8 = 26
Total : 17 + 19 + 26 = 62
DevA gave random# 4 to DevB.
DevB gave random# 1 to DevC.
DevC gave random# 8 to DevA.
DevA's Random #: 3,8
DevB's Random #: 6,4
DevC's Random #: 1,9
DevC subtracts his rand#.
62 - 1 - 9 = 52. ( sum of his original rand# 9 + 8 != 1 + 9 )
DevB subtracts
52 - 6 - 4 = 42 ( same )
DevA subtracts
42 - 3 - 8 = 31 ( same )
** so far, they can't figure out other's salary.
31 / 3 = 10.3333... => Average Salary
have each engineer express his salary as a sum of two numbers.
Sa = Sa0 + Sa1
Sb = Sb0 + Sb1
Sc = Sc0 + Sc1
A will provide Sa0 to B
B will provide Sa0+Sb0 to C
C will provide Sa0+Sb0+Sc0 to A
A will provide Sa0+Sb0+Sc0+Sa1 to B
B will provide Sa0+Sb0+Sc0+Sa1+Sb1 to C
and C calculates avg = (Sa0+Sb0+Sc0+Sa1+Sb1+Sc1)/3
When you work out what information each engineer has regarding the numbers, following is what I came up with:
Person A knows the following : { Sa0, Sa1, Sb0+Sc0 , Sb1+Sc1 }
Person B knows the following: { Sb0, Sb1, Sa0, Sa1+Sc0, Sc1 }
Person C knows the following: { SC0, Sc1, Sa0+Sb0, Sa1+Sb1 }
This information is not sufficient for any one person to figure out the other persons salary
Here's a simple solution. We start out assuming everyone's salary is in a certain range, say 0 - 1 trillion. The first person picks a number uniformly at random in that range and informs only the second person about this random number. Since this number is just random, it conveys no information. The second person adds their salary to the number and informs the third person about this sum. The third person receives no info from this because of the random element added in. The third person adds their salary to this running total and informs the first person about the sum. The first person knows the random number and subtracts it out, leaving the first person with the sum of the second and third person's salary. The first person could have obtained this info from the average anyway, so no extra information has been conveyed. Finally the first person adds their salary and divides by 3.
- eugene.yarovoi July 03, 2012