3
\$\begingroup\$

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(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)
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – IEatBagels Nov 15 '18 at 21:44
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Anthony Nov 15 '18 at 21:46
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ – IEatBagels Nov 15 '18 at 21:49
  • 1
    \$\begingroup\$ The inclusion of negative integers makes it impossible, I think, to get a linear solution, unfortunately... \$\endgroup\$ – Graipher Nov 16 '18 at 12:33
  • 2
    \$\begingroup\$ Also, if you include test cases, you should include the expected outcome as well. \$\endgroup\$ – Graipher Nov 16 '18 at 12:34
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Excellent, thank you for pointing these out - much appreciated. \$\endgroup\$ – Anthony Nov 15 '18 at 22:16
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – vnp Nov 15 '18 at 23:05
  • \$\begingroup\$ @vnp You're right, I'm still struggling a little bit with the Big O notation. \$\endgroup\$ – IEatBagels Nov 20 '18 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.