5Sum Interview Question
Anonymous User
2827

Someone got this interview question from some company that I don't know.

  • There are five unsorted number arrays.
  • Choose only one number from each array.
  • Check whether the sum of the five numbers can be 2018. Return true if so otherwise return false.

Python Solution

import collections


def five_sum(A, B, C, D, E):
    AB = collections.Counter(a + b for a in A for b in B) # O (N ^ 2) time O(N) space
    CD = collections.Counter(c + d for c in C for d in D) # O (N ^ 2) time O(N) space

    # O (N ^ 3)
    for ab in AB: 
        for cd in CD:
            for e in E:
                if ab + cd + e == 2018:
                    return True
    return False


A = [0, 2000]
B = [0, 10]
C = [0, 10]
D = [0, -1]
E = [0, -1]

print(five_sum(A, B, C, D, E))
Technically, it would be three separate blocks for time complexity analysis:

# This block is O(N ^ 2)
for element in array 1
    for element in array 2
        generate dictionary 1 # O(N) space
# This block is O(N ^ 2)
for element in array 3
    for element in array 4
        generate dictionary 2 # O(N) space

# This block is O(N ^ 3)
for element in dictionary 1
    for element in dictionary 2
        for element in array 5
            if statement
Then for the space complexity, it would be two dictionaries, each one is an order of N, then the memory would be O(N).

Is my solution and time and space complexity analysis correct or are there any better solution and analysis?

Comments (1)