## Adobe Abs india pvt. ltd. Interview Question for Software Engineer / Developers Interns

Team: Lifecycle
Country: India

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

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

one comment only ............... awesome

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

That works fine if there's a fourth person trusted by everyone else. What if there's not?

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

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!

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

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.

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

So please let us know as well

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

The solution is really awesome

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

awesome!

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

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.

Comment hidden because of low score. Click to expand.
2
of 4 vote

This has been asked before: question?id=14184700

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

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

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

nice

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

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.

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

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?

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

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

@cdonthini: why it can't be 50?Why only 100?

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

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.

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

@cdonthini: just play this game with your friend and you will understand this problem.

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

@cdonthini: As long as the information is shared with only one person (instead of everyone). This solution should work.

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

the solution posted is just awesome.

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

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.

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

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.

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

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.

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

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 ????

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

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.

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

@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 :)

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

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

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

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

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.