logical interview question...
-
How stupid do *I* have to be to screw up this question. It's 9 balls not 8. ARGGHHH! With 8 balls it's trivial it falls right out. There's 9 :doh: You have a classic scale. You put known weights on one side to calculate the unknown weight of the other. = You have 9 balls all the same size. No visible characteristics make one appear larger or smaller but one of them weighs more. = What is the least number of measurements used to isolate the heaviest ball. {Sorry it's been 4 years since I last thought about this. Now I remember the question.} This can be done I got it in my interview at my last job before I went on my own. It was an 8 hour interview filled with crud like this. (I later learned that most people *do not* get this and the fact I *did* got me hired. LAME!!!) - Rex
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
Well, since you've told me that one ball is heavier than the others the difficulty of the problem is reduced by an order of magnitude. This becomes a simple binary search. The heavier ball can be found in a minimum maximum of log(8)=3 moves. (base 2 of course). 1 - Place 4 balls on each plate. The lower side contains the heavier ball. Toss the 4 balls from the light side. 2 - Place 2 balls on each plate. Once again toss the light side. 3 - Place 1 ball on each plate. The heavier side indicates the desired ball. Now, if you really want to make the problem difficult, consider 8 balls that are identical in every way except that one of the balls has a different weight. What is the least number of measurements to locate the different ball and is it heavier or lighter than the other balls. -Sean ---- Shag a Lizard
-
Well, since you've told me that one ball is heavier than the others the difficulty of the problem is reduced by an order of magnitude. This becomes a simple binary search. The heavier ball can be found in a minimum maximum of log(8)=3 moves. (base 2 of course). 1 - Place 4 balls on each plate. The lower side contains the heavier ball. Toss the 4 balls from the light side. 2 - Place 2 balls on each plate. Once again toss the light side. 3 - Place 1 ball on each plate. The heavier side indicates the desired ball. Now, if you really want to make the problem difficult, consider 8 balls that are identical in every way except that one of the balls has a different weight. What is the least number of measurements to locate the different ball and is it heavier or lighter than the other balls. -Sean ---- Shag a Lizard
Can solve in 2 moves (the first problem). 1 - Place 3 balls in each side. If both sides have the same weight: 2- Test the 2 remaining balls. Else 2- Test 2 of the 3 balls in the heaviest side. If they have same weight the heaviest is the one left out, else ... Rui A. Rebelo De perto, ninguém é normal. (At a close look, no one is normal) C. Veloso
-
Can solve in 2 moves (the first problem). 1 - Place 3 balls in each side. If both sides have the same weight: 2- Test the 2 remaining balls. Else 2- Test 2 of the 3 balls in the heaviest side. If they have same weight the heaviest is the one left out, else ... Rui A. Rebelo De perto, ninguém é normal. (At a close look, no one is normal) C. Veloso
oops, what I meant to say was it would take a maximum of 3 moves. Yeah, that's it. :doh: -Sean ---- Shag a Lizard
-
How stupid do *I* have to be to screw up this question. It's 9 balls not 8. ARGGHHH! With 8 balls it's trivial it falls right out. There's 9 :doh: You have a classic scale. You put known weights on one side to calculate the unknown weight of the other. = You have 9 balls all the same size. No visible characteristics make one appear larger or smaller but one of them weighs more. = What is the least number of measurements used to isolate the heaviest ball. {Sorry it's been 4 years since I last thought about this. Now I remember the question.} This can be done I got it in my interview at my last job before I went on my own. It was an 8 hour interview filled with crud like this. (I later learned that most people *do not* get this and the fact I *did* got me hired. LAME!!!) - Rex
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
2 steps
Pandoras Gift #44: Hope. The one that keeps you on suffering.
aber.. "Wie gesagt, der Scheiss is' Therapie"
boost your code || Fold With Us! || sighist | doxygen -
Well, since you've told me that one ball is heavier than the others the difficulty of the problem is reduced by an order of magnitude. This becomes a simple binary search. The heavier ball can be found in a minimum maximum of log(8)=3 moves. (base 2 of course). 1 - Place 4 balls on each plate. The lower side contains the heavier ball. Toss the 4 balls from the light side. 2 - Place 2 balls on each plate. Once again toss the light side. 3 - Place 1 ball on each plate. The heavier side indicates the desired ball. Now, if you really want to make the problem difficult, consider 8 balls that are identical in every way except that one of the balls has a different weight. What is the least number of measurements to locate the different ball and is it heavier or lighter than the other balls. -Sean ---- Shag a Lizard
I'm a moron. I told you 8 now that I sit and think about it it's 9. While this does not make me an idiot it sure comes close to proving it. :doh:
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
-
oops, what I meant to say was it would take a maximum of 3 moves. Yeah, that's it. :doh: -Sean ---- Shag a Lizard
I'm a moron. I told you 8 now that I sit and think about it it's 9. While this does not make me an idiot it sure comes close to proving it. :doh:
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
-
2 steps
Pandoras Gift #44: Hope. The one that keeps you on suffering.
aber.. "Wie gesagt, der Scheiss is' Therapie"
boost your code || Fold With Us! || sighist | doxygenI'm a moron. I told you 8 now that I sit and think about it it's 9. While this does not make me an idiot it sure comes close to proving it. :doh:
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
-
Chris Maunder wrote: but what if the coffee was a latte? Never buy a latte from someone you don't trust. :-D _________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
Jeffry J. Brickley wrote: but what if the coffee was a latte? Don't know why but this reminds me of... "In God We Trust, all others must have good credit." {Sign seen at car dealer ship.}
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
-
I'm a moron. I told you 8 now that I sit and think about it it's 9. While this does not make me an idiot it sure comes close to proving it. :doh:
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
You still can solve in 2 moves. 1- Place 3 in each side. 2- If they are in equilibrium test 2 of the remainder group. If not test 2 of the heaviest group. In second test if they remain in equilibrium the non-tested ball is the heaviest; else... But Sean's analysis is very valid: it's still log(9) but the base is 3, since there are 3 states (heaviest left, equilibrium and heaviest right). Rui A. Rebelo De perto, ninguém é normal. (At a close look, no one is normal) C. Veloso
-
You still can solve in 2 moves. 1- Place 3 in each side. 2- If they are in equilibrium test 2 of the remainder group. If not test 2 of the heaviest group. In second test if they remain in equilibrium the non-tested ball is the heaviest; else... But Sean's analysis is very valid: it's still log(9) but the base is 3, since there are 3 states (heaviest left, equilibrium and heaviest right). Rui A. Rebelo De perto, ninguém é normal. (At a close look, no one is normal) C. Veloso
Yes. Despite my best efforts to screw up everything and confound the problem. You got it right. Log() is an amazingly powerful tool.
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
-
but what if the coffee was a latte? cheers, Chris Maunder
Chris Maunder wrote: but what if the coffee was a latte? That would be Soy, wouldn't it? Michael Martin Australia "I controlled my laughter and simple said "No,I am very busy,so I can't write any code for you". The moment they heard this all the smiling face turned into a sad looking face and one of them farted. So i had to leave the place as soon as possible." - Mr.Prakash 24/04/2004
-
a waitress brings a man a cup of coffee with a match in it ... the man sees that and asks for another cup ... the waitress goes back and brings another cup of coffee ... how does the man know if its not the same cup of coffee? http://www.boreddude.com
The man kept the old cup (according to the description, the waitress did not take the old cup away from him) ------- sig starts "I've heard some drivers saying, 'We're going too fast here...'. If you're not here to race, go the hell home - don't come here and grumble about going too fast. Why don't you tie a kerosene rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt "...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001
-
I'm a moron. I told you 8 now that I sit and think about it it's 9. While this does not make me an idiot it sure comes close to proving it. :doh:
I know you can't become if you only say what you would have done and you'll miss a million miles of fun." - Len Work hard, play hard. Don't forget who you are and don't forget where you're from. Do all these things well and you won't have to wonder where you are going.
Same solution: (1) three balls on the left, three balls on the right. You know have a set of three balls containing the heavier one (either the side that goes down, or the three that you left aside) (2) from these three, put one left, one right. Again, it's the one going down, or the one left aside if the two on the scale are equal :cool:
Pandoras Gift #44: Hope. The one that keeps you on suffering.
aber.. "Wie gesagt, der Scheiss is' Therapie"
boost your code || Fold With Us! || sighist | doxygen
