[Clubber]

Uh, if you drop an egg out of the first floor window onto cement, it will break.

The answer should be a form of binary search, but since you only have two eggs, you'd have to do a sequential search from the bottom floor. You have one chance at a mistake, so I would almost say start with the 2nd floor, but I know it will break on the first floor.

I don't see how that in any way gauges programming what so ever.

[blueline]

>The answer should be a form of binary search, but since you only have two eggs, you'd have to do a sequential search from the bottom floor. You have one chance at a mistake, so I would almost say start with the 2nd floor, but I know it will break on the first floor.

yeah, sorta. essentially you partition the 100 floors into some number of groups (i forget what partition length is optimal) and drop the first egg at each segment until it breaks, then go linearly from the previous one

[taurath]

A quick naive not completely optimal but still relevant solution:

Since you have 2 eggs you can start on the 33rd floor. It breaks you can use the 2nd egg from 1st to 32nd floor.

If it doesn't break, use the first egg on the 66th floor. If it does break, the answer is between 33 and 65, if it doesn't the answer is between 66 and 100. That cuts the maximal testing time time from splitting at 1/2 (1st egg at flr 50), to 1/3rd.

To optimize further, since in the bad case we'd have to search up to 34/35 floors, you can mathmatically find a number where you split the drops at an interval (IIRC the "real" optimal answer is 14, then 13, then 12, etc), which means you're doing less explicit checking.

At 14 - i, you have 10 drops to find a range of 13 - i floors in which the optimal path is found. So instead of a worst case of 35, you have a worst case of around 17.

I find the best way to approach this sort of problem is to first find one optimization, and then use the same process to find if there are further optimizations.

[sireat]

It's not the worst type of puzzle except if you do not know of a solution it might take a while to figure it out.

It does relate to programmer's ability to amortize worst case running time.

Once you realize that 1 egg requires linear search you just have to realize that with 2 eggs you have to decrease the level increase by 1 on each success.

Of course those must be some crazy genetically modified eggs.

[Clubber]

>It's not the worst type of puzzle except if you do not know of a solution it might take a while to figure it out.

I would guess the interviewer probably rates people who have memorized the solution far higher than people who have never encountered it and solved it with their brains.