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.
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:
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.
