Daily Coding Problem 24
Welcome back with another problem to solve! Today, we are dealing with eggs falling from rooftops with this really nice problem, which will involve two possible solutions: one pretty naive and a more clever one. This last one will also give us the chance to talk about a quite famous algorithm.
As always, today’s problem is provided by the wonderful newsletter
Enough talking then; let’s see the problem!
The Problem
This problem was asked by Goldman Sachs in a job interview. Let’s see the problem.
You are given
Nidentical eggs and access to a building withkfloors. Your task is to find the lowest floor that will cause an egg to break, if dropped from that floor. Once an egg breaks, it cannot be dropped again. If an egg breaks when dropped from thexthfloor, you can assume it will also break when dropped from any floor greater thanx.Write an algorithm that finds the minimum number of trial drops it will take, in the worst case, to identify this floor.
For example, if
N = 1andk = 5, we will need to try dropping the egg at every floor, beginning with the first, until we reach the fifth floor, so our solution will be5.
So, we are given some eggs to throw from different floors of a building. We are sad that from a certain floor (which we will call targetFloor ), eggs thrown out do not break when falling to the ground.
From that floor to every floor below it, the eggs won’t break when thrown out from the window. What we are asked to do is to find an efficient method to find the targetFloor .
As anticipated, we’ll see two methods to solve this: a really simple one, which will brute force the solution out, but it will not be efficient. The second one will be much more efficient and will try to solve the problem by breaking the least number of steps.
It will also give us the chance to talk about a really famous and important algorithm; one of those you need to know to do … basically anything!
Setting Up the Environment
To start off, we need to set up a bit of environment, namely the building and the targetFloor . To create the building, we simply create an array containing the numbers of the floors, from the ground floor to the nᵗʰ floor. Then, we generate a random number which will be our targetFloor .
We’ll write this problem in Go once again: simple enough to be readable, but complex enough to understand the inner mechanics.
https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go
We first create the array which will serve as our building: we can give it the size we want, the greater the size, the higher the building will be. After that, we create an instance of the targetFlor using the math/rand module built in Go.
Basically, we create a new random integer between 0 and the height of the building (… the length of the array :D) using as a source the current time.
The Brute Force Solution
Of course, the simplest solution possible would be to throw each egg on each floor out, so to see on which floor the eggs start to break. Since we have a variable containing that information, one could simply do a for loop to solve the problem:
https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go
While this is the simplest solution, it is unfortunately highly inefficient. Imagine if the right floor is the top one: one must break 100.000 eggs to solve the problem: that would be a huge omelet but quite a waste!
Generally speaking, this solution has a time complexity of O(n) because the complexity of the solution grows linearly to the complexity of the input problem. This is not the most efficient solution we could think of though.
An Efficient Solution
Let’s think about an efficient solution then. Instead of walking floor by floor breaking each egg on each floor, we could take a guess and, based on the result of that guess, adjust the next guess.
Here’s an example: suppose we have a building with 10 floors, and the targetFloor is floor 7 (we don’t know that, of course). We could take the following guesses:
Basically, we guess that the targetFloor is the middle floor of the building. We throw the egg from there, and the possible outcomes are two:
- the egg breaks, meaning that we are too high. We can discard the floor higher than this one, included, and keep going on with our guesses.
- The egg does not break, meaning that we are too low or on the correct floor. We discard every floor lower than this one, included, and
Given this, we now take another educated guess about the middle floor or the “remaining” building, and apply the same strategy seen above. We can go on with this approach until we are left with one floor.
If you happen to recognize this approach, you are perfectly right: this is simply a binary search applied to a “real world” problem. Binary search is a simple and neat divide-and-conquer algorithm, meaning that at each step, the size of the problem gets halved until we find the solution.
This means that this algorithm, compared to the previous one, is way faster. Let’s see the code!
https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go
Let’s take a deeper look. The binary search function takes in 4 arguments:
overArray, an array of integers, which is the building we are looping over;
bottom, the bottom index of the building;
top, the top floor index of the building;
breakFloor, the variable holdingtargetFloorto check if we can find it in the building.
After that, we loop over the building while bottom is lower than top : in binary search, when the two positional arguments interlace and swap, it means that the searched element was not found.
Therefore, if the algorithm ends up in this situation, the loop ends and we return -1 , meaning that the element we are looking for was not present in the array. If we are still searching for the element, we apply what is shown in the image above.
We calculate the middlePoint element as the floor between bottom, and top and we check if middlePoint == breakFloor . If it is, we return the middlePoint as result.
If it’s not, we adjust bottom or top accordingly: if middlePoint is greater than breakFloor , it means we are too high on the building so we lower our prediction by setting the top possible floor to middlePoint — 1 .
If middlePoint is smaller than breakFloor , we adjust our bottom by setting is as middlePoint+1 .
Now to check everything, in the main function, we generate the environment as before, and create a new variable called bsFloor which will hold our result.
To confirm that our algorithm brought us to the right result, we print out both bsFloor and targetFloor , which was previously generated randomly.
Time Complexity
As we anticipated before, this algorithm is way faster than the linear one. Since we halve the building at each step, we can find the correct floor in log₂(n) where n is equal to len(building) .
This means that the time complexity of this algorithm is O(log(n)). To give you some comparison between the linear solution and this last one, if the building has 100 floors, the linear algorithm takes in the worst case 100 iterations, while the binary search algorithm takes log₂100 = 6.64, so 7 iterations.
Also, this last one is increasingly more efficient than the linear one because the more the building grows, the more the binary search is efficient. For a building with 1.000.000.000 floors, the linear one takes 1.000.000.000 steps, while the binary one takes log₂1.000.000.000 = 29.9, so 30 steps. A huge improvement!
Conclusion
This is it! I hope you enjoyed the article as much as I had fun trying to solve the challenge! If so, please leave a clap or two, it would be a great support! If you like these types of articles and want to see more, follow the page as I release this type of content every time I can.
Finally, if you found this article interesting or helpful and would like to contribute by offering a coffee, feel free to do so on my
And, as always, thanks for reading!
Nicola
Also published here