Microsoft

www.microsoft.com
Engaged Employer

## Interview Question

Software Development Engineer In Test Intern Interview(Student Candidate) Redmond, WA

# You have a building with 100 stories. You also have two

glass balls. You can drop the glass balls as many times as you want before they break. How can you find the floor at which they start breaking with the fewest number of drops?
Tags:
brain teaser

0

Not truly a brain teaser because the answer is mathematical.

Interview Candidate on Apr 21, 2012
1

If you have N stories, you use the first glass ball to increment by sqrt(N) stories. Once that ball breaks, you use your second to go to the level of sqrt(N) below where it broke, and increment floor by floor. You know it must break somewhere in that group of sqrt(N) stories. I believe this method gets you a runtime of O(n^0.5).

Alex on May 2, 2012
1

search for "two egg problem". its a minimization of maximum regret problem
http://www.datagenetics.com/blog/july22012/index.html

moataz on Oct 4, 2012