Amazon Interview Question
Software DevelopersCountry: India
1. Compute leftmax and rightmax arrays. leftmax[i] denotes max in arr[0..i]. rightmax[i] denotes max in arr[i..n-1].
2. compute extra[] for each tower.
extra[i] = ( (min(leftmax[i], rightmax[i]) - arr[i] > 0) ? arr[i] : min(leftmax[i], rightmax[i]))
3. compute the ans as in the normal algorithm.
ans += ( (min(leftmax[i], rightmax[i]) - arr[i] > 0) ? min(leftmax[i], rightmax[i]) - arr[i] > 0 : 0)
4. now the final result would be ans + firstmax(extra) + secondmax(extra).
Please let me know if there is anything wrong in this approach.
# Let's define a function to capture rainwater
arr = [2,0,4,0,6,0,2,0,1,0]
def trap_rain_water(arr):
#Initialize water variable
water = 0
#Iterate through array and find out volume of water captured at current bar
for i in range(1, len(arr)-1):
vol_at_current_bar = min(max(arr[:i]), max(arr[i:])) - arr[i]
if vol_at_current_bar > 0:
water += vol_at_current_bar
return water
}
- divm01986 October 20, 2018