An interview for a programmer is an excellent experience, during which many excellent tasks arise. Google recruiters also like my favorite task: You work in a 100-story building and you have two identical eggs. You need to determine the highest floor from which you can drop an egg and not break it. Find an algorithm that minimizes the number of shots in the worst case scenario.

We can make several assumptions:

If an egg does not break when falling from a particular floor, then it will not break when falling from lower floors.

If the egg does not break, it can be used again.

Broken egg must be excluded.

The drop effect is the same for all eggs.

If an egg breaks during a fall, then it will break when it falls from a higher floor.

Many people have written an algorithm to solve this problem (and we will write our own), but there is a simple solution.

Simple answer

An easy way to get the minimum floor is to start throwing an egg from the first floor, then from the second and so on. When the egg breaks, we will know that this is the floor we are looking for. This is a reliable method, but in the worst case, it will require 100 shots.

It is important to note that this is the only algorithm available when you have only one egg. So you need to start using it when you break the first egg.

Intuitive answer

Our first egg must be used to divide one hundred floors into smaller ranges as efficiently as possible. Then the first egg must be thrown from the 1 / n floor, for example, ⅓. Then the algorithm will look like this: Throw an egg from the 33rd floor. If it breaks, check the first 32 floors with the second egg.

If it does not break, throw the egg from 33 + (67 * ⅓) = 55 floors. If it breaks, check floors 34–55 with the second egg.

…

In the worst case, for ⅓ (33, 24, …) it is 33. So we can find the ideal n that optimizes the number of throws using dynamic programming. This is a good solution that shows programmer thinking, but it is not optimal.

The perfect solution

To understand the ideal solution, we need to understand the equality that is used to calculate the number of shots in the worst case: Where F (n) is the next floor from which we throw the first egg.

If we introduce such a variable:

That equality would look like this:

The optimal solution is when all the arguments of this maximum function are equal. How to achieve this? If you look from the end, the last D (n) should be 1, because this is how we get to the point where only one floor remains for the first egg. Then D (n-1) should be equal to 2, because it differs in one throw of the first egg.

If the first egg was dropped for the last time from the 99th floor, then before that we will get 99-2 = 97, 97-3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 and 9 floors. This is the best solution! So, in the worst case, we will need to make 14 shots (the smaller difference is 13, but we need to make another shot from the 9th floor).

Interview for a programmer: check

Ok, we have a solution, and we can calculate it without any help. Time to check it is correct. To do this, we will write a simple program on Kotlin. First, let’s express how to calculate the number of shots for a solution. When we have 2 or fewer floors, we need to make as many throws as there are floors left. Otherwise, we must use the equality already presented: fun maxThrows (floorsLeft: Int, nextFloor: Int): Int =

if (floorsLeft <= 2) floorsLeft

else maxOf (nextFloor, bestMaxThrows (floorsLeft – nextFloor) + 1)

We used the bestMaxThrows function. This is a hypothetical function that returns the number of rolls if the following solutions are ideal. Here’s how we can define it: fun bestMaxThrows (floorsLeft: Int): Int =

maxThrows (floorsLeft, bestNextStep (floorsLeft))

We have delegated the responsibility of optimizing the next floor of the bestNextStep function. She gives us the best next step. We can define it simply – when there are 2 floors or less left, we will throw an egg from the first floor. Otherwise, we need to check all the options and choose the best one.

val bestNextStep (floorsLeft: Int): Int =

if (floorsLeft <= 2) 1 else (1..floorsLeft) .toList() .minBy { maxThrows(floorsLeft, it) }!! Эта функция использует maxThrows, поэтому у нас возникает повторение. Это не проблема, потому что, когда bestNextStep вызывает MaxThrows, она всегда вызывает ее со значением меньше, чем floorsLeft (потому что nextFloor всегда больше нуля). Перед использованием добавим буферизацию для ускорения вычислений: val bestNextStep: (Int) -> Int = memorise {floorsLeft -> if (floorsLeft <= 2) 1

else (1..floorsLeft)

.toList ()

.minBy {maxThrows (floorsLeft, it)} !!

} fun maxThrows (floorsLeft: Int, nextFloor: Int): Int =

if (floorsLeft <= 2) floorsLeft else maxOf(nextFloor, bestMaxThrows(floorsLeft – nextFloor) + 1) val bestMaxThrows: (Int) -> Int = memorise {floorsLeft -> maxThrows (floorsLeft, bestNextStep (floorsLeft))

} fun <V, T> memorise (f: (V) -> T): (V) -> T {

val map = mutableMapOf<V, T>()

return {map.getOrPut (it) {f (it)}}

} Now we can check if the function returns the same result that we calculated:

fun main (args: Array) {

print (bestMaxThrows (100)) // Prints: 14

} Good answer. Check the following steps:

fun main (args: Array) {

var floor = 0

while (floor <100) {

val floorsLeft = 100 – floor

val nextStep = bestNextStep (floorsLeft)

floor + = nextStep

print (“$ floor,”)

}

} The result: 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100, as we calculated.

Very promising

Now we have a good algorithm for solving similar problems. For example, we can modify it a bit to calculate the number of shots in the most likely scenario. We can check how the minimum number of shots will depend on the height of the building. Here is a graph with the answer to this question: Conclusion

Now you are better prepared, maybe the interview for the programmer at Google will be easier, but, more importantly, you are more familiar with general algorithmic thinking. This algorithm represents a good functional approach that can be used for various problems in our work.