A Twitter Interview Question

interview_q2.py

# Python solution for https://qandwhat.runkite.com/i-failed-a-twitter-interview/ 

# Actually the original implementation is as following which is done in n-pass:
def water_vol_orig(a):    
    lv = rv = -1
    result = lmax = rmax = l = 0
    r = len(a)-1 # no pass on array    
    while (l < r):
        lv = a[l]
        if lv > lmax:
            lmax = lv
            
        rv = a[r]
        if rv > rmax:
            rmax = rv
            
        if lmax >= rmax:
            result += rmax - rv
            r -= 1
        else:
            result += lmax - lv
            l += 1
    return result
 
# This implementation avoids the lookup for the max item in the array to finish in n-pass. 
# However, it is doing 3 comparisons inside the inner loop and in dynamic languages like Python/Java 
# indexed access to an array is expensive, using enumerators is far more effective. 
 
# So more efficient way of doing this in Python may be:
# 1) find the max item
# 2) approach to max item from left and right.
def water_vol_fast(a):
    
    def _imax(x): # find max in single pass, faster than max(..,itemgetter(..))
        max_idx = max_val = 0
        for i, v in enumerate(a):
            if v > max_val:
                max_val = v
                max_idx = i
        return max_idx
        
    def _volp(x): 
        max = result = 0        
        for e in x:
            if e > max:
                max = e
            else:
                result += max - e
        return result
        
    imax = _imax(a) # n-pass
    return _volp(a[:imax]) + _volp(reversed(a[imax:])) # n pass
 
# This version will have 2N comparisons(1N for finding max and 1N for calculating the volume) and no index 
# based access to any array.
# If these are profiled, one can see the difference:
# water_vol_orig takes 0.405603 CPU Secs, and water_vol will take 0.265202 which is nearly %80 faster.
import random 
a = [int(1000*random.random()) for i in range(10000)]
assert water_vol_orig(a) == water_vol_fast(a)