Note: This coding challenge was asked in Goldman Sach coding round and in many other technical job interviews.
Given an array of non-negative integers representing the elevations from the vertical cross-section of a range of hills, determine how many units of snow could be captured between the hills.
See the example array and elevation map below.
Output: In this example, 13 units of snow (*) could be captured.
This problem is similar to the “maximum level of water it can trap after the rain”.
min(left[i], right[i]) - arr[i]for each element.
We are implementing above algorithm using Python programming.
def computeSnowpack(arr): # Todo: Implement computeSnowpack len_arr = len(arr) left = [arr]*len_arr left_max = arr for i in range(1, len_arr): left_max = left_max if left_max>arr[i] else arr[i] left[i] = left_max right = [arr[-1]]*len_arr right_max = arr[-1] for i in range(len_arr-2, -1, -1): right_max = right_max if right_max>arr[i] else arr[i] right[i] = right_max sum = 0 for i in range(len_arr) : sum += min(left[i], right[i]) - arr[i] return sum def doTestsPass(): """ Returns True if all tests pass. Otherwise returns False. """ tests = [ [[2, 1, 3, ], 1], [[0,1,3,0,1,2,0,4,2,0,3,0], 13], [[2,1,3,0,1,2,0,4,2,0,3,0], 14], ] for test in tests: if not (computeSnowpack(test) == test): return False return True if __name__ == "__main__": if( doTestsPass() ): print( "All tests pass" ) else: print( "Not all tests pass")
Similar coding challenges asked in Goldman Sachs
If you have any other solution or if you have any question, let’s discuss in the comment.