Re: analytical Skill for Java Development


"Adam Maass" <adam.nospam.maass@xxxxxxxxxxx> wrote in message
news:NeednZ7aGsJBM3TenZ2dnUVZ_tWdnZ2d@xxxxxxxxxxxxxx

"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


.

Relevant Pages

  • Re: analytical Skill for Java Development
    ... You have two identical glass balls; when dropped from a certain height, ... in words the algorithm you would use. ... are an infinite number of rocks in each pile. ... Describe an algorithm to determine which pile contains the heavier ...
    (comp.lang.java.programmer)
  • Re: analytical Skill for Java Development
    ... You have two identical glass balls; ... in words the algorithm you would use. ... The rocks in each pile are identical. ...
    (comp.lang.java.programmer)
  • Re: Question about shock sensitive spheres
    ... gave my nerves a workout) and I painted the composition onto hollow plastic balls instead since I have no rocks handy, but anyways, after I let them dry overnight I took one and threw it against my rock firepit to see what, if any, reaction there is going to be....nothing....absolutely nothing except the fact the composition just either splattered onto the ground in little pieces or stuck to the firepit. ... Unless using plastic balls instead of rocks made a difference? ... It sounds like they're not dry for one thing. ...
    (rec.pyrotechnics)
  • Re: analytical Skill for Java Development
    ... At each interview, 75% of the alloted ... 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. ... The rocks in each pile are identical. ... There are an infinite number of rocks in each pile. ...
    (comp.lang.java.programmer)
  • Re: analytical Skill for Java Development
    ... At each interview, 75% of the alloted ... in words the algorithm you would use. ... The rocks in each pile are identical. ...
    (comp.lang.java.programmer)