{{ message }}

Instantly share code, notes, and snippets.

# igor47/walls.py

Last active Jun 4, 2016
another solution to the problem found in this post about twitter interviewing: http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ this was on hacker news: https://news.ycombinator.com/item?id=6639839 the original post author solved it here: https://gist.github.com/mkozakov/59af0fd5bddbed1a0399 i use a state machine. this seemed like …
 #!/usr/bin/python def water(levels, second_pass = False): # sanity check if len(levels) < 2: return 0 # state machine filling = False h = 0 h_index = 0 total = 0 cur = 0 for i in xrange(1, len(levels)): # we can start filling once we see a first drop in level if not filling and levels[i] < levels[i-1]: filling = True h_index = i-1 h = levels[h_index] if filling: # we need to stop filling if level is above the original wall if levels[i] >= h: total += cur cur = 0 filling = False # otherwise, count this level as a puddle else: cur += h - levels[i] # close the final puddle by going backwards from -1 to h_index if not second_pass: final_puddle = [levels[l] for l in range(len(levels) -1, h_index, -1)] total += water(final_puddle, True) return total if __name__ == "__main__": testcases = [ ([1,0,1], 1), ([5,0,5], 5), ([0,1,0,1,0], 1), ([1,0,1,0], 1), ([1,0,1,2,0,2], 3), ([2,5,1,2,3,4,7,7,6], 10), ([5,1,0,1],1), # thanks https://news.ycombinator.com/item?id=6640085 ([2,5,1,2,3,4,7,7,6,3,5], 12), # thanks https://news.ycombinator.com/item?id=6640105 ] for case in testcases: w = water(case[0]) if w == case[1]: print "TRUE: %s holds %s" % (case[0], w) else: print "MISMATCH: %s holds %s (got %s)" % (case[0], case[1], w)

### llelf commented Oct 30, 2013

 [2,0,1]

### chrisdone commented Nov 13, 2013

 `````` ([2,5,1,2,3,4,7,7,6], 10), # ok ([6,7,7,4,3,2,1,5,2], 10), # fail ``````

### bourneagain commented Sep 10, 2014

 This seems to work ;) https://gist.github.com/bourneagain/0cb90851106756746933