[Community puzzle] Google Interview - The Two Egg Problem


#21

You're right, I modified the test case #5 so there is no test/validator with N <= 2 to not break previous solutions.


#22

Hi,

It seems easy to implement with correct mathematical solution, but considering only case for 2 eggs as case 0 and one loop over one parameter in equation I get answer that I've hard-coded solution for 2 validators. What might needed to be changed?


#23

This change doesn't solve the issue. You have to change the problem statement like an egg can be broken if it's thrown from the first floor. Otherwise, answers for all other test cases should be reduced by 1 too. We can examine a small example.


#24

Solved. All validators after including case zero in different way worked.


#25

I checked, all testcases works with this rule or not!
But i agree, we can specify it in the statement.


#26

This is a maths problem, not the kind of things I'm expecting on codingame. It shouldn't have been accepted as a puzzle, in my opinion.


#27

Algorithms are math. Where do you set the limit?


#28

To me, it's not a good argument. The entire field of computer science is, to some degree, 'math'.

Can't really answer your question precisely, I'm just a bit mad because I had to relearn stuff I was glad I could put behind me when I started coding (ie: lovely things like square roots of quadratic equations). A coding problem that can be solved by one line of code which definitely looks like a math equation is not fun at all (again, to me). Once you have the 'math solution', there's absolutely no challenge left.
And it's a google interview question, which are all known to be kinda 'gotcha' questions.


#29

You can solve some puzzles only with maths even if they do not look like a pure maths puzzle. Look at the solutions!


#30

I'm not arguing yet. I'm merely trying to understand your position.

Right now, you're saying "CS is math" and "math problems shouldn't be allowed in". You know where this is going, and you'll understand we find this a little surprising.


#31

For example, I solved the deleted puzzle with the motorcycles only with pure maths.


#32

I myself am trying to understand my position :p.

I just don't like this type of puzzle, especially on a coding platform. I want to get better at coding, not better at finding the correct equation that will solve the problem.

Anyway, let's forget about it, I have plenty more coding challenges to do.


#33

I actually solved this (more or less) without using maths. I interpreted it as a minimax game where I select where to drop the egg and try to minimize the number of drops, while my opponent chooses whether or not the egg breaks and tries to maximize the number of drops.

If I only have one egg left, I have to drop it at every floor except for the bottom one to find the point.
When I drop an egg at floor k, it will tell me if the target is above or below k. Now we have the same problem with k-1 floors and one fewer egg if it breaks and with n-k+1 floors if it doesn't.

This problem only has 2*n different states, so with memoization/dynamic programming, the solution is O(n^2) = (n states * try n different values of k for each), which is definitely fast enough for 2<= n<=1000.

You can do many further optimizations without using much maths, but it's not really needed. Point is, you can make this into a programming challenge if you want to. :slight_smile:


#34

On the other hand, It would probably have been more fun if it was stated more like a game. For example, if the challenge was to write a bot which each turn gives the best floor to drop the egg at and then gets back if it breaks or not. Maths solutions, which instantly calculates the answer would still be possible, but it invites more programming oriented solutions and it feels more like a game.


#35

At that point you pretty much have the Batman puzzles, but easier.


#36

Without my math background, I don't genuinely know how I could build up a valid answer with an algorithmic approach.
The exercise must be really good in interviews to test and examine how one's think but I don't think it is suited for a codingame puzzle.

Nonetheless, the problem was really interesting and thank you OlogN for it.


#37

Dynamic Programming :slight_smile:


#38

Hello :slight_smile:

I disapprove the fact that codes use a wrong formula and are validated.
Ok. The result is the same until there are not 10000 floors or more.
These ugly solutions are acceptable for a physicist.
But for computer science, where the code is used, re-used, re-re-used, etc, one day, someone will take that source code that is wrong, and may cause a disaster.

When finishing the puzzle, i have been shocked to see solutions of others that are not correct.

Thank you for your attention. :wink:

Flo


#39

As I said, you can use a minimax algorithm with dynamic programming to constructively reach the answer. Once you see the problem as a two player game it becomes fairly easy to find an algorithmic solution.


#40

If you don’t know the trick, you can still solve it by defining the problem recursively and using memoisation. That’s what I did.