Best way to search for a saturation value in a sorted list

Question

A question from Math Battle. This particular question was also asked to me in one of my job interviews.

" A monkey has two coconuts. It is fooling around by throwing coconut down from the balconies of M-storey building. The monkey wants to know the lowest floor when coconut is broken. What is the minimal number of attempts needed to establish that fact? "

Conditions: if a coconut is broken, you cannot reuse the same. You are left with only with the other coconut

Possible approaches/strategies I can think of are

• Binary break ups & once you find the floor on which the coconut breaks use upcounting from the last found Binary break up lower index.
• Window/Slices of smaller sets of floors & use binary break up within the Window/Slice (but on the down side this would require a Slicing algorithm of it's own.)

Wondering if there are any other way to do this.

Answer 1

The best solution I know is 2*sqrt(n). Drop the first coconut from sqrt(n), 2*sqrt(n),... up to n (or until it breaks). Then drop the second one from the last known "safe" point, in one floor increments until it breaks. Both stages take at most sqrt(n) throws.

Edit: You can improve the constant within O(sqrt(n)), see comment by recursive. I think that the first step should be around sqrt(2*n) and decrease by 1 with each throw, so that the last step (if the breaking height is actually n) is exactly 1. Details to be figured out by readers :)

Answer 2

A binary search is not the answer, because you only get one chance to over-estimate. Binary search requires log m maximum over-estimations.

This is a two phase approach. The first is to iterate over the floors with relatively big steps. After the first coconut breaks, the second phase is to try each floor starting after the last safe floor.

The big steps are roughly sqrt(m), but they are bigger early, and smaller later because if the first coconut breaks early, you can afford more iterations in the second phase.

StepSize = (minimum s such that s * (s + 1) / 2 >= m)
CurrentFloor = 0

While no coconuts broken {
    CurrentFloor += StepSize
    StepSize -= 1

    Drop coconut from CurrentFloor
}

CurrentFloor -= StepSize + 1

While one remains coconut unbroken {
    CurrentFloor += 1
    Drop remaining coconut from CurrentFloor
}

// CurrentFloor is now set to the lowest floor that will break the coconut, 
// using no more total drops than the original value of StepSize

Answer 3

Interview questions like this are designed to see how you think. So I would probably mention a O(N^0.5) solution as above, but also I would give the following discussion...

Since the coconuts may have internal cracking over time, the results may not be so consistent to a O(N^0.5) solution. Although the O(N^0.5) solution is efficient, it is not entirely reliable.

I would recommend a linear O(N) solution with the first coconut, and then verify the result with the second coconut. Where N is the number of floors in the building. So for the first coconut you try the 1st floor, then the 2nd, then the 3rd, ...

Assuming both coconuts are built structurally exactly the same and are dropped on the exact same angle, then you can throw the second coconut directly on the floor that the first one broke. Call this coconut breaking floor B.

For coconut #2, you don't need to test on 1..B-1 because you already know that the first cocounut didn't break on floor B-1, B-2, ... 1. So you only need to try it on B.

If the 2nd coconut breaks on B, then you know that B is the floor in question. If it doesn't break you can deduce that there were internal cracking and degradation of the coconut over time and that the test is flawed to begin with. You need more coconuts.

Given that building sizes are pretty limited, the extra confidence in your solution is worth the O(N) solution.

As @Rafał Dowgird mentioned, the solution also depends on whether the monkey in question is an African monkey or a European monkey. It is common knowledge that African monkeys throw with a much greater force. Hence making the breaking floor B only accurate with a variance of +/- 2 floors.

To guarantee that the monkey doesn't get tired from all those stairs, it would also be advisable to attach a string to the first coconut. That way you don't need to do 1+2+..+B = B*(B+1)/2 flights of stairs for the first coconut. You would only need to do exactly B flights of stairs.

It may seem that the number of flights of stairs is not relevant to this problem, but if the monkey gets tired out in the first place, we may never come to a solution. This gives new considerations for the halting problem.

We are also making the assumption that the building resides on earth and the gravity is set at 9.8m/s^2. We'll also assume that no gravitation waves exist.

Answer 4

Since it's an interview question, consider

1. The expensive operation is the monkey going up and down the stairs, not tossing the coconut. Thinking about it this way, the 'linear' approach is actually N².

2. The energy imparted to the coconut by falling is roughly proportional to the height of the drop. If the shell is broken after absorbing some amount of energy in ALL of it's falls ...