January 2, 2018

How to solve the Google recruiters’ puzzle about throwing eggs from a building

The problem: You work in a 100 floor building and you get 2 identical eggs. You need to figure out the highest floor an egg can be dropped without breaking. Find an algorithm that is minimizing number of throws in the worst-case scenario.

We can make a few assumptions:
  • If an egg doesn’t break when dropped from some floor, then it will not break when dropped from any lower floors.
  • An egg that survives a fall can be used again.
  • A broken egg must be discarded.
  • The effect of a fall is the same for all eggs.
  • If an egg breaks when dropped, then it would break if dropped from a higher floor.

Most people writes some algorithms to solve this puzzle (and we will do it too), but there is actually an easy solution.

Simplest answer
The simplest way to obtain the minimal floor is to throw an egg from the first floor, then from the second and so on. This way when the egg is finally broken then we will know that this is the floor. This is a reliable algorithm, but in the worst-case scenario it would take 100 throws.

The important thing to notice is that it is the only reliable algorithm when you have only one egg. So you need to start using this algorithm when you break the first egg.

No comments:

Post a Comment