analytical Skill for Java Development
nospam
Recently I had been attending some interviews(almost after 10years)
for Java Developer/Lead position. At each interview, 75% of the alloted
time was spend was on problem solving sessions or checking the
analytical skills. I was just wondering what has prompted the companies
to include such a session & give so much importance to it.?
Regards,
SMC
A couple of reasons we do this:
* resumes are often embellished
* references are only ever positive
* both of the above give you no real idea of how good the candidate is at
actual software engineering
* we don't care if you're a syntax dictionary, we care about the way you
think and solve problems. We're happy with reference book programmers as
long as they have the right mind for software engineering
We've had people who know a language but can't write decent working
software to save their lives.
Best of all, people with good problem solving and analytical skills can
transfer these skills to any programming language. If we one day ditch
Java for Ruby (for example) we'd have confidence in most of our people
easily making the transition.
--
Sean
I doubt, therefore I may be.
Tony Morris
news:babGf.28240$F_3....@newssvr29.news.prodigy.net...
There has been a slight shift in the industry in that the creation of a
distinction between "experience" and "skill" has seen a bias toward "skill".
Skill may (at least, according to the industry) be measured by one's ability
to analyse a problem in contrast to having appeared to analyse many problems
in the past (experience).
The industry is beginning to demand skill and not experience, instead of
equating the two with some blur. One can speculate on the reasons why, but I
would probably base them somehow on the rise and fall of demand a few years
ago.
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. Like many maturing industries in the past, we can only sit back
and wait for these people to retire before serious progress is made. Until
then, one can only minimise the adverse consequences that are caused by this
phenomena, educate, and be educated with, the growing minority - 3 days to
go before I'm outta here!!!
Is it any wonder the industry is littered with failed software projects?
--
Tony Morris
http://tmorris.net/
im
Could you please post some examples of specific problems you had to solve
during the interviews?
Adam Maass
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.
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.
Ingo R. Homann
I think these are very good questions that show how you solve problems
(and e.g. do not show how exactly you know a certain API or technology
that may - no: "will certainly" - change in the next years or months).
Ciao,
Ingo
PS: Am I wrong, or is the second question (to which IMHO the answer is
obvious) *much* easier than the first one? My first idea was to throw
one of the balls from the 50th floor, but on second thought that is of
course far from optimal (or perhaps on 100th thought it might not be as
bad as all ;-)
Ingo R. Homann
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)?
Perhaps you can find a much better algorithm, depending on your measure:
Perhaps, it is not interesting, how many tries you need, but how many
stairs you have to go.
Then, when you know that it does not break on the 10th floor, you down
and get the ball, go to the 11th floor, where you throw one ball and
then go 9 stairs up to the 20th floor where you throw the other ball.
That are 2 tries, but only 20 stairs! So, a slightly different algorithm
might be much better!
This becomes *quite* challanging!
Ciao,
Ingo
stixwix
Adam Maass wrote:
> 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.
Huh? Surely this is not possible to determine?
stixwix
>
> Could you please post some examples of specific problems you had to solve
> during the interviews?
There are 7 visually identical balls. One ball weighs slightly more
than all the others.
Use a weighing balance to determine the heavy ball in the least number
of attempts.
pa...@atom.sbrk.co.uk
What counts as "once"? Does put rock from pile a on left, then from b on
right, then from c on left, then from d on right... count as one use?
Andrea Desole
should be 1+2+3+...+n kilos. If it's .1 more the rocks from the first
pile are heavier, if it's .2 more the rocks from the second are heavier,
and so on. I knew the solution :-)
I find the first one harder; I would probably go with a binary search at
the beginning to do it faster, until the first ball breaks, and then I
would do that linearly.
sunand...@gmail.com
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.....
Ingo R. Homann
Andrea Desole wrote:
> take 1 rock from the 1st pile, 2 from the 2nd, etc. The total weight
> should be 1+2+3+...+n kilos. If it's .1 more the rocks from the first
> pile are heavier, if it's .2 more the rocks from the second are heavier,
> and so on. I knew the solution :-)
Yes, this is easy.
> I find the first one harder; I would probably go with a binary search at
> the beginning to do it faster, until the first ball breaks, and then I
> would do that linearly.
As I explained in another post, this was also my first idea. But this
fails: When you throw the first ball from the 50th floor and it breaks,
you have to do a linear search from 1 to 49. That's hard.
What do you think of my ideas explained in my other posts?
Ciao,
Ingo
Chris Uppal
> > > 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.
> take 1 rock from the 1st pile, 2 from the 2nd, etc. The total weight
> should be 1+2+3+...+n kilos. If it's .1 more the rocks from the first
> pile are heavier, if it's .2 more the rocks from the second are heavier,
> and so on. I knew the solution :-)
That depends on knowing the specific difference between the weights of the
heavier and typical rocks. It is not clearly stated in the problem definition
that you do have that information. The phrase "(Say 1.1 kg instead of 1 kg.)"
sounds like an indication of the /kind/ of difference ("small but not tiny"),
rather than a statement of the actual number.
Typically vague/incomplete requirements specification...
Another problem that the customer hasn't thought through is how you are
supposed to prise a rock off any of the piles all. Being infinite massive, the
piles' gravity would be something of a problem, as would their natural tendency
to collapse forming black holes.
-- chris
Thomas Hawtin
>
> I think these are very good questions that show how you solve problems
> (and e.g. do not show how exactly you know a certain API or technology
> that may - no: "will certainly" - change in the next years or months).
I think they're party tricks. Java hasn't changed much since 1.1.
> PS: Am I wrong, or is the second question (to which IMHO the answer is
> obvious) *much* easier than the first one? My first idea was to throw
> one of the balls from the 50th floor, but on second thought that is of
> course far from optimal (or perhaps on 100th thought it might not be as
> bad as all ;-)
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.
Tom Hawtin
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
Ingo R. Homann
Thomas Hawtin wrote:
>> I think these are very good questions that show how you solve problems
>> (and e.g. do not show how exactly you know a certain API or technology
>> that may - no: "will certainly" - change in the next years or months).
>
> I think they're party tricks. Java hasn't changed much since 1.1.
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.
Whereas the value of your *general* konowledge about
Client-Server-Architecture did not change so much.
But the value of your general problem-solution-capabilities did not
change at all.
>> PS: Am I wrong, or is the second question (to which IMHO the answer is
>> obvious) *much* easier than the first one? My first idea was to throw
>> one of the balls from the 50th floor, but on second thought that is of
>> course far from optimal (or perhaps on 100th thought it might not be
>> as bad as all ;-)
>
> 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.
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...)
Ciao,
Ingo
Timbo
you drop the 2nd ball? You have to start from the ground and do a
linear search. 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.
Andrea Desole
> As I explained in another post, this was also my first idea. But this
> fails: When you throw the first ball from the 50th floor and it breaks,
> you have to do a linear search from 1 to 49. That's hard.
yes, but that's the worst case.
>
> What do you think of my ideas explained in my other posts?
That's really a tough question. We should assume a specific distribution
of the "breaking position" (probably uniform), and see on average which
solution is more efficient, and by how much. This is not an easy problem.
Even from a qualitative point of view, the binary search solution tends
to lose a lot in some specific positions, since if the ball breaks the
search has to be stopped, but tends to be pretty good in others because
of the nature of binary search. Which one is better is difficult to tell.
Maybe, because of the problem that if the ball breaks the binary search
can't continue, another solution might be a mix: instead of a fixed
amount, increase it, making it square every time. Something like
positions 4,8,16,32,64...
Andrea Desole
>
> That depends on knowing the specific difference between the weights of the
> heavier and typical rocks. It is not clearly stated in the problem definition
> that you do have that information. The phrase "(Say 1.1 kg instead of 1 kg.)"
> sounds like an indication of the /kind/ of difference ("small but not tiny"),
> rather than a statement of the actual number.
>
> Typically vague/incomplete requirements specification...
:-)
To me it just meant "for example all the heavier rocks are 1.1 kg heavier"
>
> Another problem that the customer hasn't thought through is how you are
> supposed to prise a rock off any of the piles all. Being infinite massive, the
> piles' gravity would be something of a problem, as would their natural tendency
> to collapse forming black holes.
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
- who can take the time to collect an infinite number of rocks?
- who can take the time to weight them?
- 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?
Ingo R. Homann
Andrea Desole wrote:
>> As I explained in another post, this was also my first idea. But this
>> fails: When you throw the first ball from the 50th floor and it
>> breaks, you have to do a linear search from 1 to 49. That's hard.
>
> yes, but that's the worst case.
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).
My worst case is 20! And the average is 10. (If my calculations are
correct.) I think, this is hard to top.
>> What do you think of my ideas explained in my other posts?
>
> That's really a tough question. We should assume a specific distribution
> of the "breaking position" (probably uniform), and see on average which
> solution is more efficient, and by how much. This is not an easy problem.
> Even from a qualitative point of view, the binary search solution tends
> to lose a lot in some specific positions, since if the ball breaks the
> search has to be stopped, but tends to be pretty good in others because
> of the nature of binary search. Which one is better is difficult to tell.
> Maybe, because of the problem that if the ball breaks the binary search
> can't continue, another solution might be a mix: instead of a fixed
> amount, increase it, making it square every time. Something like
> positions 4,8,16,32,64...
I dont agree: In binary search, you need to halve the *remaining*
interval in every step. You do the opposite.
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.
Note that the cost measure I used is the number of tries you drop a ball.
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 explained how to
"parallelize" my algorithm - but of course that is not optimal as well).
Ciao,
Ingo
Thomas Hawtin
> Hi,
>
> Thomas Hawtin wrote:
>>> I think these are very good questions that show how you solve
>>> problems (and e.g. do not show how exactly you know a certain API or
>>> technology that may - no: "will certainly" - change in the next years
>>> or months).
>>
>> I think they're party tricks. Java hasn't changed much since 1.1.
>
> Java has changed very much in the last years. E.g. think of generics.
To me most of the change for generics was replacing /*< with < and >*/
with >. It makes little fundamental difference. It just tidies things up.
> 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.
>> 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.
>
> 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.
Thomas Hawtin
> Thomas Hawtin wrote:
>> 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.
>>
> 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.
Ingo R. Homann
Thomas Hawtin wrote:
> To me most of the change for generics was replacing /*< with < and >*/
> with >.
That's funny! :-)
>> 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.
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.
Nowadays, your *specific* knowledge of the <applet>-Tag is worthless.
(And please remember what I said in my first two paragraphs about examples!)
>> Whereas the value of your *general* konowledge about
>> Client-Server-Architecture did not change so much.
>
> Good old 3270 terminals.
No. I speak about *general* knowledge. "general knowledge" never heard
of any "version numbers" or specific products.
>> But the value of your general problem-solution-capabilities did not
>> change at all.
>
> 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
Ingo R. Homann
Thomas Hawtin wrote:
> 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
"Tony Morris" <n...@telling.you> wrote in message
news:43e9...@quokka.wn.com.au...
>
> 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
"Adam Maass" <adam.nos...@comcast.net> wrote in message
news:NeednZ7aGsJBM3Te...@comcast.com...
>
> "im" wrote:
>> Could you please post some examples of specific problems you had to solve
>> during the interviews?
>>
>
> 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
"Ingo R. Homann" <ihoman...@web.de> wrote in message
news:43e9fbc4$0$338$9b4e...@newsread2.arcor-online.net...
> Hi,
>
> Thomas Hawtin wrote:
>> 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!
>
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
Timbo
> Timbo wrote:
>
>> Thomas Hawtin wrote:
>>
>>> 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.
>>>
>> 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.
>
first drop?
>> 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.
>
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.
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
"Andrea Desole" <ne...@desole.demon.NOSPAMPLEASE.nl> wrote in message
news:7accc$43e9e9ba$d468cb3c$27...@news.support.net...
> Chris Uppal wrote:
>>
>> That depends on knowing the specific difference between the weights of
>> the
>> heavier and typical rocks. It is not clearly stated in the problem
>> definition
>> that you do have that information. The phrase "(Say 1.1 kg instead of 1
>> kg.)"
>> sounds like an indication of the /kind/ of difference ("small but not
>> tiny"),
>> rather than a statement of the actual number.
>>
>> Typically vague/incomplete requirements specification...
>
> :-)
> 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?
>
>>
>> Another problem that the customer hasn't thought through is how you are
>> supposed to prise a rock off any of the piles all. Being infinite
>> massive, the
>> piles' gravity would be something of a problem, as would their natural
>> tendency
>> to collapse forming black holes.
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
<sunand...@gmail.com> wrote in message
news:1139396589.0...@z14g2000cwz.googlegroups.com...
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
Chris Uppal wrote:
> [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
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.
>> 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;
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
>> - 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.
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.
Chris Lamb
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
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.
Roedy Green
<adam.nos...@comcast.net> wrote, quoted or indirectly quoted
someone who said :
>
>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.
Look up the ball manufacturer on the net. Send an email asking for the
floor-rating of their weapons..
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.
Ingo R. Homann
Chris Lamb wrote:
> 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.
Yes, but i meant to prove that there is no better solution than this!
Ciao,
Ingo
Roedy Green
wrote, quoted or indirectly quoted someone who said :
>
> 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.
But everybody knows a glass ball will break even if dropped from 3
feet, unless it is some special glass.
Chris Uppal
> > 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?
One way to think of it, consider a series of possible algorithms:
First: start at the ground floor, drop the ball, go up one
flight, repeat until it breaks. This takes n+1 throws to discover that the
ball breaks on floor n (zero based).
Second. Instead of going up one flight each time, go up two. Then
use ball two to discover the exact floor. This roughly halves the number of
throws.
Third. Instead of going up one flight each time, go up three. This roughly
cuts the number of throws in three. However we may now have to make two throws
with ball 2.
... etc...
If we call the number of flights in each version of the algorithm f and the
average number of throws that results from using that version t, then we have
that roughly:
t = ( N/f + f - 1 ) / 2
which comes to a minimum when f = sqrt(N), at that point t = sqrt(N) - 1/2.
Another way to think of it, which I consider intuitively obvious[*] is that the
optimum comes when both balls are doing the same amount of work -- when the
amount of information (in the sense of information theory) yielded by ball 1 is
the same as that yielded by ball 2. That will happen if (on average) they are
used to explore the same number of possibilities. (Ball 1 chooses one group
from sqrt(N) groups of floors, ball 2 chooses one floor from sqrt(N) floors in
a group.) If this "explanation" is true at all, then I think it gives a deeper
insight into what's going on.
([*] NB: "intuitively obvious" == "I'm not even remotely close to having a
proof")
-- chris
Chris Uppal
> 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.)
The distribution is unknown -- we don't have enough data to compute it (even if
we were better physicists than me). For instance, the balls could have been
chosen randomly from a population that had been carefully pre-selected so that
the breaking-height varied uniformly over 0-99. OTOH, we could create a
physically realistic model of how the breaking height depended on thing like
the balls' shells' thicknesses, the number and severity of manufacturing flaws,
etc. We then assume some physically plausible distribution functions for these
parameters, and plug those into our model, and derive a distribution for the
breaking-height. Or there again, we might assume that the balls had been
carefully selected to have uniformly varying (over some range) mass, and that
would yield a different distribution again. No matter what we do, we can't
derive anything without making /some/ assumptions.
BTW, even if the balls' breaking heights do vary uniformly, I don't think the
problem specified that the floors were all the same height ;-)
> 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%27s_law
I think that if the breaking-height distribution is "completely unknown" then
we can't say /anything/.
I strongly suspect that Benford's law is irrelevant unless we make further (and
implausible) assumptions -- I can't prove it though (not least because I
haven't yet understood why Benford's law ever holds).
-- chris
Chris Uppal
> No really: you explained very clearly the (IMHO optimal) solution,
> thanks for that!
Sadly, I suspect that I got the arithmetic wrong. The overall idea is correct,
but I think I miscounted some of the possibilities. Also I'm not sure that
starting by dropping a ball from the ground floor is optimal. I'll get back
with corrections when I've worked them out.
-- chris
Ingo R. Homann
Andrea Desole wrote:
> Ingo R. Homann wrote:
>
>> 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
Yes, but even if every other of your cases had O(0), then your total
worst case would be 49/2 and your total best case would be 25/2 - which
is both not as good as mine solution!
>> 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
OK, I do not count that exactly... ;-)
>> 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.
Yes, but you did not convince me that your kind of binary search is
adequate.
> Still, it would be nice to use the first ball to eliminate as many
> possibilities as possible before it breaks
Strange logic: Then you could do a linear search only with the first
ball, completely ignoring the second ball!
>> 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?
Yes: With both balls, I want to get the same "amount" of information.
Although my thoughts are not totaly correct, as Thomas explained in his
posting from 16:44:
"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)."
And shit - he's damn right! That means... ehh... yes, was does it mean?
My idea is good - but obviously not good enough! Or is it? Or not?
>> 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 :-(
OK, now the same with a different cost measure:
...
???
Ciao,
Ingo
Andrea Desole
>
> One way to think of it, consider a series of possible algorithms:
>
> First: start at the ground floor, drop the ball, go up one
> flight, repeat until it breaks. This takes n+1 throws to discover that the
> ball breaks on floor n (zero based).
>
> Second. Instead of going up one flight each time, go up two. Then
> use ball two to discover the exact floor. This roughly halves the number of
> throws.
>
> Third. Instead of going up one flight each time, go up three. This roughly
> cuts the number of throws in three. However we may now have to make two throws
> with ball 2.
>
> ... etc...
>
> If we call the number of flights in each version of the algorithm f and the
> average number of throws that results from using that version t, then we have
> that roughly:
> t = ( N/f + f - 1 ) / 2
> which comes to a minimum when f = sqrt(N), at that point t = sqrt(N) - 1/2.
nice one
>
> Another way to think of it, which I consider intuitively obvious[*] is that the
> optimum comes when both balls are doing the same amount of work -- when the
> amount of information (in the sense of information theory) yielded by ball 1 is
> the same as that yielded by ball 2. That will happen if (on average) they are
> used to explore the same number of possibilities. (Ball 1 chooses one group
> from sqrt(N) groups of floors, ball 2 chooses one floor from sqrt(N) floors in
> a group.) If this "explanation" is true at all, then I think it gives a deeper
> insight into what's going on.
I was trying to think in the same way, but I was not able to convince
myself. The symmetry argument creates some doubts when I think that ball
1 is more "important" than ball 2, in the sense that ball 1 has to
determine the range of values of ball 2.
I am probably looking at the problem in the wrong way
Dimitri Maziuk
>
> 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.
Easy: O(1). Drop balls from 100th floor. If they break, the answer
is "floor 100", otherwise it's "they don't".
> 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.
Assuming perfectly sherical rocks of uniform density, easy again:
"Thank you for your time. I do not believe I'd like to work here".
Dima
--
Well, lusers are technically human. -- Red Drag Diva
Bent C Dalager
Thomas Hawtin <use...@tackline.plus.com> wrote:
>
>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).
I doubt you could do that as it would tell you that floor 82 is twice
as hard on the balls as floor 81, and this is unlikely to be the case.
Cheers
Bent D
--
Bent Dalager - b...@pvv.org - http://www.pvv.org/~bcd
powered by emacs
Andrea Desole
>> Still, it would be nice to use the first ball to eliminate as many
>> possibilities as possible before it breaks
>
> Strange logic: Then you could do a linear search only with the first
> ball, completely ignoring the second ball!
right. Sorry, I should have said as many possibilities as possible as
fast as possible, that is, with the smallest number of throws.
That's why I thought of the binary search
>
> Yes: With both balls, I want to get the same "amount" of information.
>
> Although my thoughts are not totaly correct, as Thomas explained in his
> posting from 16:44:
>
> "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)."
>
> And shit - he's damn right! That means... ehh... yes, was does it mean?
I didn't read that one. He has a point. So you should choose 10,
10+sqrt(90) = (more or less) 19, 19+sqrt(81) = 28,...
Chris Lamb
I was just expressing formally what we were discussing. No need to
break my balls!
Um. Er.
Chris
Oliver Wong
>
> I was trying to think in the same way, but I was not able to convince
> myself. The symmetry argument creates some doubts when I think that ball 1
> is more "important" than ball 2, in the sense that ball 1 has to determine
> the range of values of ball 2.
> I am probably looking at the problem in the wrong way
The symmetry is important in that you essentially have two chances. If
you screw up (i.e. if the ball breaks), then you've lost one of your chances
to determine the secret number that the client wnats you to determine.
Using the previously described family of algorithms, the first ball will
tell you which "bucket" (the 1st floor to 10th floor bucket, or the 11th
floor to 21st floor bucket, etc.) the secret number lies in, and the second
ball will pick out the exact number within that range.
The more work you do with the first ball, the smaller the buckets are,
and the less work you need to do with the second ball.
The less work you do with the first ball, the bigger the buckets are,
and the more work you need to do with the second ball.
You want to minimize the sum of the work done with the first ball and
the work done with the second ball, hence there's some "balancing" to be
done. I also suspect that when the amount of work done (in the metric of
"how many drops are done") of the two balls are exactly equal, that's gives
you the optimal sum, but I can't prove this either.
- Oliver
Scott....@gmail.com
The basic flaw I saw in the original, increase by 10 then drop, is that
your search area increases. First ball, max drops is 10, next is 11,
next is 12, next is 13...all the way up to 19. What I did was try to
equalize the search:
(starting at 0 - 99)
First ball is dropped at 15, worst case of 16.
Next ball is dropped at 29(+14), worst case of 16
Then 42(+13), 54(+12), 65(+11), 75(+10), 84(+9), 92(+8), and finally
99(+7)
All of these(except the final drop), has a worst case of 16 drops. If I
did my math right, which I probably didn't knowing me.
If anyone finds any flaws in my logic and math, please, let me know.
Oliver Wong
<Scott....@gmail.com> wrote in message
news:1139426041.9...@g44g2000cwa.googlegroups.com...
Good job. I didn't think anyone could beat 20 (or 19, whatever), but it
looks like there is indeed a way to beat it. But you have an "off by one"
error. Let's say you drop the first ball at 15, and it doesn't break, but
then you drop it at 29 and it does break. Then you would drop the second
ball at 16, 17, 18, etc. up to 28, which gives 13 extra drops in the worst
case, not 14.
Also, if you drop it at 92, and it doesn't break, then you drop it at 99
and it does break, then you have a worse case of 93,94,95,96,97,98 or 6
extra drops. However, if you had dropped it at 92 and it didn't break, and
dropped it at 96, then your worst case would be 4 extra drops (93,94,95 if
it broke vs 97,98,99,100 if it didn't break), which is better than your 6.
- Oliver
Scott....@gmail.com
be 3, as I went 0-99 in true programmer fasion.
I think I also have a start on a general formula for the solution, my
math notation and verbage was never my strong point so let me see if I
can state this:
x = max number of drops required (what we want)
y = upper bound (our case 100 here)
q >= lower bound for the problem (in our case problem lower bound is 1,
but q turns out to be 7 or so)
x = summation(q to x) Where summation <= y AND x <=(q - x)
I think I got that right.
Eric Sosman
Adam Maass wrote On 02/08/06 03:42,:
> "im" wrote:
>
>>On Wed, 08 Feb 2006 00:44:55 +0000, nospam wrote:
>>
>>
>>>Hi...All,
>>>
>>> Recently I had been attending some interviews(almost after 10years)
>>>for Java Developer/Lead position. At each interview, 75% of the alloted
>>>time was spend was on problem solving sessions or checking the
>>>analytical skills. I was just wondering what has prompted the companies
>>>to include such a session & give so much importance to it.?
>>>
>>
>>Could you please post some examples of specific problems you had to solve
>>during the interviews?
>>
>
>
> 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.
>
>
> 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.
If we accept Tony Morris' thesis that one should prefer
skill over experience, the ability to answer these questions
might well DISqualify the answerer. Both are old chestnuts,
which an experienced person has almost certainly encountered
before. (Besides: The "usual" answer for questions like #2
will not work for the question as stated! The person to hire
is not the guy who "solves" #2, but the guy who says it can't
be done.)
Oliver Wong
"Eric Sosman" <Eric....@sun.com> wrote in message
news:dsdjk6$3lq$1...@news1brm.Central.Sun.COM...
>
> If we accept Tony Morris' thesis that one should prefer
> skill over experience, the ability to answer these questions
> might well DISqualify the answerer. Both are old chestnuts,
> which an experienced person has almost certainly encountered
> before. (Besides: The "usual" answer for questions like #2
> will not work for the question as stated! The person to hire
> is not the guy who "solves" #2, but the guy who says it can't
> be done.)
In practice, a "reasonable" interviewerwould probably not be so
interested in whether or not the person being interviewed got the right
answer, but would rather want to follow the interviewed person's thought
process. Asking relevant questions like "Is the difference between the mass
of a heavier rock and a lighter rock known?" will probably give you "bonus
points" for the interview.
Obviously, the optimal strategy is to research as many of these problems
as possible and memorize their solutions, but then, in the interview,
pretend you are encountering them for the first time, and work through them
a little slowly in front of the interviewer.
- Oliver
Monique Y. Mudama
>
>
> Obviously, the optimal strategy is to research as many of these
> problems as possible and memorize their solutions, but then, in
> the interview, pretend you are encountering them for the first
> time, and work through them a little slowly in front of the
> interviewer.
>
I don't think most engineers are good enough actors to pull this off
successfully.
--
monique
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
Chris Uppal
[me:]
> > The distribution is unknown -- we don't have enough data to compute it
>
> Finding a probability distribution in this case is the field
> of applying a so called "uninformative prior". See
>
>
http://en.wikipedia.org/wiki/Prior_probability_distribution#Uninformative_priors
Thanks for the reference, I hadn't come across this field before.
I must say that -- judging /only/ from the WP article -- it strikes me as a
mixture of hogwash and bafflegab. That's probably unfair, but I'm not
qualified to judge the more esoteric arguments. I don't see how from a
position of zero knowledge, one can deduce /anything/. If -- say -- arguments
based on (in some sense) maximising entropy appear to allow one to make
deductions, then it seem necessary that what's really happening is that the
assumptions built into the entropy concept and/or the idea of (in some sense)
maximising it, are being unpacked.
Still interesting, though, so thanks again...
-- chris
Tony Morris
news:p7nGf.184344$AP5.139134@edtnps84...
>
> "Tony Morris" <n...@telling.you> wrote in message
> news:43e9...@quokka.wn.com.au...
> >
> > 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
>
>
Not exactly - more precisely, I am saying that the orthodox definition of
"experience" is contrived.
I know many people on this planet, but certainly nowhere near the entire set
(6.5 billion or whatever it is).
Of the people I know, there are a few who can learn things 1000 times faster
than I can (conservative estimate), and likewise, there are people who can
learn things 1000 times slower than I can (again, conservative estimate).
Assuming this premise, this means that given a very small subset of the
entire living human population, there exists in general, one person (A) who
can learn 1,000,000 times faster than another person (B). So what then is
the definition of "experience"? Arguably, person B will learn in 1,000,000
years what person A will learn the same thing in 1 year. Does this mean that
person A has 1,000,000 times more experience than person B? Certainly a more
plausible definition than many others that I have heard. I acknowledge that
this logic contains many holes, but my observations come out to around
something similar as well. That is, yes I can take an "experienced" person
and watch their problem solving skills crumble. This also fits my theory
that this industry is based in more ways than one, on "how things appear"
instead of "how things are", however, there has been a recent slight (very
slight in the greater scheme of everything) shift toward "how things are".
--
Tony Morris
http://tmorris.net/
Dimitri Maziuk
> "Oliver Wong" <ow...@castortech.com> wrote in message
> news:p7nGf.184344$AP5.139134@edtnps84...
>>
>> "Tony Morris" <n...@telling.you> wrote in message
>> news:43e9...@quokka.wn.com.au...
>> >
>> > 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?
>>
Here's "how things are": given the balls problem upthread,
Skill sez:
Problem statement implies that 1) balls will break when dropped off
*some* floor of the building, and 2) laws of "falling apple" physics
apply, so probability of the ball breaking grows with floor number.
Therefore, probability of balls breaking when dropped from 100th
floor is 100%.
Furthermore, the question is not to "find the lowest-numbered floor
such that balls dropped from it will break", it's "which floor" --
meaning "find *any* floor such that ..."
Ergo, the answer is "Floor 100", and time taken to find it is O(0).
Experience sez:
I've seen "This should never happen" error message on my screen
enough times to know I should take both balls up to 100th floor,
drop them, and watch them actually break before I commit to the
answer.
Therefore, the answer if "Floor 100", and time is O(1).
That's how analytical problem solving skills of an experienced
developer fail to arrive at infinitely faster O(0) solution.
HTH
Dima
--
The wombat is a mixture of chalk and clay used for respiration. -- MegaHal
Adam Maass
Folks, thank you for your enormously entertaining responses, both serious
and non-serious. I was asked these -- one apiece -- at two different
companies, and they obviously seemed to like my responses since I got offers
from them both.
-- Adam Maass
Roedy Green
Dalager) wrote, quoted or indirectly quoted someone who said :
>I doubt you could do that as it would tell you that floor 82 is twice
>as hard on the balls as floor 81, and this is unlikely to be the case.
Some elementary physics here.
Energy available to break the ball
e = m * v * v;
m = mass, v = velocity
v = a * t;
d = 1/2 * a * t * t;
a = acceleration due to gravity, t = time.
Do a little algebra and you have the energy at any distance (floor).
Still if the ball breaks at 3 feet, none of this means anything.
These same physics will have you questioning Bush's story about he
collapse of the World Trade Towers. They fell too fast in the early
part of the fall for gravity to account for it.
Roedy Green
<chris...@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly
quoted someone who said :
>One way to think of it, consider a series of possible algorithms:
You could tackle this with a Monte Carlo approach.
You write a simulating that picks a random ball strength and random
tests (subject to a little common sense) where to drop the next
ball).
Let it run for a few hours and keep say the most successful 100 runs.
Look at what it does. See if you can come up with an algorithm to
repeat that performance, not using just blind luck.
Roedy Green
<adam.nos...@comcast.net> wrote, quoted or indirectly quoted
someone who said :
>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.
Depends what you mean by a scale. With a balance scale the answer is
trivial. Put a rock from one pile in the left pan and a rock from the
other in the right.
In the olden days, when I was in high school, you used to weigh things
with a box of weights and a pair of tweezers and a balance scale with
a knife edge balanced on an agate or some similar hard smooth stone.
Ingo R. Homann
Andrea Desole wrote:
>>> Still, it would be nice to use the first ball to eliminate as many
>>> possibilities as possible before it breaks
>>
>> Strange logic: Then you could do a linear search only with the first
>> ball, completely ignoring the second ball!
>
> right. Sorry, I should have said as many possibilities as possible as
> fast as possible, that is, with the smallest number of throws.
> That's why I thought of the binary search
Yes, but because of the fact that in "some" cases you cannot re-use the
ball, binary-search is not exactly what we need.
>> Yes: With both balls, I want to get the same "amount" of information.
>>
>> Although my thoughts are not totaly correct, as Thomas explained in
>> his posting from 16:44:
>>
>> "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)."
>>
>> And shit - he's damn right! That means... ehh... yes, was does it mean?
>
> I didn't read that one. He has a point. So you should choose 10,
> 10+sqrt(90) = (more or less) 19, 19+sqrt(81) = 28,...
You are correct that the steps have to be adjusted in the way you do it.
BUT: I had choosen my initial start value of '10' with the assumption in
mind that the steps are being *not* adjusted. That assumption was wrong
- and so, the initial value of '10' is wrong!
So, it get's complicated (but I think/hope, now this is really correct):
1. It's optimal, when you maximally do as many steps with the first ball
as you will maximally need with the second ball (that was my first
assumption, which I did not explicitely formulate).
2. If in step 0 the (start-)value is s0, which can be calculated by an
unknown function s0=f(100), then the second value is s1=s0+f(100-s0).
(That's what you are saying - and I agree.)
Continuing that, we generally get s_i = s_(i-1) + f(100-s_(i-1))
Now we know (or "think"), that f must somehow be a square-function with
an (linear?) "adjustment" factor. We further know that s0 - 1 is the
worst case of throws we need with the second ball. The worst case for
the first ball is that w for which the following equation is correct: s_w=99
Considering assumption 1, this should be enough to calculate the function f.
Problem solved. ;-)
Ciao,
Ingo
Ingo R. Homann
your specific solution convinces me. But you must explain your formula:
> x = summation(q to x) Where summation <= y AND x <=(q - x)
For me, summation(q to x) is q + (q+1) + (q+2) + ... + (x-1) + (x)
But obviously, you mean something different.
Ciao,
Ingo
Andrea Desole
the only thing I can say is that we should minimize the average, not the
worst case. I assume in this case average is also smaller, but the fact
that we now have a variable step makes the problem more complicated
Andrea Desole
>
> Yes, but because of the fact that in "some" cases you cannot re-use the
> ball, binary-search is not exactly what we need.
yes, that's a problem I pointed out already. But I had the idea of using
the first ball to rule out as many floors as possible in the smallest
number of drops. Maybe a binary search is not the best approach in that
sense
>
> You are correct that the steps have to be adjusted in the way you do it.
>
> BUT: I had choosen my initial start value of '10' with the assumption in
> mind that the steps are being *not* adjusted. That assumption was wrong
> - and so, the initial value of '10' is wrong!
>
> So, it get's complicated (but I think/hope, now this is really correct):
>
> 1. It's optimal, when you maximally do as many steps with the first ball
> as you will maximally need with the second ball (that was my first
> assumption, which I did not explicitely formulate).
>
> 2. If in step 0 the (start-)value is s0, which can be calculated by an
> unknown function s0=f(100), then the second value is s1=s0+f(100-s0).
> (That's what you are saying - and I agree.)
>
> Continuing that, we generally get s_i = s_(i-1) + f(100-s_(i-1))
>
> Now we know (or "think"), that f must somehow be a square-function with
> an (linear?) "adjustment" factor. We further know that s0 - 1 is the
> worst case of throws we need with the second ball. The worst case for
> the first ball is that w for which the following equation is correct:
> s_w=99
I would rather go for the "we think" option :-)
Andrea Desole
>
> Folks, thank you for your enormously entertaining responses, both serious
> and non-serious. I was asked these -- one apiece -- at two different
> companies, and they obviously seemed to like my responses since I got offers
> from them both.
I just tried a search on google for "analytical interview questions",
and I found a couple of cool links with some more questions:
http://www.acetheinterview.com/cgi-bin/qanda.cgi?action=topics&number=3
http://www.geekinterview.com/Global-Interview-Questions/Infosys/Analytical
there are a few interesting questions
Thomas Hawtin
>
> And shit - he's damn right! That means... ehh... yes, was does it mean?
It means we're hopeless at these puzzles. Imagine if we were in an
interview situation. It follows absolutely that we must be hopeless
programmers.
Oops
Tom Hawtin
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
Ingo R. Homann
I would say "there are few interesting questions" ;-)
Many questions are quite easy or at least well-known. (This one here
with the two balls I dint know before, and I think it is very interesting!)
Some questions do not have anything to do with 'logic', although they
are also quite interesting to guess: "How many kilometers of roads are
there in the US?"
Or, my favourite:
"If you could remove any of the 50 states, which state would it be and why?"
As a German, I would say: There are only 15 states, and it's obvious
that everyone (*) would remove Bavaria.
*=(Including the Bavarians themselves! :-)
Reason: They are unable to speak German. ;-)
(OK, the Bavarians would name a different reason...)
(Oh - but then I also would have to remove "Sachsen-Anhalt" where my
wife comes from! Bad idea! ;-)
Ciao,
Ingo
Ingo R. Homann
Thomas Hawtin wrote:
> It means we're hopeless at these puzzles. Imagine if we were in an
> interview situation. It follows absolutely that we must be hopeless
> programmers.
>
> Oops
It might also mean that we give new ideas to out employer which did not
consider that the solution is much more complicated than he thought
(which, I think, is often the case ;-)
Ciao,
Ingo
Andrea Desole
> Many questions are quite easy or at least well-known. (This one here
> with the two balls I dint know before, and I think it is very interesting!)
i like the mirror one
>
> Some questions do not have anything to do with 'logic', although they
> are also quite interesting to guess: "How many kilometers of roads are
> there in the US?"
yes, that one is strange. The toaster one is also a bit strange.
The second link has probably more interesting questions
>
> Or, my favourite:
>
> "If you could remove any of the 50 states, which state would it be and
> why?"
>
> As a German, I would say: There are only 15 states, and it's obvious
> that everyone (*) would remove Bavaria.
I wouldn't. I used to live in Munich.
Ingo R. Homann
Andrea Desole wrote:
> i like the mirror one
Yes (I skipped that before), that is really good - since every child
asks that but most parents are unable to give the correct answer.
>> Some questions do not have anything to do with 'logic', although they
>> are also quite interesting to guess: "How many kilometers of roads are
>> there in the US?"
>
> yes, that one is strange.
I have *no* idea. Only large roads, but also small streets?
I also have nothing to compare (e.g. I have no idea how many kilometers
of roads or rails are in Germany).
Perhaps 500.000 kilometers in total (including every small street)? No,
I think this is not enough... 1 mio?
> The toaster one is also a bit strange.
Yes!
>> Or, my favourite:
>>
>> "If you could remove any of the 50 states, which state would it be and
>> why?"
>>
>> As a German, I would say: There are only 15 states, and it's obvious
>> that everyone (*) would remove Bavaria.
>
> I wouldn't. I used to live in Munich.
I tought, <prejudice>all</prejudice> Bavarians think that Bavaria is
much better than "the rest of Germany" (which they like to call
"Northern Germany") and would be glad if it was an own country. ('We are
proud to be a 'Freistaat'." ;-)
You are not a native Bavarian (*), are you?
(*) Then you are no Bavarian at all! ;-)
Ciao,
Ingo
Ingo R. Homann
And I like this one:
"How many points are there on the globe where by walking one mile south,
one mile east and one mile north you reach the place where you started."
Hint: The "obvious" answer ("There is one point.") is *wrong*!
Ciao,
Ingo
Andrea Desole
>
> Yes (I skipped that before), that is really good - since every child
> asks that but most parents are unable to give the correct answer.
really? I never really cared until I saw the question
>
> I have *no* idea. Only large roads, but also small streets?
and mainly: why would someone ask a question like that? It doesn't look
that analytical to me, and it depends on so many factors
>
> I tought, <prejudice>all</prejudice> Bavarians think that Bavaria is
> much better than "the rest of Germany" (which they like to call
> "Northern Germany") and would be glad if it was an own country. ('We are
> proud to be a 'Freistaat'." ;-)
True. Bavaria is Bavaria
>
> You are not a native Bavarian (*), are you?
no. I was just there for a few years
Roedy Green
<ne...@desole.demon.NOSPAMPLEASE.nl> wrote, quoted or indirectly quoted
someone who said :
>I just tried a search on google for "analytical interview questions",
>and I found a couple of cool links with some more questions:
Where do you think the interviewers get these? The surely don't make
them up.
Roedy Green
>True. Bavaria is Bavaria
I was reading a book about Hitler. He apparently was very embarrassed
about his Bavarian accent. I guess it had something of the status of
an Applachian accent in the USA.
Andrea Desole
why?
Andrea Desole
>
> Where do you think the interviewers get these? The surely don't make
> them up.
probably not, at least not many of them. There are books and magazines
full with these games. I specially remember Martin Gardner's book, many
years ago. Man, that was tough.
Thomas Hawtin
> Ingo R. Homann wrote:
>>
>> "How many points are there on the globe where by walking one mile
>> south, one mile east and one mile north you reach the place where you
>> started."
>>
>> Hint: The "obvious" answer ("There is one point.") is *wrong*!
>
> why?
Hint: Go south a mile, travel around the world a few times, go north a mile.
I believe there are regular "around the world" races.
Andrea Desole
> Hint: Go south a mile, travel around the world a few times, go north a
> mile.
This would imply that you are able, one mile from the north pole (or
somewhere in the world), to travel around the world in less than one
mile. I'm not sure it's possible.
Chris Lamb
> Hmm, All I can think of is N pole. Starting 1 mile N of the South pole
> results in a degenerate point. Having walked 1 mile S you are at the pole,
> 1 mile E is a null operation, and any direction is N so you could end up
> anywhere in a ring 1 mile N of the S pole. You _could_ reach where you
> started, but likely not.
Arrgh. Just realised that there are a set of discrete orbitals round each
pole where each orbit circumf divides a mile eactly.
Chris
Chris Lamb
Hmm, All I can think of is N pole. Starting 1 mile N of the South pole
results in a degenerate point. Having walked 1 mile S you are at the pole,
1 mile E is a null operation, and any direction is N so you could end up
anywhere in a ring 1 mile N of the S pole. You _could_ reach where you
started, but likely not.
Chris
Ingo R. Homann
No, the idea is the following:
About 1300 meters from the S pole (P0), you can go 1000m towards south
pole (P1). If you walk 1000 m towars east, you will stand again at point
P1. If you now go 1000 m north, you will be at qour start-point P0.
This also works when the "diameter" (sorry, I'm not sure if this is the
correct word in English) of the earth at point P1 is 500 m or 333m or
250m...
Ciao,
Ingo
Jens Auer
> I was reading a book about Hitler. He apparently was very embarrassed
> about his Bavarian accent. I guess it had something of the status of
> an Applachian accent in the USA.
This is getting off-topic now, but just to mention: Hitler's origin is
Austria, so he should have had an austrian accent.
Andrea Desole
>
> No, the idea is the following:
>
> About 1300 meters from the S pole (P0), you can go 1000m towards south
> pole (P1). If you walk 1000 m towars east, you will stand again at point
> P1. If you now go 1000 m north, you will be at qour start-point P0.
>
> This also works when the "diameter" (sorry, I'm not sure if this is the
> correct word in English) of the earth at point P1 is 500 m or 333m or
> 250m...
got it. Thanks
Scott....@gmail.com
numbers.
In this case, it would be 7+8+9+10+1+12+13+14+15 = 99 And, the number
of steps(x - q, I had this wrong originally) is less than x(15). So, x
= 15, y = 100 q = 7.
To try and put it in English. Find some numbers x and q, where q is
less than x, and the summation of q to x is less than or equal to y.
And, the distance between q and x is less than the distance between 0
and x.
Ingo R. Homann
Scott....@gmail.com wrote:
> Thats what I mean, I think. It would probably be best to show with
> numbers.
>
> In this case, it would be 7+8+9+10+1+12+13+14+15 = 99
OK, lets make it with numers:
For me, summation(q to x) with q=1 means:
1+2+3+4+5+...+x
How do you get the numers 7+8+9+10+1+12+13+14+15?
Ciao,
Ingo
Oliver Wong
<Scott....@gmail.com> wrote in message
news:1139429060.1...@g47g2000cwa.googlegroups.com...
> Yeah, noticed that after I hit post, and my worst case up at 92 would
> be 3, as I went 0-99 in true programmer fasion.
>
> I think I also have a start on a general formula for the solution, my
> math notation and verbage was never my strong point so let me see if I
> can state this:
>
> x = max number of drops required (what we want)
> y = upper bound (our case 100 here)
> q >= lower bound for the problem (in our case problem lower bound is 1,
> but q turns out to be 7 or so)
>
> x = summation(q to x) Where summation <= y AND x <=(q - x)
I didn't understand this formula, but I took your idea, and improved on
it slightly:
Assuming the floors go from 1 to 100 (and not 0 to 99)...
First ball dropped at 14, if it breaks, then I need 13 extra drops with
the second ball. Otherwise, drop it at 27 (12 extra drops if it breaks),
then at 39 (11 extra drops), 50 (10 extra drops), 60 (9 extra drops), 69 (7
extra drops), 76 (6 extra drops), 92 (5 extra drops). Then drop it at 96. If
it breaks, then there's 3 extra drops (93, 94, 95). If it doesn't, then
there's 4 extra drops (97,98,99,100)
I've reduced the worst case to 14 total drops.
- Oliver
Oliver Wong
"Andrea Desole" <ne...@desole.demon.NOSPAMPLEASE.nl> wrote in message
news:8fc7a$43eb0694$d468cb3c$24...@news.support.net...
I think we should minimize the worst case, not the average, because we
only need to determine the floor once, right? If we had to determine the
floor millions of time, then yes, it would make sense to minimize the
average, because on average, we would benefit more. But if we only perform
the experiment once, we want an upper bound of how long the experiment would
take before we can call it a day and all go home.
- Oliver
Oliver Wong
"Roedy Green" <my_email_is_post...@munged.invalid> wrote in
message news:o3klu19sangjfkuce...@4ax.com...
> On Wed, 8 Feb 2006 16:37:13 -0000, "Chris Uppal"
> <chris...@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly
> quoted someone who said :
>
>>One way to think of it, consider a series of possible algorithms:
>
> You could tackle this with a Monte Carlo approach.
>
> You write a simulating that picks a random ball strength and random
> tests (subject to a little common sense) where to drop the next
> ball).
>
> Let it run for a few hours and keep say the most successful 100 runs.
> Look at what it does. See if you can come up with an algorithm to
> repeat that performance, not using just blind luck.
Instead of a random ball, how about an "adversarial ball", whose
behaviour changes depending on what your algorithm is? That is, you say in
advance what height you want to drop it from, and then the ball either
breaks or doesn't break, depending on which is worse for you. Obviously, it
has to choose in a "fair" way so that if dropping from height X doesn't
break it, then dropping from height Y where Y <= X never breaks it either.
- Oliver
Oliver Wong
"Roedy Green" <my_email_is_post...@munged.invalid> wrote in
> On Wed, 8 Feb 2006 00:42:07 -0800, "Adam Maass"
> <adam.nos...@comcast.net> wrote, quoted or indirectly quoted
> someone who said :
>
>>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.
>
> Depends what you mean by a scale. With a balance scale the answer is
> trivial. Put a rock from one pile in the left pan and a rock from the
> other in the right.
I believe this only solves the problem if the number of piles = 2.
- Oliver
Scott....@gmail.com
(Sum(13) = 91, so it wont work, but Sum(14) = 105)
Scott....@gmail.com
summation was from 7-15
Andrea Desole
>
> I think we should minimize the worst case, not the average, because we
> only need to determine the floor once, right? If we had to determine the
> floor millions of time, then yes, it would make sense to minimize the
> average, because on average, we would benefit more. But if we only perform
> the experiment once, we want an upper bound of how long the experiment would
> take before we can call it a day and all go home.
That depends. If you minimize the average you minimize the likelihood
that your experiment is taking longer.
If you have a worst case of 20 but 99% of the times I prefer a worst
case of 30 1% of the times, if the other 99% I get 5. That way I have
99% chance to do that only in 5.