Skip to content

Instantly share code, notes, and snippets.

@flowolf flowolf/gist:7247585
Last active Dec 27, 2015

Embed
What would you like to do?
simple python solution to puddle problem found here: http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
# Python solution to the puddle problem
# from: http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
#
# single pass, streaming capable. O(n), memory as much as wall size.
#
def calc_vol(a):
vol = 0
count = [0]
maxi = 0
last = 0
for w in a:
if w >= maxi:
print "new max!"
for i in range(maxi,w):
count.append(0)
maxi = w
else:
print "smaller than current max!"
for i in range(w,maxi):
count[i] += 1
print count
if w > last:
for i in range(0,w):
vol += count[i]
count[i] = 0
print "adding to vol = %d" % vol
last = w
print "volume is: %d" % vol
return vol
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.