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

@isaiah-perumalla isaiah-perumalla 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