{{ message }}

Instantly share code, notes, and snippets.

# shaobohou/gist:7231961

Last active Dec 26, 2015
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 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 commented Oct 30, 2013

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

### thisvar commented Oct 30, 2013

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

### shaobohou commented Oct 30, 2013

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

### thisvar commented Oct 30, 2013

 oh, my fault, I probably missed last digit