Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
twitter water fill problem, solution to problem described here https://medium.com/@bearsandsharks/i-failed-a-twitter-interview-52062fbb534b
def water_collected(A):
sortedHeights = [(x,i) for i,x in enumerate(A)]
sortedHeights.sort(key=lambda v: v[0]*-1) #sort in decreasing order
leftIdx = rightIdx = sortedHeights[0][1]
waterLevel = 0
for i in xrange(1,len(A)):
x,idx = sortedHeights[i]
if idx > rightIdx:
water = (idx-rightIdx-1)*x
rightIdx = idx
elif idx < leftIdx:
water = (leftIdx-idx-1)*x
leftIdx = idx
else:
water = -x
waterLevel += water
return waterLevel
assert water_collected([2, 5, 1, 2, 3, 4, 7, 7, 6]) == 10
assert water_collected([2, 5, 1, 3, 1, 2, 1, 7, 7, 6]) == 17
assert water_collected([2, 7, 2, 7, 4, 7, 1, 7, 3, 7]) == 18
assert water_collected([6, 7, 7, 4, 3, 2, 1, 5, 2]) == 10
assert water_collected([2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4]) == 26
assert water_collected( [2, 5, 1, 2, 3, 4, 7, 5, 6]) == 11
@isaiah-perumalla

This comment has been minimized.

Copy link
Owner Author

commented Aug 13, 2015

n log(n) solution with o(n) space, but simple solution

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.