Hello! Community Page
- 20bits.com Jump to website »
-
Subscribe -
Community
-
Top Commenters
-
Popular Threads
-
Recent Comments
- Apparently there is a new one (^^^) = shark ahhaha these above comments are hilarious...I love seeing people get pissed off about this
- I keep trying the robot but the straight line is messing me up. Im pretty sure it's a lowercase L but i'm not completley sure....
- underline, which is underline where the asterisks were.
- (^^^) is a shark
- hold shift and push the \ above "enter"
11 months ago
10, 9, 9, 8 ,8 ... 3, 3, 2, 2, 1, 1
7 months ago
Can you share the math that gave you those numbers? I'd be interested in taking a look.
7 months ago
7 months ago
Don't make a mean comment if you don't know what's going on.
7 months ago
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
7 months ago
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.
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
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.
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
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.
7 months ago
How do you find the first floor where they do break?
7 months ago
7 months ago
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.
7 months ago
7 months ago
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.
7 months ago
Maybe the bowling balls are coated in a self-repairing layer of nanites, which stop working if the ball shatters.
7 months ago
7 months ago
7 months ago
7 months ago
{
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);
}
}
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
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.
7 months ago
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.
7 months ago
7 months ago
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.
7 months ago
7 months ago
7 months ago
http://www.anonymity.at.tc
7 months ago
7 months ago
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.
7 months ago
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.
7 months ago
If you want to be the one managing coders then ask them to read the bowling ball manual !
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
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
7 months ago
7 months ago
I only blame myself, although in retrospect I'm glad I didn't get it.
7 months ago
7 months ago
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.
7 months ago
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.
7 months ago
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.
7 months ago
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 ;-)
7 months ago
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.
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
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
7 months ago
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...
7 months ago
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."
7 months ago
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.
7 months ago
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.
7 months ago
7 months ago
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.
7 months ago
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!
7 months ago
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).
7 months ago
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
3 months ago
3 months ago
7 months ago
7 months ago