There is a cluster of n nodes, each node has a failure rate Pi, e.g. the failure rate of node 1 is P1, the failure rate of node 2 is P2. If there are more than half of nodes fail, the cluster fails. The question is given an array double[] P, what is the failure rate of this cluster.

I gave a brute-force solution in the interview, which is to first write a helper function to get the subsets of P, where each subset is of size K, and use a for loop to call that helper method from (P.length + 1) / 2 to P.length. When it came to optimization, i mentioned DP, and the interviewer didn't say yes or no, just asked me to go ahead, but i didn't even come up with the transition function.

I don't know if there's a dp solution, but any idea of a better solution?