Hey Guys,
So I was asked this question during my google phone screen Interview.
You are given input balls in different color and each color correspond to weight
Green :1, Yellow :2, Blue :3, Red: 4
Return the kth highest weight combinations of balls that have of all the balls combined in any order
K = 6
input :[R,B,Y,G]
output: [ [R, B, Y, G], = 10
[R, B, Y], = 9
[R, B, G], = 8
[R, Y, G], = 7
[R, B] = 7
[B, Y, G] = 6 ]
Also, the constaint was that if 2 combination result in the same weight, then the size of greater combination should be selected before the smaller size combination for that given weight. That is in here for the combination weight 7, [R,Y,G] must be selected before [R,B] and then any subsequent weight. I bombed it because the only thing that I could think of at the moment could only think of sorting the array and then backtracking, but I was computing the weight many times over. Hence it was not the optimal solution.
Any idea, how would you solve this problem in optimal way( preferably in java)