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.

Interview Answer

2 Answers


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

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.