[PopeDotNinja]

I don't know anything about dynamic programming in the manner that it is taught. I also don't get why it's even a thing (which is to say I haven't studied the topic, and haven't yet seen a need to do so).

Someone recently gave me the egg dropping problem in an interview. I had never seen it before, but the answer eas obvious, and I verbally stated the solution in under a minute. I asked the interviewer if I could out the Log N solution, which I believe was essentially a binary search on a logical list of length N using a bit of looping or recursion. He asked me to go through the process of explaining it, and I really didn't see the point. He knew the answer, and he knew the answer, and he asked me to implement the simplest solution first. To me, that was the solution I started, but that wasn't good enough. The interview went downhill from there.

I later googled the answer, saw people explaining some overly complex matrix-y shenanigans, and I tuned out.

Maybe I'm missing something?

[Jach]

Talk is cheap, code is what matters. But maybe the interviewer wanted to save time not writing an incorrect solution if he believed your approach was wrong and you could talk yourself out of it? Did you get to step through how your solution would arrive at the number 14 given 2 eggs and 100 floors? And if you wrote it out, would it produce that number? (Personally I have no idea what you mean with the binary search approach, what is your logical list since doing it on the list of floors is wrong? But I've not thought about the egg dropping problem in a long time and have only seen the DP approach.)

It might of course be that the interviewer only knew one way to solve it, any other way was therefore wrong. Or admitting they don't understand a demonstrated other way shows weakness, so is also wrong. I'd be perfectly happy to receive rejections from companies with those sort put in charge of interviewing.

[wizzairflyer]

A funny trick is to ask this question but first give the candidate an infinite amount of eggs. Once he succeeds, ask the question with only 2 eggs. That might explain the binary search answer.

[PopeDotNinja]

The approach would have been easier way for me to answer the question. I wrote something like that to guesstimate the number of git commits on GitHub a project I didn't have time to clone a few years back (I think it was Linux). Basically I started at page 1, then went to 2, 4, 8, 16, etc. When I hit a 404, I went back 50% of the way to the previous number (e.g. if it was page 1024, the previous was 512, then I went to 768). If 50% was a 404, go to back midpoint of lower range (e.g. midpoint of 512 and 768). It if was legit, go to midpoint of upper range (e.g. between 768 and 1024). Wash/rinse/repeat. It was a fun exercise to burn some time on a slow day. If someone actually wants to see the code, reply to this comment and I'll find it, or write it again.

Now I want to go back and study up on that dynamic programming stuff again! Yay inspiration!

[bspammer]

I don't know what version of the problem you solved, but generally you are limited by the number of eggs you are allowed to use. Say you have a hundred floors and 1 egg, binary search would drop an egg from the 50th floor, have it break (assuming the key floor was <50), and then promptly fail.