Adobe Interview Question Software Engineer in Tests
Country: India
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes
Your code is probably wrong. This question is NP hard. We know a NP problem: check if a subset of given numbers sums up to 0.
So, suppose the average of the given set is avg. We subtract every number by avg. Then, the posted question becomes: find a subset of numbers whose sum is 0, which is NP hard.
The practical algorithm is enumeration.
Comment hidden because of low score. Click to expand.
0
of 0 vote
S= S1 union S2
be the partition
s1 is summation of S1
s2 is summation of S2
s1/n1 =s2/n2 = (s1+s2)/(n1+n2)=s/n where s is summation of all elements of S
let P(i,j) denote there is a subset of 1..i such that summation=j
so find P(i,j) such that j=s/n
and
P(i,j) = max { P(i-1,j) ,P(i-1,j-ai) } ai is the ith element
if P(n,s/n)=1 then return "yes"
else return "no partition"
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.
Solutions are here careercup.com/question?id=8872057
- anonymous2 September 23, 2011