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 , which you can subscribe to for free to get your daily coding challenge too. Check it out, and try to solve your problems too! Daily Coding Problem 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. identical eggs and access to a building with floors. 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 the floor, you can assume it will also break when dropped from any floor greater than . You are given N k xth x Write an algorithm that finds the minimum number of trial drops it will take, in the worst case, to identify this floor. and , 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 be . For example, if N = 1 k = 5 5 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 ), eggs thrown out do not break when falling to the ground. targetFloor 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 . 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 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 using the module built in Go. targetFlor math/rand 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 is floor 7 (we don’t know that, of course). We could take the following guesses: targetFloor Basically, we guess that the is the middle floor of the building. We throw the egg from there, and the possible outcomes are two: targetFloor 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 applied to a “real world” problem. Binary search is a simple and neat algorithm, meaning that at each step, the size of the problem gets halved until we find the solution. binary search divide-and-conquer 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: , an array of integers, which is the building we are looping over; overArray , the bottom index of the building; bottom , the top floor index of the building; top , the variable holding to check if we can find it in the building. breakFloor targetFloor After that, we loop over the building while is lower than : in binary search, when the two positional arguments interlace and swap, it means that the searched element was not found. bottom top Therefore, if the algorithm ends up in this situation, the loop ends and we return , 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. -1 We calculate the element as the floor between , and and we check if . If it is, we return the as result. middlePoint bottom top middlePoint == breakFloor middlePoint If it’s not, we adjust or accordingly: if is greater than , it means we are too high on the building so we lower our prediction by setting the possible floor to . bottom top middlePoint breakFloor top middlePoint — 1 If is smaller than , we adjust our by setting is as . middlePoint breakFloor bottom middlePoint+1 Now to check everything, in the function, we generate the environment as before, and create a new variable called which will hold our result. main bsFloor To confirm that our algorithm brought us to the right result, we print out both and , which was previously generated randomly. bsFloor targetFloor 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 . 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. O(log(n)) 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 page! Ko-fi And, as always, thanks for reading! Nicola Also published here

Too Long; Didn't Read

Making security fun one episode at a time

When You Have to Throw Eggs From the Rooftop: Daily Coding Problem

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

When You Have to Throw Eggs From the Rooftop: Daily Coding Problem

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES