20bits: Interview Questions: Two Bowling Balls | 20bits
ken vh
· 1 year ago
I couldnt help myself and went ahead and found the optimal strategy under the (not unreasonable) assumption of uniform distribution. The 14 strategy outlined above is the best worst case, but it will always take 14 tries. The following sequence of skips has the optimal expected tries of around 12.84--not much of an improvement--with worst case 19:
10, 9, 9, 8 ,8 ... 3, 3, 2, 2, 1, 1
Jesse Farmer
· 11 months ago
Yeah, the idea is that the person placing the light bulb is actively working against you and knows your strategy beforehand.
Can you share the math that gave you those numbers? I'd be interested in taking a look.
RAR RAR FIGHT THA POWA
· 11 months ago
awwwww... butthurt?
maxvinland
· 11 months ago
Why would he be? According to the parameters set out by the interviewer his solution is still 5 tries better.
Don't make a mean comment if you don't know what's going on.
Andrew
· 11 months ago
The problem gets more interesting if you have 3 balls, 4 balls, etc. I believe
for 3 balls, n = 100, the first floor should be 36. 8 * 9 / 2!, max 8 tries for 4 balls, n = 100, the first floor should be 56. 6 * 7 * 8 / 3! max 6 tries for 5 balls, n = 100, the first floor should be 70. 5 * 6 * 7 * 8 / 4! max 5 tries
Chris L.
· 11 months ago
Those are some intelligent, logical solutions you've provided. Kudos on your cleverness and ability to figure that out on the spot in an interview setting.
I probably would have turned the question around on the interviewer and asked how resilient the bowling ball needed to be? Did it need to survive 10 floors? 15? Why were we doing the resiliency test in the first place? Developers who take the requirements at face value without understanding the motivation aren't nearly as valuable as the ones who can see past what is being asked for and find a simpler solution that delivers the underlying need.
If it turned out we just needed it to survive falling from 15 stories, I would have dropped one ball from the 15th floor window and if it survived it passed our test otherwise it didn't. One step, and we save a ball.
Jon Shea
· 11 months ago
I like the variation where there’s no elevator. How does it change if you have to walk up the stairs each time you drop the ball, and you want to minimize the total number of flights of stairs you have to climb up? What if you can only carry one ball at a time? What if you can carry both balls at the same time?
X
· 11 months ago
These kind of interview questions are retarded
Jesse Farmer
· 11 months ago
I don't think that word means what you think it means.
Word Nazi
· 11 months ago
I don't think that you don't think you know what he was saying, and at mutual understanding that word means what he thinks it means.
One "Special" Guy
· 11 months ago
nope.. I pretty much agree. This problem is retarded.
Put the ball it in a vise where you can measure the force when the ball breaks. Calculate the velocity required to reach that force and subsequent height needed. Then A) go bowling or B) sell the second one on ebay.
So this is a legitimate answer. You (as interviewer) say we should take the problem at face value and devise an algorithm to solve it. Me: Ok that's cool. I then tell you the problem isn't really solvable then because the bowling ball will accumulate damage as we test it (as others have pointed out). Me: OK (rolls eyes internally) I solve problem again this time assuming changing floors and retrieving the ball is very time consuming (I don't know... like a database call, or a disk read... that doesn't have anything to do with computers either I guess). You again tell me I'm "wrong" because I didn't guess how you wanted me to solve this. (At this point I don't want your f'ing job anyway but decide to trudge through this retardation anyway (that's right because this interview is actually killing brain cells and making me think slower)) Alright now I go through the process you've gone through, get the "right" answer, and try to get the hell out of your office before the stink of failure rubs off on my clothes. The interviewer is annoyed it took me so long and I'm pissed off that I've wasted half of my day with your crappy company.
Jesse Farmer
· 11 months ago
You sound pretty anti-social.
One "Special" Guy
· 11 months ago
I don't think that word means what you think it means.
What if your ball breaks while you're testing? If you have no replacements, then you can only skip one floor at a time, for a worst case of 51 ball drops. If have a big supply of spares, then I must be missing something. Why not just do a binary search? If you're only measuring the number of dropped balls, it's O(log2(N)). For N=100, you only need 7 ball drops.
Jesse Farmer
· 11 months ago
That's the whole point of the problem, really. You have two bowling balls. Some tests might cause them to break.
How do you find the first floor where they do break?
enkidu
· 11 months ago
OK, I didn't read it through. I agree with the analysis. Is there anyway to delete my comment?
socrates
· 11 months ago
You don't consider the timing factor. It takes (much) more time to climb to higher floors. And, more time to drop (not so much).
You say: "You're graded on your algorithm's worst-case running time. ", but you're optimizing on # of tries, which does not = time unless you account for actual time, not just # of tries.
Jesse Farmer
· 11 months ago
There's a version with stairs, where the time to climb is taken into account, and there's a version with an elevator or other "cost-free" form of transportation. This one is the latter, and it's the one the interviewer was asking about.
Jordan
· 11 months ago
The problem is that if you drop the ball and it doesn't break then you have a damaged ball. You're measuring resilience based on accumulated damage not resilience based on a fresh ball.
If you can drop the ball without it being damaged then it will never break.
It's an inherently flawed question if they require you to use only two balls. Ideally you'd need a fresh ball for each drop.
Jesse Farmer
· 11 months ago
It's a math problem disguised as a story. The story doesn't need to be literal if you can still understand it.
Maybe the bowling balls are coated in a self-repairing layer of nanites, which stop working if the ball shatters.
gwenhwyfaer
· 11 months ago
Nonetheless, it's probably worth mentioning as a real-world constraint that can stymie even the best of theoretical solutions. We all know how often that happens, after all. :)
utsuprainfra
· 11 months ago
I guess you're right, but it would be a very strong answer to point out Jordan's point, as well as the manufacturer's information, etc., before going into your math logic.
Leo
· 11 months ago
Why not try some kind of binary-search-like algorithm? For example, say the true value at which it would first begin to break is floor 61. Test length/2, which is 50. Does it break? No, so reject all floors below 50. Test 75; breaks, reject > 75. Test 63; breaks, reject > 63. Test 57; no break, reject < 57. Test 60; no break, reject < 60. Test 62; breaks, reject > 62. Test 61; if it breaks, you have the true value, else it is 62. That's 7 tests. If the true value is 100, it takes 6 steps (I think). Did I read the problem wrong?
Leo
· 11 months ago
public static void main(String[] args) { int length = 100; for (int i = 0; i < length; i++) { int realValue = i;
boolean[] floors = new boolean[length]; for (int n = 0; n < realValue; n++) { floors[n] = false; } for (int n = realValue; n < length; n++) { floors[n] = true; }
int tests = 0; int start = 0; int end = length; int testPoint = 0; while (end - start > 1) { testPoint = (end - start) / 2 + start; if (floors[testPoint]) { end = testPoint; } else { start = testPoint; testPoint = end; } tests++; }
IF it does break at 50, you're screwed. Worst case is like 49.
Leo
· 11 months ago
With the true value at 50 it turns out to be 7 tests, which is the worst case. 6 tests is the best case =). At least, that's with the code above. I'm not sure if there's some subtlety with starting the floors and true value at 0 or 1 or what.
Mike
· 11 months ago
If you had log2n bowling balls, binary search would be optimal. But if one breaks at 50, then the other one breaks at 25, you haven't found where it breaks, other than "less than 25".
Leo
· 11 months ago
Yep. Guess I should have read the problem description more carefully =)
Azn
· 11 months ago
You tell the interviewer that a mathematical solution isn't always required, and for the first preliminary round you use your gut feeling to pick an approximate floor and throw it out the window. If it breaks, whoopie, the ball isn't as tough as you think, and if it doesn't, its tougher than you think. Either way, you got a ballpark based on your gut feeling.
In real life, a bowling ball will NOT survive a 100 floor drop. It just isn't possible. So you can discount the 100th floor. 99th? Discount it too. Repeat until you feel that the bowling ball is likely to survive. There is no point testing at any floor above that if you're sure the results aren't what you're looking for.
This question is akin to asking an undergraduate engineer what voltage a resistor will take, and then in demonstration, a far lower voltage would have burnt out the resistor already. Mathematics is fun, but in engineering, real life is what matters.
Alex S
· 11 months ago
Is't there a case where it takes 15 tries?
In the strategy above we're dropping the first ball from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95. Suppose it does not break on any.
After that there are 5 unexplored floors left, 96,97,98,99,100. We've used up 10 tries already, which means that worst case it will take 15 to find the remaining one.
Alex S
· 11 months ago
Oh wait, 99, doh.
IConrad
· 11 months ago
This is, of course, on Reddit. A gentleman there (not me) had the conniving idea of getting a lower bound not by trial but by additional data request: ask the manufacturer what the physical standards are for the ball.
Your algorithm is numerically sound, but that //would// be a "cheating" way to get the job done that would be more highly optimized.
Is it a hack? Sure. But it's a 'legitimate' hack -- and might have represented a similar way of thinking to the "get the cup without walking on the carpet" problem.
utsuprainfra
· 11 months ago
I would have hired you. Why do you think they didn't?
DUMB ASS - if you are hiring me to do things with bowling balls I am definitely in the wrong building ... I thought you wanted a programmer...here let me show you what you can do with 2 bowling balls...oh btw when i throw you off the freaking building at what point will you realize YOU ARE A DUMB ASS - you and all the DUMBASSES who read REDdit and think you are not DUMBASSES - well - YOU ARE
Jesse Farmer
· 11 months ago
You realize this is a question someone asked me, right? Not one that I've asked someone else.
Even so, I like it more than most silly puzzle questions because there's a clear naive solution and a steady progression of solutions from poor to best.
Paul
· 11 months ago
My solution is to start at the tenth floor and drop a ball at each floor, increasing by ten. If the ball break, go back 9 floors and go up by one. That gives you O(2 * log10(n)). It's not the best for efficiency, but it is simple enough to explain to someone who doesn't have a college education, which makes it very desirable. Loops as follows:
i = 0 while( i < log10(n) and testFloor( (i + 1) * log10(n) ) { i = i + 1 } j = ( i * log10(n) ) + 1 while( j < i and testFloor(j) ) { j = j + 1 } return j * i
The pattern, I'm sure, can be improved. I was just exploiting that it is guaranteed to be within a 2 digit number. So one ball to figure out each digit.
Ron Stewart
· 11 months ago
RTFM - If you want to code for the rest of your life give the answers above. If you want to be the one managing coders then ask them to read the bowling ball manual !
npboards
· 11 months ago
Who would work at a place that asked such a ridiculous interview question?
Jesse Farmer
· 11 months ago
About 500 people, last count. It was Facebook.
skitzo
· 11 months ago
I don't know if I want to take interview advice from a guy who didn't get the job.
Jesse Farmer
· 11 months ago
*shrug*
Yishan
· 11 months ago
Oh, that was at Facebook. We [used to] ask that question, and have teams of 4 interviewers, but didn't hire you. Let me know if you want to take another shot, though it looks like you're doing pretty well with Adnomics.
Jesse Farmer
· 11 months ago
Hey Yishan,
Thanks for the offer. A year and a half ago I might have taken you up on that, but Facebook has changed too much and so have I.
I only blame myself, although in retrospect I'm glad I didn't get it.
Scott
· 11 months ago
When thinking about how to improve upon this method for testing bowling balls, it seems more efficient to carry two balls up with you for each state of the testing, dropping one after the other on different floors, to save on the trip down. After all, pitching one out the 10th floor and one out the 20th requires only twenty floors of travel, not thirty transporting them individually.
Meneer R
· 11 months ago
You failed.
You were being judged on the WORST CASE. If you choose to use 2 balls, the worst case is 100 throws plus one (the extra ball you had to throw from floor 100) If you choose to use just one ball, the worst case is 100 throws.
There, solved it for ya.
And because you went all complex on this trivial logic excersize is likely why you didn't get the job.
Meneer R
· 11 months ago
Let me rephrase that: you and others here did not solve the original problem.
You went looking for an optimal solution, if you would solve this problem a 100 times, with the balls breaking on a different floor each time. You clearly state in the beginning that you were suppose to solve the problem of the WORST CASE. Which is just (n); using one ball.
You never told the interviewer that. You went on to solve a different problem. The one you were not asked to solve.
Kapow
· 11 months ago
"You're graded on your algorithm's worst-case running time."
Your algorithm's worst-case is 100. His last algorithm's worst-case is 14. A shorter running time is better, of course.
You have the worst possible worst-case running time. Not only did you fail, you failed as hard as you possibly could.
Meneer R
· 11 months ago
Correction: If you choose to use 2 balls, the worst case is 100 throws
You can, with two balls, have the same optimum solution as with one ball, off course. Just keep switching them ;-)
Jesse Farmer
· 11 months ago
Meneer,
If you read the post, the naive solution of using one ball and going one floor at a time is the first one given. The interviewer was happy with the solution.
Mat
· 11 months ago
Ummm... I don't understand a lot of above BUT, BUT, BUT.... surely you don't need to include any floors above that which throwing the ball from would allow it to achieve achieve terminal velocity...
Mobile360
· 11 months ago
I don't understand what it means, therefore I am confused by this!
rdoggett
· 11 months ago
I give up. I've a neat little program, but every time I try to post, it comes out a huge pile of garbage. I can't even figure out how to delete the garbage posts, but fortunately they don't seem to show up here. This problem stumped me in a Google interview. It's fun and easy to write a program that solves it recursively. If I can figure out how to post successfully, I'll publish my code.
John Whipple
· 11 months ago
I enjoyed reading this and am very impressed with how you came to the conclusion. Makes me wish I could do that kind of math. Because it was an engineering job interview is it assumed that the context is not real world? Funny how engineers love to phrase things in real world terms to give it a facade of real world. If this were a real world situation I don't think you could conduct the test and get accurate results with two balls. Each time a ball is dropped it is weaken and is not the ball it was before that drop. A ball receiving it's first drop from any floor would be less likely to break than a ball which had already suffered several violent impacts. A ball dropped twice from any floor might break on the second drop, the damage is cumulative. I mean this in a friendly, humorous way; I would worry about the common sense of the interviewer and of any interviewee who didn't blurt that out right away. The two ball limitation is specified in the question but whatever number of drops you come up with you would have to have that many identical test balls.
codist
· 11 months ago
That's a math question not a programming question. It's not relevant at all, but people love giving them anyway. Has anyone ever quantitatively proven that asking math questions to programmers leads to hiring the best programmer?
Biff Tardisblue
· 11 months ago
If you only have two balls, probability will prevent you from completing any of these prosposed solutions, as both balls will be destroyed before the answer is found.
Jesse Farmer
· 11 months ago
Not true. You are guaranteed to find a solution by going one floor at a time with one ball. But can you do better?
Biff Tardisblue
· 11 months ago
Yer so clever! you get 4 gold stars today. It's interesting to see all the erroneous assumptions posited here. I give, what's the answer?
Jesse Farmer
· 11 months ago
I outline the steps in the article.
Rick Spencer
· 11 months ago
Obviously the point of the question is to get a sense of the prospect's mathematical reasoning ability. That said, before working out algorithms, I'd expect a pragmatic programmer to ask things like:
1. Can't he manufacturer just tell us, so we can store the value and retrieve it as needed? 2. Can we copy the bowling balls, and then use an existing binary search function? 3. Has anyone else done this? Is there a library that we can use? 4. Etc ...
In other words, how can we avoid having to solve the problem ourselves if we don't have to?
Cheers, Rick
Jarrod
· 11 months ago
Excellent article, very thought-provoking.
I cannot help but wonder if, by presenting the article in story format (and not as a purely abstract mathematical problem), the interviewer was inviting you to consider real-world implications such as the damage done to each ball when dropped, terminal velocity, etc. Especially if the job was for a programmer, who'd be familiar and comfortable with more abstract problems.
As one previous comment suggested, sometimes it's more difficult to find a programmer who understands the business rules than it is to find someone who can devise an efficient, mathematically sound algorithm. I've seen programmers spend hours and wrack their brains coming up with elegant, sophisticated "solutions" that overlook simple, common-sense factors. No offense intended, but programmers, IT specialists, and INTP-types are sometimes guilty of dwelling on theory at the expense of practice...
Jesse Farmer
· 11 months ago
Jarrod,
No, that wasn't the reason. If anything it was the opposite. The rest of my interview didn't inspire enough technical confidence, and I spent my time asking questions about their business. Read here for the details: http://20bits.com/articles/when-its-your-turn/
The reason I received for not getting an offer was that I, quote, "didn't have a strong enough technical background."
Ali Pang
· 11 months ago
I don't see why you have the equality C + (C-1) + ... + 1 > N strict here. Dropping a ball at a level C gives you an inclusive upper bound in the resilience-height of the ball.
Secondly: You ponder the existence of a better solution. Would you not be able to easily prove this is optimal? This is worst-case analysis so we can take on the role of the adversary when considering alternative algorithms.
Clearly there exists a smallest integer C s.t. C is the lowest possible number of tries you have to make.
Claim: Dropping the ball on height C in the first step is optimal. Proof: If an alternative algorithm chooses to drop it lower, we just place the actual place the ball breaks higher. Then in the next step the alternative would have to solve something >at least< as hard. If an alternative algorithm chooses to drop it higher, then just place the ball in the last spot the algorithm would look with the remaining ball. (Remember we can be psychics when placing the ball here.) This would result in a >worse< number of tries.
Repeating this argument in each step proves that your strategy is optimal.
Alcari
· 11 months ago
You missed something potentially usefull. Setting the upper limit where you can stop testing.
Step 1 -- Calculate terminal velocity, using size and weight (for example, say thanks to wikipedia, example uses maximum weight), guesstimating drag coefficient at .47 for a smooth sphere.
-1/2 (rho) * v^2 * A * Cd = m * g -1/2 1.3 * v^2 * pi*(0.108)^2 * 0.47 = 7.2 * 9.81 0.0112 * v^2 = 70.6 v ~ 79.40 m/s
Step 2 -- Determine fall distance at which terminal velocity is achieved 79.4 m/s is reached after 79.4 / 9.8 = 8.1 seconds
d = 1/2 * g * t^2 d = 1/2 * 9.8 * 8.1^2 d = 321.65 meters
So, depending on the dimensions of the building (and of course, the weight of the bowling ball), you can skip the top few floors. If it's a children's ball (weight 6 pounds or 2.72 kg), the max required test height is only 121 meters, or roughly 40 floors. Depending on your ball, a little physics will do wonders for the number of tests.
With a light ball, even your Method 1 will solve the problem in 10 steps, if only you used some physics first. You can do even better by calculating at which height the ball will break. That way, assuming you have reasonably accurate figures, you can do it in 3 or 4 tests.
Lee
· 11 months ago
You were on the right track at the start of "Solution 2". The solution to this problem is obviously an application of the binsearch or binary search algorithim. You divide each remaining half of the floors and seach in the middle of the remaining segment of floors. As an example, if the ball breaks at the 50th floor, you go to the 25th floor for the next trial. If it doesn't break, you go to the 75th floor. The worst-case solution is seven bowling ball drops.
Jesse Farmer
· 11 months ago
Lee,
That's not true. What happens if the bad floor is the 10th floor? Once the ball breaks on the 25th floor you're done.
Jim Dunlop
· 11 months ago
I'm not an engineer or a mathematician, but I am a logical sort of person with some kind of college science degree -- I've forgotten what it's in because I've never worked in the industry.
Anyway, that aside, the problem is fundamentally flawed and I'd refuse to answer the question on those grounds (and obviously not get the job). At any rate, I like to think out of the box, so here's some out-of-the box considerations for this problem.
The problem must first be re-defined to make it into a legitimate problem. Why? Any time you drop the bowling ball from any floor, you are subjecting it to forces that have the potential of breaking the ball. Now, even though a single drop from, say, the 10th floor may not break the ball, it may cause certain internal stress on the ball (or micro-fractures) that are not visible to the naked eye, which will cause the ball to break on the next drop above 10 (let's say 14 for the sake of argument). Thus, if you took a brand new, never-been-dropped ball and let it go from 14, not having suffered previous trauma, may stay intact, thus skewing your results.
In order for this problem to become valid, you go over to company stores, and social-engineer them into requisitioning a box of bowling balls to be FedExed to you. Then you can start with a baseline of 50 floors, examine the results, and whether the ball breaks or not, add or subtract floors accordingly, but ensuring to drop a fresh ball each time. If you were to multiply or divide by a factor of 2 (or so): 50; (25 is not further divisible by 2 so let's just go ahead and descend one more floor)... 24; 12; 6; 3; 2; 1, your worst case scenario would look like this: (B=break; I=intact). 50(B); 24(I); 36(B); 30(I); 33(B); 32(B); 31(B).
If, however you are an unlucky bugger and the breaking point just happens to be 49, you might get this:
50(B); 24(I); 36(I); 43(I); 46(I); 48(I); 49(B).
Either way, the answer will be 7.
Thus, make sure your purchasing department orders 25 bowling balls. That way you can run the experiment 3 times for consistency and to get accurate numbers. This will use 21 of the 25 balls. Then, you can take the remaining 4 balls, one for yourself, and 3 for the guys down in purchasing so you can take them out bowling as a "thank you" when all the BS is done!
Hotball
· 11 months ago
This problem is recursive in nature. Basically, if you drop a ball at floor k, and it breaks, then you reduce the problem to one less ball with floor k -1. On the other hand, if it does not break, the problem becomes the same number of balls but with floor n - k.
So, basically this problem can be solved with dynamic programming, by optimizing this:
F(m, n) = 1 + max(F(m-1, k-1), F(m, n-k)) for k = 1.. n
Running this on F(2, 100) can show that 14 is indeed the optimal solution. This should be able to changed to optimize for the average case, not the worst case.
What's interesting is that (if my program is correct) it only takes 5 balls to achieve 7 steps (which is the best possible number of steps, since 2^6 < 100 and 2^7 > 100).
bob
· 11 months ago
anyone take into account the acceleration of the ball.
The speed of the ball is the key to when it breaks, and it goes as sqrt(h). So one should take that into account when sampling (i.e. sample not every S floors, but make it a uniform stride in impact velocity).
from a physics point of view, questions are not asked to see the result, but how one thinks about things. Including discussions of important factors like:
climbing up stairs, terminal velocity, the quick solution, the optimal solution, accumulated wear on the ball, insuring zero initial velocity, using non-integer floors by allowing a small initial downward velocity, or tossing the ball up halfway between floors, repeatability of the experiment, are the balls identical, why aren't the windows locked, measuring the temperature while doing the experiment, effect of Coriolis force on the ball, etc
sarafoster
· 7 months ago
ohh Math .. I think its so much puzzling Question
David B
· 7 months ago
Well, the biggest problem I have with the entire problem is that you're missing a very pressing point. You only have two balls. If you drop even one ball one floor, you're fracturing the structure of the ball, and as such, weakening it. My biggest concern wouldn't be how many tries it takes, but to test the resilience of the ball and find the maximum height at which you could drop it and have it still maintain its integrity, then convert that to 'floors high' - Great question though!
All Comments
10, 9, 9, 8 ,8 ... 3, 3, 2, 2, 1, 1
Can you share the math that gave you those numbers? I'd be interested in taking a look.
Don't make a mean comment if you don't know what's going on.
for 3 balls, n = 100, the first floor should be 36. 8 * 9 / 2!, max 8 tries
for 4 balls, n = 100, the first floor should be 56. 6 * 7 * 8 / 3! max 6 tries
for 5 balls, n = 100, the first floor should be 70. 5 * 6 * 7 * 8 / 4! max 5 tries
I probably would have turned the question around on the interviewer and asked how resilient the bowling ball needed to be? Did it need to survive 10 floors? 15? Why were we doing the resiliency test in the first place? Developers who take the requirements at face value without understanding the motivation aren't nearly as valuable as the ones who can see past what is being asked for and find a simpler solution that delivers the underlying need.
If it turned out we just needed it to survive falling from 15 stories, I would have dropped one ball from the 15th floor window and if it survived it passed our test otherwise it didn't. One step, and we save a ball.
Put the ball it in a vise where you can measure the force when the ball breaks. Calculate the velocity required to reach that force and subsequent height needed. Then A) go bowling or B) sell the second one on ebay.
So this is a legitimate answer. You (as interviewer) say we should take the problem at face value and devise an algorithm to solve it. Me: Ok that's cool. I then tell you the problem isn't really solvable then because the bowling ball will accumulate damage as we test it (as others have pointed out). Me: OK (rolls eyes internally)
I solve problem again this time assuming changing floors and retrieving the ball is very time consuming (I don't know... like a database call, or a disk read... that doesn't have anything to do with computers either I guess). You again tell me I'm "wrong" because I didn't guess how you wanted me to solve this. (At this point I don't want your f'ing job anyway but decide to trudge through this retardation anyway (that's right because this interview is actually killing brain cells and making me think slower)) Alright now I go through the process you've gone through, get the "right" answer, and try to get the hell out of your office before the stink of failure rubs off on my clothes. The interviewer is annoyed it took me so long and I'm pissed off that I've wasted half of my day with your crappy company.
skip one floor at a time, for a worst case of 51 ball drops. If have a big supply of spares, then
I must be missing something. Why not just do a binary search? If you're only measuring the
number of dropped balls, it's O(log2(N)). For N=100, you only need 7 ball drops.
How do you find the first floor where they do break?
You say: "You're graded on your algorithm's worst-case running time. ", but you're optimizing on # of tries, which does not = time unless you account for actual time, not just # of tries.
If you can drop the ball without it being damaged then it will never break.
It's an inherently flawed question if they require you to use only two balls. Ideally you'd need a fresh ball for each drop.
Maybe the bowling balls are coated in a self-repairing layer of nanites, which stop working if the ball shatters.
{
int length = 100;
for (int i = 0; i < length; i++)
{
int realValue = i;
boolean[] floors = new boolean[length];
for (int n = 0; n < realValue; n++)
{
floors[n] = false;
}
for (int n = realValue; n < length; n++)
{
floors[n] = true;
}
int tests = 0;
int start = 0;
int end = length;
int testPoint = 0;
while (end - start > 1)
{
testPoint = (end - start) / 2 + start;
if (floors[testPoint])
{
end = testPoint;
}
else
{
start = testPoint;
testPoint = end;
}
tests++;
}
System.out.println("True value: " + testPoint);
System.out.println("Tests: " + tests);
}
}
In real life, a bowling ball will NOT survive a 100 floor drop. It just isn't possible. So you can discount the 100th floor. 99th? Discount it too. Repeat until you feel that the bowling ball is likely to survive. There is no point testing at any floor above that if you're sure the results aren't what you're looking for.
This question is akin to asking an undergraduate engineer what voltage a resistor will take, and then in demonstration, a far lower voltage would have burnt out the resistor already. Mathematics is fun, but in engineering, real life is what matters.
In the strategy above we're dropping the first ball from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95. Suppose it does not break on any.
After that there are 5 unexplored floors left, 96,97,98,99,100. We've used up 10 tries already, which means that worst case it will take 15 to find the remaining one.
Your algorithm is numerically sound, but that //would// be a "cheating" way to get the job done that would be more highly optimized.
Is it a hack? Sure. But it's a 'legitimate' hack -- and might have represented a similar way of thinking to the "get the cup without walking on the carpet" problem.
http://www.anonymity.at.tc
Even so, I like it more than most silly puzzle questions because there's a clear naive solution and a steady progression of solutions from poor to best.
i = 0
while( i < log10(n) and testFloor( (i + 1) * log10(n) ) {
i = i + 1
}
j = ( i * log10(n) ) + 1
while( j < i and testFloor(j) ) {
j = j + 1
}
return j * i
The pattern, I'm sure, can be improved. I was just exploiting that it is guaranteed to be within a 2 digit number. So one ball to figure out each digit.
If you want to be the one managing coders then ask them to read the bowling ball manual !
Thanks for the offer. A year and a half ago I might have taken you up on that, but Facebook has changed too much and so have I.
- Jesse
I only blame myself, although in retrospect I'm glad I didn't get it.
You were being judged on the WORST CASE.
If you choose to use 2 balls, the worst case is 100 throws plus one (the extra ball you had to throw from floor 100)
If you choose to use just one ball, the worst case is 100 throws.
There, solved it for ya.
And because you went all complex on this trivial logic excersize is likely why you didn't get the job.
You went looking for an optimal solution, if you would solve this problem a 100 times, with the balls breaking on a different floor each time.
You clearly state in the beginning that you were suppose to solve the problem of the WORST CASE. Which is just (n); using one ball.
You never told the interviewer that. You went on to solve a different problem. The one you were not asked to solve.
Your algorithm's worst-case is 100. His last algorithm's worst-case is 14. A shorter running time is better, of course.
You have the worst possible worst-case running time. Not only did you fail, you failed as hard as you possibly could.
If you choose to use 2 balls, the worst case is 100 throws
You can, with two balls, have the same optimum solution as with one ball, off course. Just keep switching them ;-)
If you read the post, the naive solution of using one ball and going one floor at a time is the first one given. The interviewer was happy with the solution.
1. Can't he manufacturer just tell us, so we can store the value and retrieve it as needed?
2. Can we copy the bowling balls, and then use an existing binary search function?
3. Has anyone else done this? Is there a library that we can use?
4. Etc ...
In other words, how can we avoid having to solve the problem ourselves if we don't have to?
Cheers, Rick
I cannot help but wonder if, by presenting the article in story format (and not as a purely abstract mathematical problem), the interviewer was inviting you to consider real-world implications such as the damage done to each ball when dropped, terminal velocity, etc. Especially if the job was for a programmer, who'd be familiar and comfortable with more abstract problems.
As one previous comment suggested, sometimes it's more difficult to find a programmer who understands the business rules than it is to find someone who can devise an efficient, mathematically sound algorithm. I've seen programmers spend hours and wrack their brains coming up with elegant, sophisticated "solutions" that overlook simple, common-sense factors. No offense intended, but programmers, IT specialists, and INTP-types are sometimes guilty of dwelling on theory at the expense of practice...
No, that wasn't the reason. If anything it was the opposite. The rest of my interview didn't inspire enough technical confidence, and I spent my time asking questions about their business. Read here for the details: http://20bits.com/articles/when-its-your-turn/
The reason I received for not getting an offer was that I, quote, "didn't have a strong enough technical background."
Secondly: You ponder the existence of a better solution. Would you not be able to easily prove this is optimal? This is worst-case analysis so we can take on the role of the adversary when considering alternative algorithms.
Clearly there exists a smallest integer C s.t. C is the lowest possible number of tries you have to make.
Claim:
Dropping the ball on height C in the first step is optimal.
Proof:
If an alternative algorithm chooses to drop it lower, we just place the actual place the ball breaks higher. Then in the next step the alternative would have to solve something >at least< as hard.
If an alternative algorithm chooses to drop it higher, then just place the ball in the last spot the algorithm would look with the remaining ball. (Remember we can be psychics when placing the ball here.) This would result in a >worse< number of tries.
Repeating this argument in each step proves that your strategy is optimal.
Setting the upper limit where you can stop testing.
Step 1 -- Calculate terminal velocity, using size and weight (for example, say thanks to wikipedia, example uses maximum weight), guesstimating drag coefficient at .47 for a smooth sphere.
-1/2 (rho) * v^2 * A * Cd = m * g
-1/2 1.3 * v^2 * pi*(0.108)^2 * 0.47 = 7.2 * 9.81
0.0112 * v^2 = 70.6
v ~ 79.40 m/s
Step 2 -- Determine fall distance at which terminal velocity is achieved
79.4 m/s is reached after 79.4 / 9.8 = 8.1 seconds
d = 1/2 * g * t^2
d = 1/2 * 9.8 * 8.1^2
d = 321.65 meters
So, depending on the dimensions of the building (and of course, the weight of the bowling ball), you can skip the top few floors. If it's a children's ball (weight 6 pounds or 2.72 kg), the max required test height is only 121 meters, or roughly 40 floors. Depending on your ball, a little physics will do wonders for the number of tests.
With a light ball, even your Method 1 will solve the problem in 10 steps, if only you used some physics first.
You can do even better by calculating at which height the ball will break. That way, assuming you have reasonably accurate figures, you can do it in 3 or 4 tests.
That's not true. What happens if the bad floor is the 10th floor? Once the ball breaks on the 25th floor you're done.
Anyway, that aside, the problem is fundamentally flawed and I'd refuse to answer the question on those grounds (and obviously not get the job). At any rate, I like to think out of the box, so here's some out-of-the box considerations for this problem.
The problem must first be re-defined to make it into a legitimate problem. Why? Any time you drop the bowling ball from any floor, you are subjecting it to forces that have the potential of breaking the ball. Now, even though a single drop from, say, the 10th floor may not break the ball, it may cause certain internal stress on the ball (or micro-fractures) that are not visible to the naked eye, which will cause the ball to break on the next drop above 10 (let's say 14 for the sake of argument). Thus, if you took a brand new, never-been-dropped ball and let it go from 14, not having suffered previous trauma, may stay intact, thus skewing your results.
In order for this problem to become valid, you go over to company stores, and social-engineer them into requisitioning a box of bowling balls to be FedExed to you. Then you can start with a baseline of 50 floors, examine the results, and whether the ball breaks or not, add or subtract floors accordingly, but ensuring to drop a fresh ball each time. If you were to multiply or divide by a factor of 2 (or so): 50; (25 is not further divisible by 2 so let's just go ahead and descend one more floor)... 24; 12; 6; 3; 2; 1, your worst case scenario would look like this:
(B=break; I=intact).
50(B); 24(I); 36(B); 30(I); 33(B); 32(B); 31(B).
If, however you are an unlucky bugger and the breaking point just happens to be 49, you might get this:
50(B); 24(I); 36(I); 43(I); 46(I); 48(I); 49(B).
Either way, the answer will be 7.
Thus, make sure your purchasing department orders 25 bowling balls. That way you can run the experiment 3 times for consistency and to get accurate numbers. This will use 21 of the 25 balls. Then, you can take the remaining 4 balls, one for yourself, and 3 for the guys down in purchasing so you can take them out bowling as a "thank you" when all the BS is done!
So, basically this problem can be solved with dynamic programming, by optimizing this:
F(m, n) = 1 + max(F(m-1, k-1), F(m, n-k)) for k = 1.. n
Running this on F(2, 100) can show that 14 is indeed the optimal solution. This should be able to changed to optimize for the average case, not the worst case.
What's interesting is that (if my program is correct) it only takes 5 balls to achieve 7 steps (which is the best possible number of steps, since 2^6 < 100 and 2^7 > 100).
The speed of the ball is the key to when it breaks, and it goes as sqrt(h).
So one should take that into account when sampling (i.e. sample not every S floors,
but make it a uniform stride in impact velocity).
from a physics point of view, questions are not asked to see the result, but
how one thinks about things. Including discussions of important factors
like:
climbing up stairs, terminal velocity, the quick solution, the optimal solution,
accumulated wear on the ball, insuring zero initial velocity, using non-integer floors
by allowing a small initial downward velocity, or tossing the ball up halfway between floors,
repeatability of the experiment, are the balls identical, why aren't the windows locked, measuring
the temperature while doing the experiment, effect of Coriolis force on the ball, etc