2 widgets, 100 floors, and a smash

Question posted in Computer Software on 05 2010
Rate question difficulty level 1 Votes
You have 2 identical widgets (toys, boxes, remotes, book, w/e) you wish to test. The test you are concerned with is related to impact rating.
The test will be conducted by dropping one a widget out of various windows in a 100 story building. Once the widgets are broken, you cannot obtain more and testing cannot continue. You must identify what is the lowest possible floor that you can drop one of the widgets from that will cause it to break.
What process would you follow to conduct this test? What is the worst case scenario for how many times you must drop a widget from a window?
 
 
1 Answer
 
n is a variable. It will indicate the worst case scenario and also the starting floor.
This is a sequence. You want the sum of the series to be >= 100 (lets call this X in case the number of floors change).
To find n, solve ((n*(n+1))/2) = X. Take the ceiling of n.
for our case this is ceiling(n(n+1)) = 200.
and our worst case scenario is 14 drops.
Our starting floor is 14.

The process to conduct the test:
Start at the 14th floor. Drop the widget.
If it breaks, take the second widget to the first floor and work your way up to the 13th floor until the second widget breaks. (if the second widget does not break by the 13th floor, then you know 14 is the lowest floor from which you can throw the widget that will cause it to break)
If it does not break, move up 13 floors (from the 14th to the 27th floor).
Repeat this process, decrementing the amount of floors by you climb between each non-break.
Assuming the widget does not break, you would visit floors:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
If the first widget breaks at any of these floors, simply take the second widget to the floor which is one above the last floor you successfully dropped the first widget from without it breaking (that is if you broke it on floor 69, go back down to 61 and work your way up to 68.

This is easy to recalculate if the amount of floors involved change. However if the amount of widgets provided change, your series will change as well.

05/25/2010
 
 
Add an answer*
 
Your name
Email
 
Company: Microsoft
Location: Charlotte , North Carolina , United States
Efficient Efficiency Algorithm Software Develop Development

add a question

arrow_blue


Now hiring!
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------