Learn practical skills, build real-world projects, and advance your career
Updated 3 years ago
Subarray with Given Sum
The following question was asked during a coding interview for Amazon:
You are given an array of numbers (non-negative). Find a continuous subarray of the list which adds up to a given sum.
# Solve the problem here
'''
1. Clearly state the problem and identify input and output formats.
2. Create some test cases
- Generic Cases,
- Subarray at the start,
- Subarray at the end,
- Single element,
- No Subarrayexits,
- More than one subarray exists.
3. Try all subarrays
4. (Optional) Implement brute force solution.
5. Analyze the complexity and identify inefficiency.
6. Apply the right technique and repeat step 3 to 6
'''
'\n1. Clearly state the problem and identify input and output formats.\n2. Create some test cases\n - Generic Cases,\n - Subarray at the start,\n - Subarray at the end,\n - Single element,\n - No Subarrayexits,\n - More than one subarray exists.\n3. Try all subarrays\n4. (Optional) Implement brute force solution.\n5. Analyze the complexity and identify inefficiency.\n6. Apply the right technique and repeat step 3 to 6\n'
test0 = {
'input': {'arr': [1,7,4,2,1,3,11,5], 'target': 10},
'output': (2, 6)
}
test1 = {
'input': {'arr': [4,2,1,3,11,5], 'target': 10},
'output': (0, 4)
}
test2 = {
'input': {'arr': [1,7,4,2,1,3], 'target': 10},
'output': (2, 6)
}
test3 = {
'input': {'arr': [], 'target': 10},
'output': (None, None)
}
tests = [test0, test1, test2, test3]
Solution
Test case:
def subarray_sum1(arr, target):
n = len(arr)
for i in range(n):
for j in range(i, n+1):
if sum(arr[i:j]) == target:
return i, j
return None, None