Flint
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
The optimal solution should be the one using pseudopolynomial algorithm for the partition problem. Hope this is correct:
def is_magic(seq, magic_number):
# sum(seq) = sum_pos + sum_neg
# if there is a solution:
# sum_positive  sum_negative = magic_namber
# Therefore, the task can be formulated as looking for a subset of seq such that:
# sum_neg = (sum(seq)  magic_number)/2
check_list = seq[1:] # The first element of seq cannot be negative
tmp = sum(seq)  magic_number
if tmp % 2 != 0 or tmp < 0:
return False
# pseudopolynomial algorithm for the partition problem
target = tmp // 2
n = len(check_list)
table = np.zeros((target + 1, n + 1), dtype=bool)
table[0, :] = True
for i in range(1, target + 1): # O(target)
for j in range(1, n + 1): # O(N)
if i  check_list[j  1] >= 0:
table[i, j] = table[i, j  1] or table[i  check_list[j  1], j  1]
else:
table[i, j] = table[i, j  1]
return table[target, n]

Flint
July 15, 2018 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
This algorithm consists of:
(1) checking the least frequent element of a in b
(2) find all the occurrences of this in b
(3) from each position look left and right to see if there are other contiguous characters from a
 Flint October 15, 2018