Count Snow Units Captured between the Hills asked in GS [Coding Challenge]
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”.
Explanation with algorithm:
- Create array left and save all the local current maxima while traversing from left to right.
- Create an array right and save all the local current maxima while traversing from right to left.
min(left[i], right[i]) - arr[i]for each element.
- Cacualte the sum form resultant array.
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")
- The time complexity of this algorithm is O(n).
- The space complexity of this algorithm is O(n).
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.