{{ message }}

Instantly share code, notes, and snippets.

# DrewFitz/puddle.py

Last active Dec 27, 2015
Twitter Interview Solution Problem described here: http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ It's messy, but it solves it in one pass
 def puddle(xs): result = 0 unresolved = [] for i in range(len(xs)): y = xs[i] if len(unresolved) > 0: while y > unresolved[-1][0]: z = unresolved.pop()[0] if len(unresolved) == 0: break g, j = unresolved[-1] g = min(g, y) result += (g-z) * (i-j-1) if len(unresolved) == 0: unresolved.append((y, i)) continue if y <= unresolved[-1][0]: unresolved.append((y, i)) else: unresolved.append((y, i)) return result a = [2,5,1,3,1,2,1,7,7,6] b = [2,5,1,2,3,4,7,7,6] c = [2,4,1,1,2,1,5,4,3,5,4] print puddle(a) # 17 print puddle(b) # 10 b.reverse() print puddle(b) # also 10! print puddle(c) # 14 (2 puddles)

### chrisdone commented Nov 13, 2013

 This breaks if you reverse the order of the elements: ``````print puddle([2,5,1,2,3,4,7,7,6]) → 10 print puddle([6,7,7,4,3,2,1,5,2]) → 11 ``````

### DrewFitz commented Jan 8, 2014

 AH! Good catch! It was an errant < vs <= bug that caused it to not add unresolved walls of the same height back-to-back. (Hopefully) fixed now!