Last active
December 26, 2015 23:39
-
-
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/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Doh, you are right, guess I needed a second pass after all, oh well.
bartkappenburg
It should give 17, as it seems to me )
If you picture it, you'll see.
Presumably the 7,5,6 at the end also holds 1 unit.
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
it doesn't work for the case:
2,5,1,3,1,2,1,7,5,6 (it should give 18)