Skip to content

Instantly share code, notes, and snippets.

@shaobohou
Last active December 26, 2015 23:39
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shaobohou/7231961 to your computer and use it in GitHub Desktop.
Save shaobohou/7231961 to your computer and use it in GitHub Desktop.
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
Copy link

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

@shaobohou
Copy link
Author

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

@thisvar
Copy link

thisvar commented Oct 30, 2013

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

@shaobohou
Copy link
Author

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

@thisvar
Copy link

thisvar 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