analytical Skill for Java Development

[Timbo]

Yup. But if I'm 99.99% confident that the first ball survives and 0.1% I
have to do the full 100 drops, then that's a mean of around 1.01 drops.
The obvious answer is averaging about 20.

Why would you be 99.99% confident that the ball would survive the
first drop?

I didn't get that from the question.

I did: "Your task is to find *which* floor of a 100-storey
building the balls will break on". To me, that implies that it
will break on at least one of the floors.

 

[Thomas Hawtin]

Hi,



Java has changed very much in the last years. E.g. think of generics.

And the technology around Java has changed much more.

Example: 5 years ago you probably would have written an Applet which now
you write as a Java-Webstart-Application. Although your specific
knowledage about applets is still true (did not change), it is now more
or less worthless.

I packaged my first app in JNLP (0.4) over five years ago. It's not
rocket science. And applet is small API (although browser bugs were a
pain). Applets can still be useful (although I don't run the plug-in in
any of my browsers).

Whereas the value of your *general* konowledge about
Client-Server-Architecture did not change so much.

Good old 3270 terminals.

But the value of your general problem-solution-capabilities did not
change at all.

Nobody wants general problem-solution-capabilities. A sane employer will
want someone capable in a particular field. Particular APIs aren't of
much concern, nor is the ability to play silly games.

Sorry, I don't get what you mean. (One reason might be that I did not
even realize the grammar of your first sentence. Remember, I'm from
Germany and my English is not the best...)

Er, yeah. A bit of a tortuous sentence there.

If you drop a ball a foot or two and then from one floor up, it wouldn't
be much of a surprise if it broke on the proportionately much higher drop.

If you drop a ball from the 99th floor, you can be reasonably confident
that it will survive the drop from the 100th floor. Particularly if you
consider terminal velocities. If you were doing the problem with cats,
you should throw one off the top floor.

Tom Hawtin

 

[Ingo R. Homann]

Hi,

To me most of the change for generics was replacing /*< with < and >*/
with >.

That's funny!

I packaged my first app in JNLP (0.4) over five years ago. It's not
rocket science.

That's the nature of examples: Of course I use a simple example to show
what I mean. If I would have choosen an example from rocket science,
then we would have to argue about too much details.

But my example shows perfectly what I mean - and there would be much
more examples from the degree of rocket science that would also show the
same.

And applet is small API (although browser bugs were a
pain). Applets can still be useful (although I don't run the plug-in in
any of my browsers).

OK, seems that even for this simplest example we have to go to detail:
Once, there was an <applet>-Tag, now there is an <object
type=applet>-Tag (or something like that). WebStart also has its special
things to consider.

Good old 3270 terminals.

No. I speak about *general* knowledge. "general knowledge" never heard
of any "version numbers" or specific products.

Nobody wants general problem-solution-capabilities.

Well, *I* want...

A sane employer will
want someone capable in a particular field.

IMHO, only, if this someone has the necessary background-knowledge,
which is quite general.

Particular APIs aren't of
much concern, nor is the ability to play silly games.

To find an optimal algorithm is some kind of game (at least, most
programmers I know, think so).

If this is silly, depends on the point of view.

If you drop a ball a foot or two and then from one floor up, it wouldn't
be much of a surprise if it broke on the proportionately much higher drop.
Yes...

If you drop a ball from the 99th floor, you can be reasonably confident
that it will survive the drop from the 100th floor.

No, the opposite is true: You already know from the problem
specification that it will break somewhere between floor 1 and 100. So,
if it does not break on the 99th floor, you can be *sure* that it must
break on the 100th floor!

Ciao,
Ingo

 

[Thomas Hawtin]

Assuming that the ball breaks at the top floor, from where would you
drop the 2nd ball? You have to start from the ground and do a linear
search.

Yup. But if I'm 99.99% confident that the first ball survives and 0.1% I
have to do the full 100 drops, then that's a mean of around 1.01 drops.
The obvious answer is averaging about 20.

Furthermore, if you are guaranteed that the ball will break at
some point from 1-100, then you know it will certainly break at floor 100.

I didn't get that from the question.

Tom Hawtin

 

[Ingo R. Homann]

By the way...

To me most of the change for generics was replacing /*< with < and >*/
with >. It makes little fundamental difference. It just tidies things up.

This only works because you indeed have the necessary
general-background-knowledge about a type system.

Unfortunately, many programmers (who only learned Java and not e.g. C++)
don't have that knowledge!

Ciao,
Ingo

 

[Oliver Wong]

As an experiment, give an "experienced" developer a problem and watch
their
analytical and problem solving skills seriously fail him/her. This of
course, is the general case - there may be some corner cases where this
will
not occur.

Are you saying that, generally speaking, the more experience a person
has, the less skill they have?

- Oliver

 

[Chris Uppal]

OK, new idea: Throw one ball from the 10th floor. If it does not break,
throw it from the 20th, and so on. When it breaks, you know that it is
"breakable" between the n-th and the (n-10)-th floor. You must do a
linear search from then on with the second ball. So you need max. 20
tries. I suppose, the word case generally is 2*sqrt(N). The average case
is eh... sqrt(N)?

I think that's close to correct, may even be correct, but the average number of
throws is slightly over 10.

I'll number the floors from 0 through 99 in the logical UK style.

Start at ground level (floor 0).
Throw ball 1 out of window. If it doesn't break, go up 10 flights and repeat.
Note that we can stop after testing floor 90, since if the ball hasn't broken
there then the target floor must be in the last 9.

Go to the floor above the highest one where ball 1 didn't break. There are two
cases:
* If we are on floor 90 and the ball didn't break then go up one flight.
We have the remaining 9 floors to test using ball 2.
* Otherwise go down 9 flights. There are now 9 floors, including this
one, that we have to check with ball 2, E.g. 21 through 29.
In either case we only need to throw ball 2 out 8 times, since if the ball
hasn't broken by the eighth test then we know that it would do so on if thrown
from the next floor up.

So on average we make (1+2+3...+9+9)/10 tests with ball 1 (NB: 9 is
duplicated). That's 5.4.
And on average we make (1+2+3...+8+8)/9 tests with ball 2. That's 4.888.
Overall we make an average of 10.2888 throws. (That's all assuming that each
floor has equal probability of being "it").

If we didn't use the skip-last-test optimisation, then we'd need an average of
5.5 throws with ball 1, and 5 with ball 2, totalling 10.5.

Notice that in 1 out of 10 cases we end up with ball 1 still intact, and a we
have a 1/9 chance of not breaking ball 2; we even stand a 1/100 chance of not
breaking either ball. That suggests that we aren't /quite/ making best use of
the information they could provide. I don't see how to wring that extra bit of
data out of them, but it would be particularly neat if there was a way and it
reduced the average number of tests to exactly 10.

-- chris

 

[Chris Uppal]

I would have through the probability of a ball (pair) breaking when
dropped from the first given it does not drop from the ground floor is
much greater than it breaking from the 100th if it did not break from
the 99th. Perhaps the vast majority of balls don't break when dropped
from the 100th, so the first ball should be dropped from the top first
off.

If the probability function for a given floor's chances of being "the floor" is
non-uniform, then I think the obvious solution can be adjusted quite easily.
Instead of dividing the floors up into roughly sqrt(N) evenly sized blocks with
the first ball, and then searching within "the" block for "the" floor with the
second, we take the probabilities into account too. Partition the floors into
blocks such that each block has (as near as possible) the same probability of
containing "the" floor. Use the balls as before.

Getting the integer rounding optimal might be tricky -- might even require
exponential pre-computation.

-- chris

 

[Oliver Wong]

1) You have two identical glass balls; when dropped from a certain height,
they will break. If they do not break, they are re-usable. Your task is to
find which floor of a 100-storey building the balls will break on.
Describe in words the algorithm you would use. We are interested in the
time complexity of the algorithm; you should spend the majority of your
time on this question attempting to optimize the algorithm.

Hint: you can always do a linear search with one of the balls, though this
a profoundly suboptimal solution to the problem.

You should probably specify that the only allowable operation is to drop
the balls from various floors of the building, else a much more time-optimal
solution would be to throw an object of a known weight (e.g. 1 kg) into the
ball with higher and higher velocity until the ball breaks, at which point
you can calculate what velocity would have caused the ball to break, and
then use various Newtonian equations to calculate at what height the ball
would need to have been dropped to exert the same amount of force, and thus
cause the breakage.

2) You have many piles of rocks. The rocks in each pile are identical.
There are an infinite number of rocks in each pile. You know that the
rocks in one of the piles are slightly heavier than the rocks in all the
other piles. (Say 1.1 kg instead of 1 kg.) You have a scale that you may
use exactly once. Describe an algorithm to determine which pile contains
the heavier rocks.

The rocks in each pile are identical... to what? To every other rock in
the problem? To every other rock in the same pile? Are you essentially
saying that for your N piles of rocks, N-1 of them contain rocks that weight
1 kilogram, and 1 of them contains rocks that weight 1.1 kilogram, and that
the rocks are otherwise indistinguishable, and so the goal is to find the
pile with the 1.1. kilogram rocks using the scale exactly once?

I'm stumped on this one.

- Oliver

 

[Oliver Wong]

Hi,

Thomas Hawtin wrote:

No, the opposite is true: You already know from the problem specification
that it will break somewhere between floor 1 and 100. So, if it does not
break on the 99th floor, you can be *sure* that it must break on the 100th
floor!

If you want to get technical, the problem never actually says that the
ball will break somewhere between floor 1 and 100. It only says that it will
break from being dropped from "some height", and this height might be
equivalent to a drop from the top of a 500 story building. It phrases the
question as "which floor of a 100-storey building the balls will break on",
to which the answer could be "none of them!", or "all the floors above 50",
etc.

But probably, the person who created this problem originally meant for
the ball to break between floors 1 and 100; they merely forgot to mention it
in the problem statement.

- Oliver

 

[Oliver Wong]

My worst case is 20! And the average is 10. (If my calculations are
correct.) I think, this is hard to top.
[...]

The more I think about it, the more I think that my idea is optimal:

Do some kind of "linear search" on 10,20,30,40,50,...,100 with the first
ball and then (if the first ball e.g. breaks on 40) a linear search on
31,32,33,...39 with the second ball.

That's O(sqrt(N)). I think you cannot get any better.

You're essentially doing a bucket-sort with 2 digits. That is, you want
to classify the ball in one of the following buckets: "breaks on floor 1"
bucket, the "breaks on floor 2" bucket, etc.

What you did was create 10 new buckets ("breaks on floors 1 to 10",
"breaks on floors 11 to 20", etc.), and then used one ball to check which of
these buckets the balls belong to. Then, you narrowed the original problem
from 100 buckets to 10 buckets (e.g. you know the ball must lie between
"breaks of 61st floor" and "breaks on 70th floor").

http://en.wikipedia.org/wiki/Bucket_sort

I think your solution is pretty optimal too. Better than anything I've
come up with so far.

- Oliver

 

[Andrea Desole]

Yes, but in every second case (the probability that the ball breaks on
floor 1-50 is 0.5 when the probability is equally distributed) you need
a linear search from 1 to 49. And this needs in worst case 49 tries
(avg. 25).

true, but in the other cases efficiency increases quickly

My worst case is 20! And the average is 10. (If my calculations are
correct.) I think, this is hard to top.

Actually, I think it's 19 and 9

I dont agree: In binary search, you need to halve the *remaining*
interval in every step. You do the opposite.

I know. The point is that I can't do a real binary search in this case.
Still, it would be nice to use the first ball to eliminate as many
possibilities as possible before it breaks

Of course you are right that binary search is not the proper solution
for this problem - but this is no argument for your algorithm.

The more I think about it, the more I think that my idea is optimal:

Do some kind of "linear search" on 10,20,30,40,50,...,100 with the first
ball and then (if the first ball e.g. breaks on 40) a linear search on
31,32,33,...39 with the second ball.

That's O(sqrt(N)). I think you cannot get any better.

You might be right, now that I'm thinking about it. Do you have a reason
to choose sqrt(n) to make your interval?

Note that the cost measure I used is the number of tries you drop a ball.

Damn, I was sure that was the requirement, but when I read it again I
found out that it's not really mentioned. The only thing that suggests
it is the reference to the linear search in the hint.
I always read too fast :-(

 

[Chris Uppal]

A better cost mesaure might be the number of stairs you have to go
(which should approximately be linear to the time you need). With this
new measure, a different algorithm should be better

I think this measure could be accommodated within the same general framework,
you divide the floors up into sqrt(n) non-equal groups such that each group has
the same average number of stairs to climb /if/ the target floor is in that
group. I don't see an easy way to state that grouping analytically, off-hand,
so I'd just throw the problem at a computer and let it work it out.

You could further adjust the sizes of the groups to allow for non-constant
probabilities if you wished. To me that sounds too much like hard work to be
fun, and I think I'd rather go help Thomas throw cats off the roof.

-- chris

 

[Oliver Wong]

To me it just meant "for example all the heavier rocks are 1.1 kg heavier"

Let's say we do your technique, and we find the weight to be 1 + 2 + 3
+... +n + 0.6 kilograms heavier. So which pile contains the heavy rocks?
Well, if the heavy rocks are 1.1kg, and the non-heavy rocks are 1.0kg, then
the 6th pile contains the heavy rocks. But if the heavy rocks are 1.2kg, and
the non-heavy rocks are 1.0kg, then the 3rd pile contains the heavy rocks.
And if the heavy rocks are pi kilograms, and the non-heavy rocks are
square-root-of-two kilograms... which pile is it then?

Collapsing into black holes isn't so much a question of being infinitely
massive, but more one of being infinitely dense. For most intents and
purposes, there is "infinite" mass in the universe, and yet the universe
doesn't immediatel collapse into one giant black hole, because the mass is
distributed in such a way so as to make the universe mostly non-dense.

Similarly, perhaps each "pile" of rocks is arranged so that the rocks
within those piles are far away from each other (or of a large enough
volume, perhaps hollow inside) such that they would not collapse into a
black hole.

More probably, you don't ACTUALLY have an infinite number of rocks, but
rather, the "client" is stating that you have no upper bound on the number
of rocks you are allowed to use (e.g. if you need more rocks, the client is
willing to pay for more rocks to be acquired).

oh well, in that case you can come up with several questions:

- where are these infinite number of rocks coming from? There must be a
very big mine somewhere

This information probably won't help you solve the problem. The problem
statement says you "have" the rocks, implying that you have access to them,
so perhaps the client will create them on the fly as you ask for them.

- who can take the time to collect an infinite number of rocks?

The problem isn't bounded by time either, so if your algorithm takes a
billion years to complete, that's okay, it seems.

- who can take the time to weight them?

Perhaps the solution does not involve weighing every single rock;
perhaps you can weigh only 2n^2 rocks, where n is the number of piles. You
might protest "But how can the client guarantee that all the rocks weight
exactly 1.0 kilogram unless (s)he weighs them all?" Well, perhaps the client
*generates* the rocks for you, thus guaranteeing that every rock provided to
you will be 1.0 kilogram, except for the heavy ones.

- if the rocks are of the same material, and some are 10% heavier, they
will probably be 10% bigger. Can't you just spot them?

They might not be 10% bigger: they might be the same size, with the
non-heavy ones hollow in the center. I think the problem statement mentions
that the rocks are essentially indistinguishable except for that difference
in mass.

- Oliver

 

[Oliver Wong]

Hey it is quite easy. U can know it in 2 attempts. Devide the 6 balls
into two sets and keep the 7th ball separate. Now keep these 2 sets of
ball in the both side of weighting balance. If both side weiht equally
than the 7th ball which kept separately is the one with different
weight. If both sides are weighting differently then take the set of
ball which is heaver. Now out of these 3 balls keep one ball separately
and keep rest 2 balls in the both side of the weighting balance. If it
weights equal then the 3rd ball kept separately is the one with
different weight. Else the ball which weights more in that weighting
balance is the required ball.
So in the least 2 attempts u can find out the required result. this is
nothing but the binary search.....

I'd say this is more of a "fancy" binary search, where instead of
splitting the problem in half each time, you're splitting the problem into 3
groups, where one of the groups is size 1.

- Oliver

 

[Ingo R. Homann]

Hi,

[very interesting stuff]
Notice that in 1 out of 10 cases we end up with ball 1 still intact, and a we
have a 1/9 chance of not breaking ball 2; we even stand a 1/100 chance of not
breaking either ball. That suggests that we aren't /quite/ making best use of
the information they could provide. I don't see how to wring that extra bit of
data out of them, but it would be particularly neat if there was a way and it
reduced the average number of tests to exactly 10.

Well, if you are not satisfied, that we know the solution and one (or
even both) balls are intact - then...

....take a hammer and punsh on it! ;-)

No really: you explained very clearly the (IMHO optimal) solution,
thanks for that!

I think that the fact that a ball might be intact at the end has to do
with the rounding of the integes and cannot be solved. Perhaps this
would work better, if our building would have 110 stairs.

On the other hand: Nobody in this thread has already *proven* that the
solution is optimal! (This would also be quite interesting and very hard
imho...)

Ciao,
Ingo

 

[Stefan Ram]

If the probability function for a given floor's chances of
being "the floor" is non-uniform, then I think the obvious
solution can be adjusted quite easily.

The probability distribution can be derived from the problem
formulation, because one always gets probability distributions
from the current (possibly incomplete) knowledge.

So what is the distribution? (For someone with perfect
knowledge about the field of physics and probability
calculations, but only knowing about the problem what is given
in its text.)

"when dropped from a certain height, they will break." does
not tell that they will break for any floor at all. So if the
height is completely unknown, then by maximum entropy and
certain principles of symmetry, I believe that the chance for
smaller floors might be larger. The argument would be similar
to the proof of Benford's law (using Jeffreys' Prior):

http://en.wikipedia.org/wiki/Benford's_law

If "find which floor of a 100-story building the balls will
break on" is being interpret as the assertion that they will
indeed break for some floor one can assume even distribution
in this range. The question remains for which parameter. The
floor number might not be the best parameter because the
percentual difference in flight speed or energy should be
larger between floor 1 and 2 than between floor 99 and 100.

To find the parameter, one might like to find what the stress
of the ball is proportional to (e.g., the speed or the kinetic
energy). Possibly one might also take the air resistance into
consideration, by which the final speed is limited.

This is getting complicated. So, as a rough estimation, I
might increase the step size for the first ball somewhat,
testing it at, e.g., floor 1, 2, 3, 5, 7, 9, 14, 20, 27, 40,
60 and 99 or so.

 

[Chris Lamb]

Hi,

[very interesting stuff]
Notice that in 1 out of 10 cases we end up with ball 1 still intact, and a we
have a 1/9 chance of not breaking ball 2; we even stand a 1/100 chance of not
breaking either ball. That suggests that we aren't /quite/ making best use of
the information they could provide. I don't see how to wring that extra bit of
data out of them, but it would be particularly neat if there was a way and it
reduced the average number of tests to exactly 10.

Well, if you are not satisfied, that we know the solution and one (or
even both) balls are intact - then...

...take a hammer and punsh on it! ;-)

No really: you explained very clearly the (IMHO optimal) solution,
thanks for that!

I think that the fact that a ball might be intact at the end has to do
with the rounding of the integes and cannot be solved. Perhaps this
would work better, if our building would have 110 stairs.

On the other hand: Nobody in this thread has already *proven* that the
solution is optimal! (This would also be quite interesting and very hard
imho...)

I think you can only prove an optimal value of a given form of solution
and given metric. For example, the worst case (w) metric of a "hopping +
linear" type solution (as discussed) - we can find the optimal value of
hop size reasonably easily since for hop size n: w = 100/n + (n-1)
and we are looking to minimise (dw/dn) which leads to n being sqrt(100)
which is 10.

Chris

 

[Andrea Desole]

Let's say we do your technique, and we find the weight to be 1 + 2 + 3
+... +n + 0.6 kilograms heavier. So which pile contains the heavy rocks?
Well, if the heavy rocks are 1.1kg, and the non-heavy rocks are 1.0kg, then
the 6th pile contains the heavy rocks. But if the heavy rocks are 1.2kg, and
the non-heavy rocks are 1.0kg, then the 3rd pile contains the heavy rocks.
And if the heavy rocks are pi kilograms, and the non-heavy rocks are
square-root-of-two kilograms... which pile is it then?

well, if you know how heavy the stones are it's not a problem, is it?
And it is in the requirements, as far as I understand.
To state it clearly, all rocks from all piles have the same weight w,
known. Only one pile have rocks with the same weight w+d, also known.
This is how I understand it.

This information probably won't help you solve the problem. The problem
statement says you "have" the rocks, implying that you have access to them,
so perhaps the client will create them on the fly as you ask for them.


The problem isn't bounded by time either, so if your algorithm takes a
billion years to complete, that's okay, it seems.


Perhaps the solution does not involve weighing every single rock;

no it doesn't, even because you can't, according to the description of
the problem. I was just wondering how someone can tell how heavy every
rock is if the number of rock is infinite.
It was just a list of non serious questions

They might not be 10% bigger: they might be the same size, with the
non-heavy ones hollow in the center. I think the problem statement mentions
that the rocks are essentially indistinguishable except for that difference
in mass.

good point. I didn't think about a cavity in the stones. And you are
right, it is clearly said that the rocks are identical.

 

[Thomas Hawtin]

This is getting complicated. So, as a rough estimation, I
might increase the step size for the first ball somewhat,
testing it at, e.g., floor 1, 2, 3, 5, 7, 9, 14, 20, 27, 40,
60 and 99 or so.

I'm not convinced you'd want the later steps so big. I suppose this
applies to the linears, steps of 10 strategy too.

If I had got to floor eighty with both my balls intact, then I can
subtract 80 from the floor number and re-read the question as asking
about two balls and 20 floors. Reapplying the "linear" logic, I should
choose floor sqrt(20) (approximately).

So is a better answer going in at sqrt of remaining floors?

Oh, I hate these sorts of things.

Tom Hawtin