Michael Kozakov blogged about a twitter interview question

puddles.py

# twitter interview question: http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
#
# single pass
# recursive
#
# for debug and understanding, the function acc(umulate) returns the array of water levels in each bin.
 
def acc(land, i=0, leftmax=0):
        
    leftmax = max(leftmax, land[i])
    puddles, rightmax = acc(land, i+1, leftmax) if i < len(land)-1 else ([], 0)
    rightmax = max(rightmax, land[i])

    water = min(leftmax, rightmax) - land[i]    # compute current water
    water = max(water, 0)
    
    return [water] + puddles, rightmax          # water heights, rightmax
    
    
# usage
land = [7,0,5,0,7,0]
puddles, _ = acc(land)
print(puddles)
print(sum(puddles))