Skip to content

Instantly share code, notes, and snippets.

@DrewFitz
Last active December 27, 2015 02:49
Show Gist options
  • Save DrewFitz/7254644 to your computer and use it in GitHub Desktop.
Save DrewFitz/7254644 to your computer and use it in GitHub Desktop.
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
Copy link

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
Copy link
Author

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