Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
executable file 21 lines (18 sloc) 667 Bytes
#!/usr/bin/python
#You are given two egges. You have access to a 100-story building.
#Figure out the highest floor of a 100-story building an egg can drop without breaking
#1. Implement a binary search.
#It's a dynamic programming problem, suppose the first egg drops from ith fl,
#if it is broken: linearly try from 1-(i-1)
#else try (100-i) fl with two eggs
N = 100
results = [(0,0),(1,1)]
for i in range(2, N+1):# from 2nd fl to 101 fl the first egg.
minNum, minPos = N +1, -1
for j in range(1, i+1):
temp = 1 + max(j-1, results[i-j][0])
if temp < minNum:
minNum, minPos = temp, j
results.append((minNum, minPos))
for result in results:
print result