Skip to content

Instantly share code, notes, and snippets.

@thulka thulka/puddles.py
Last active Dec 28, 2015

Embed
What would you like to do?
Michael Kozakov blogged about a twitter interview question
# 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.