Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,225 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Jan 6, 2012
Out of 10 coins, one weighs less then the others. You have a scale. How can you determine which one weighs less in 3 weighs? Now how would you do it if you didn't know if the odd coin weighs less or more?
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (2)
3 of 3 people found this helpful
Jan 12, 2012
Weight 3 vs 3, set 4 aside.
if there's balance you're left with 4 -> weigh 2 vs 2 -> if there's balance weigh 1 vs 1.
If there's no balance weigh 1 vs 1 from the lighter side. if there's balance choose the 1 left, else choose lighter.
Best case 2 weighs, worst case 3 weighs.
As for doing it without knowing if it's lighter or heavier:
break 10 to 3,3',3'',1
function weigh(grp1, grp2) {
if grp1 is heavier return -1
if grp1 == grp2 return 0
else return 1
}
res1 = weigh(3,3')
res2 = weigh(3,3'')
if (res1 == 0 && res2 == 0) choose the '1'
if (res1 == -1 && res2 == -1) newGrp = 3, odd coin is heavier
if (res1 == 1 && res2 == 1) newGrp = 3, odd coin is lighter
if (res1 == 0 && res2 == -1) newGrp = 3'', odd coin is lighter
if (res1 == 0 && res2 == 1) newGrp = 3'', odd coin is heavier
if (res1 == 1 && res2 == 0) newGrp = 3', odd coin is heavier
if (res1 == 1 && res2 == -1) Not possible (3 lighter than 3' and heavier than 3'')
if (res1 == -1 && res2 == 0) newGrp = 3', odd coin is lighter
if (res1 == -1 && res2 == 1) Not possible (3 heavier than 3' and lighter than 3'')
newGrp is 3 coins and you know if the odd coin is heavier or lighter.
Viola!
if there's balance you're left with 4 -> weigh 2 vs 2 -> if there's balance weigh 1 vs 1.
If there's no balance weigh 1 vs 1 from the lighter side. if there's balance choose the 1 left, else choose lighter.
Best case 2 weighs, worst case 3 weighs.
As for doing it without knowing if it's lighter or heavier:
break 10 to 3,3',3'',1
function weigh(grp1, grp2) {
if grp1 is heavier return -1
if grp1 == grp2 return 0
else return 1
}
res1 = weigh(3,3')
res2 = weigh(3,3'')
if (res1 == 0 && res2 == 0) choose the '1'
if (res1 == -1 && res2 == -1) newGrp = 3, odd coin is heavier
if (res1 == 1 && res2 == 1) newGrp = 3, odd coin is lighter
if (res1 == 0 && res2 == -1) newGrp = 3'', odd coin is lighter
if (res1 == 0 && res2 == 1) newGrp = 3'', odd coin is heavier
if (res1 == 1 && res2 == 0) newGrp = 3', odd coin is heavier
if (res1 == 1 && res2 == -1) Not possible (3 lighter than 3' and heavier than 3'')
if (res1 == -1 && res2 == 0) newGrp = 3', odd coin is lighter
if (res1 == -1 && res2 == 1) Not possible (3 heavier than 3' and lighter than 3'')
newGrp is 3 coins and you know if the odd coin is heavier or lighter.
Viola!
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
2 of 4 people found this helpful
by Ahmed Al-Shinhab:
Now you have only 5 coins.
Second Trial: Hold one coin in your hand and put 2 coins at each side of the scale. If the two sides weighs the same, then the lighter one is the one you are holding in your hand (FINISHED).
If one side is heavier than the other, exclude the two coins in that side. Now you have only 2 coins and a scale to find out which is the lighter by using the scale for a third time :)