Amazon Interview Question: Given a set of numbers, parti... | Glassdoor

## Interview Question

Software Development Engineer I Interview Seattle, WA

# Given a set of numbers, partition the set in to two, such

that sum of all the candidates in first subset = sum of all the candidate numbers in second subset.

0

Solved by factoring sum of entire set and finding all candidate numbers which sums up to that factor. That is if the set sum = 15. Factorize 15 such as 1+14, 2+13, etc. And find all the candidates in the set which sums up to 1 and 14(and so on). Then subgroup them. Then follow up was how to handle negative values, what if values are largely distributed like {-1M1, -1, 0, 1M} The above method performs miserably. One solution I gave was to reduce numbers by orders of magnitude. That is above set is equivalent to {-11, -1, 0, 10} and while finding out factors of sum, go from -x to +y where x being most negative and y being most positive value in a given set.

Interview Candidate on May 24, 2011
0

it's a subset sum problem with the targetted sum equal to half of the sum of elements in the array. It can be solved usin DP.

mamun on Jun 11, 2011