Goldman Sachs Interview Question Software Engineer / Developers
Let us suppose that A, B, C and D each have 2000 Salary and A, B, C, D choose random number 1,2,3 and 4 respectively.
so A=4+2000-1
B=1+2000-2
C=2+2000-3
D=3+2000-4
So, add A+B+C+D/4=2000 average Salary
when every one has same salary then for whom you are calculating average....it is understood tat it will be 2000 and nothing else.
A will tell random number to B. B add his/her salary into that number and tell C. C will add his/her salary and tell D. Now D add his/her salary and tell the total. Now A will add his salaty and minus his uttered random number. So we get total salary of 4 employee. Now for avg divide by 4.
Another solution:
Everyone generate a random num for self, and report this number plus salary.
Manager adds them up, so the sum is sum of random + salary.
Everyone iteratively reduce the sum with their own random number without telling others.
The result will be the sum of salary. Average can be found by dividing head count.
According to qus "How can four employees calculate..."
no manager is avl... even though any one of four is manager he/she can watch who is adding or subtracting how much money...!
for ex A told his sal=60,000
total= 2,00,000
now after updating total by A....
total =1,95,000
its clear A's sal is 55,000
I think having so many random mnbrs is not necessary.
1. Let person A think of a random number, add his salary to it & whisper to B.
2. B adds his own salary to the total & whisper to C.
3. C adds his own salary to the total & whisper to D.
4. D adds his own salary to the total & whisper to A.
A subtracts the random number chosen in step 1, to get the total of all four.
:-) wat say?
alternative soln
1. A adds a random to his salary and tell everyone
2. B adds his random and salary to prev total
3. C adds his random and salary to prev total
4. D adds his random and salary to prev total
5. A subtracts his random from total and tell everyone
6. similarly B, C & D subtract their random in the order. Remaining total / 4 is the answer.
Does not rely on keeping anything secret to anyone.. should work with strangers too.
Then the salary may not be secret. Say initially every body knows what A says for his salary+Random value. At the step 5 when A subtract from total, everybody will know how much he subtracted. The same number they can subtract from what A said at step 1 and hence they will know A's salary. Same way for others...
A will tell random number to B. B add his/her salary into that number and tell C. C will add his/her salary and tell D. Now D add his/her salary and tell the total. Now A will add his salaty and minus his uttered random number. So we get total salary of 4 employee. Now for avg divide by 4.
A will tell random number to B. B add his/her salary into that number and tell C. C will add his/her salary and tell D. Now D add his/her salary and tell the total. Now A will add his salaty and minus his uttered random number. So we get total salary of 4 employee. Now for avg divide by 4.
Salary of A: x
Salary of B: y
Salary of C: z
Salary of D: u
A passes to B (x + a) where a is a number that A knows
B takes this a passes to C (x + y + a + b)
C takes this and passes to D (x + y + z + a + b + c)
D takes this and passes to A (x + y + z + u + a + b + c + d)
Now one after another they strip their constants. Ex: A now passes to B: x + y + z + u + b + c + d (She has stripped of A) and B passes to C after stripping of her constant (b).
Thus Finally D gets x + y + z + u + d. She takes away her constant and now she has x + y + z + u.
So she can publish the average (x + y + z + u) /4.
Lets name these employees A, B, C and D
- Nickolay Mazurkin February 25, 20111. A chooses any random value and whispers it to B privately
2. B chooses any random value and whispers it to C privately
3. C chooses any random value and whispers it to D privately
4. D chooses any random value and whispers to to A privately
So each employee has two numbers now - incoming and outgoing. Each employee should get own salary, then add the incoming and subtract the outgoing and report the result. Then they should add all reports and divide by 4.