Someone got this interview question from some company that I don't know.
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?