Skip to content

Instantly share code, notes, and snippets.



Last active Dec 27, 2015
What would you like to do?
Twitter Interview Solution Problem described here: 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:
g, j = unresolved[-1]
g = min(g, y)
result += (g-z) * (i-j-1)
if len(unresolved) == 0:
unresolved.append((y, i))
if y <= unresolved[-1][0]:
unresolved.append((y, i))
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
print puddle(b) # also 10!
print puddle(c) # 14 (2 puddles)

This comment has been minimized.

Copy link

@chrisdone 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

This comment has been minimized.

Copy link
Owner Author

@DrewFitz 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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.