# Introduction

This question was asked in a technical interview, I am looking for some feedback on my solution.

Given a list of integers and a number K, return which contiguous elements of the list sum to K. For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, 3, 4].

My solution works with my test cases, but I would like feedback on how others would approach the problem and where my code could be altered to improve efficiency and runtime. Currently, I have a nested for loop and I believe my solution is O(n2).

# Solution

def contigSum(nums, k):

for i, num in enumerate(nums):
accum = 0
result = []
# print(f'Current index = {i}')
# print(f'Starting value = {num}')

for val in nums[i:len(nums)]:
# print(f'accum = {accum}')
result.append(val)
# print(f'accum = {accum} + {val}')
accum += val

if accum == k:
print(f'{result} = {k}')
return 0
# else:
# print(f'accum = {accum}')

print('No match found')
return 1


# Test Cases

nums0 = []
k0 = None
contigSum(nums0, k0)

nums6 = [1, 2, 3]
k6 = 99
contigSum(nums6, k6)

nums1 = [1, 2, 3, 4, 5]
k1 = 9
contigSum(nums1, k1)

nums2 = [-1, -2, -3]
k2 = -6
contigSum(nums2, k2)

nums4 = [5, 2, 6, 11, 284, -25, -2, 11]
k4 = 9
contigSum(nums4, k4)

nums5 = [10, 9, 7, 6, 5, 4, 3, 2 ,1]
k5 = 20
contigSum(nums5, k5)

• Why is Lyft part of your title as it's mentioned nowhere in the question? Also, why isn't [4,5] a valid answer if K is 9? – IEatBagels Nov 15 '18 at 21:44
• The question was asked by Lyft in a technical interview - I agree, it is not relevant to the question. I'll remove it. [4, 5] is a valid solution, but I wrote my solution to stop at the first successful match. – Anthony Nov 15 '18 at 21:46
• I believe that specifying it is a technical interview might be useful to the question though (In my opinion) as it may orient the review in another way :) – IEatBagels Nov 15 '18 at 21:49
• The inclusion of negative integers makes it impossible, I think, to get a linear solution, unfortunately... – Graipher Nov 16 '18 at 12:33
• Also, if you include test cases, you should include the expected outcome as well. – Graipher Nov 16 '18 at 12:34

## Unused code

for i, num in enumerate(nums):, the i variable is used in your commented code, but commented code shouldn't exist, so i shouldn't exist either.

To come back on the commented code, I hope you didn't submit your solution with these comments as this is a (in my opinion) very bad practice. What does commented code mean after all? These comments could all be replaced by any debugging tool.

## Running time

I believe your solution is actually running on $$\O(n*\log(n))\$$ time as the nested loop doesn't restart at index 1 every time it runs (which is a good thing). Seems like this is wrong.

## Code structure

Usually, in an interview question code structure is pretty important. Right now you have one method that does everything. You should at least have a method that returns your result and one that prints it. Something like :

def main():
nums = ...
k = ...
print(contigSum(nums, k))

def contigSum(nums, k):
...


and contigSum should return the result, not print it.

• Excellent, thank you for pointing these out - much appreciated. – Anthony Nov 15 '18 at 22:16
• Even though the nested loop doesn't restart at index 1 every time this one is still $O(n^2)$. Please double-check your reasoning. – vnp Nov 15 '18 at 23:05
• @vnp You're right, I'm still struggling a little bit with the Big O notation. – IEatBagels Nov 20 '18 at 14:56