Count Snow Units Captured between the Hills asked in GS [Coding Challenge]

Aniruddha Chaudhari
Updated: Jan 16, 2022

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.

Example:

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.
find min(left[i], right[i]) - arr[i] for each element.
Cacualte the sum form resultant array.

Python Solution

We are implementing above algorithm using Python programming.

Prerequisite:

Python list

def computeSnowpack(arr):
    # Todo: Implement computeSnowpack

    len_arr = len(arr)
    left = [arr[0]]*len_arr
    left_max = arr[0]
    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[0]) == test[1]):
            return False
    return True

if __name__ == "__main__":
    if( doTestsPass() ):
        print( "All tests pass" )
    else:
        print( "Not all tests pass")

Complexity:

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.

Aniruddha Chaudhari

I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.