Find contiguous integers with a given sum

Question

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

The Ask

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(n²).

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)

• IEatBagels: 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?
• Anthony Chao: 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.
• IEatBagels: 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 :)
• Graipher: The inclusion of negative integers makes it impossible, I think, to get a linear solution, unfortunately...
• Graipher: Also, if you include test cases, you should include the expected outcome as well.

Answer 1

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.

• Anthony Chao: Excellent, thank you for pointing these out - much appreciated.
• vnp: 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.
• IEatBagels: @vnp You're right, I'm still struggling a little bit with the Big O notation.