Skip to content

Instantly share code, notes, and snippets.

@shaobohou shaobohou/gist:7231961
Last active Dec 26, 2015

Embed
What would you like to do?
turns out my initial one pass solution was wrong, here is a corrected two-pass solution to puzzle posted in http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
def water(heights):
vol = 0
currVol = 0
maxWall = 0
for h in heights:
if h>=maxWall:
# closed a puddle
vol += currVol
currVol = 0;
maxWall = h
else:
# extend current puddle
currVol += maxWall-h
# the remaining puddles
lastWall = 0
for h in heights[::-1]:
if h < maxWall:
if h < lastWall:
vol += lastWall-h
lastWall = max(lastWall, h)
else:
break
return vol
hs = [2,5,1,3,1,2,1,7,7,6]
hs2 = [2,7,2,7,4,7,1,7,3,7]
hs3 = [2,5,1,3,1,2,1,7,5,6]
print water(hs)
print water(hs2)
print water(hs3)
@bartkappenburg

This comment has been minimized.

Copy link

commented Oct 30, 2013

it doesn't work for the case:
2,5,1,3,1,2,1,7,5,6 (it should give 18)

@shaobohou

This comment has been minimized.

Copy link
Owner Author

commented Oct 30, 2013

Doh, you are right, guess I needed a second pass after all, oh well.

@thisvar

This comment has been minimized.

Copy link

commented Oct 30, 2013

bartkappenburg
It should give 17, as it seems to me )
If you picture it, you'll see.

@shaobohou

This comment has been minimized.

Copy link
Owner Author

commented Oct 30, 2013

Presumably the 7,5,6 at the end also holds 1 unit.

@thisvar

This comment has been minimized.

Copy link

commented Oct 30, 2013

oh, my fault, I probably missed last digit

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.