Problem-02:
There is a 100
story building; you can climb up and down the building through the fire
escalators. You are given two crystal balls.
These crystal
balls will break at a certain height. Therefore, If you release them from a
floor that is higher than their breaking height, they will break. If you
release them from a floor below their breaking height, they will resist the
fall.
You are asked
to write an algorithm to find this height. For the exercise to be successful,
at least one crystal ball must remain intact after the execution of the
algorithm.
You are
expected to provide an answer in pseudocode Java (code resembling Java).
Solution:
Here's a possible solution in Java
pseudocode:
int findBreakingHeight(int
totalFloors, int crystalBallHeight) {
int interval = (int) Math.sqrt(crystalBallHeight * 2);
int floor = interval;
while (floor < totalFloors) {
if (isCrystalBallBroken(floor,
crystalBallHeight)) {
return findBreakingHeight(floor -
interval + 1, floor);
}
floor += interval;
interval--;
}
return floor - interval + 1;
}
boolean isCrystalBallBroken(int
floor, int crystalBallHeight) {
// Assume there is a function to determine whether the crystal ball will
break at a given height.
// Return true if the crystal ball breaks, false otherwise.
return checkHeight(floor) > crystalBallHeight;
}
The findBreakingHeight
function takes two arguments: the total number of floors in the building and
the breaking height of the crystal ball. It uses a binary search-like approach
to find the highest floor from which the crystal ball won't break.
The
algorithm starts by dropping the crystal ball from a height of interval,
where interval is the square root of twice the crystal ball's breaking
height. If the ball breaks, the function recursively calls itself on the
interval of floors from the previous floor - interval + 1 to the current
floor floor. If the ball doesn't break, the algorithm increases the
floor by interval and decreases interval by 1 to narrow the
search range.
The is
CrystalBallBroken function determines whether the crystal ball will break
at a given floor by calling a hypothetical checkHeight function.
At
the end, the function returns the highest floor from which the crystal ball
won't break.