Uber interview problem

Revision en3, by rasalghul, 2018-11-13 22:34:47

A box of pre-cooked food contains N dishes and each dish has 2 properties, its Protein content and its Fat content. We need to select a non-empty subset of these N dishes such that the ratio of total Protein content to total Fat content in these selected subset of dishes is equal to a given target T.

Answer Yes if possible, No otherwise.

Constraints: 1<=N<=50 1<=T,Protein_i,Fat_i<=10

Eg1:

N=3,T=5

[[8,1],[1,1],[2,1]] where first index corresponds to protein content and second is fat content. Answer is "Yes" because selecting 1st and 3rd dish yields (8+2)/(1+1) = 5.

Eg2:

N=3,T=6

[[8,1],[1,1],[2,1]]. Answer is "No"


I don't think bitmask would work given that N can be upto 50. Any other solutions to this problem?

Tags #interview, #dynamic-programming, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rasalghul 2018-11-13 22:34:47 249
en2 English rasalghul 2018-11-13 22:31:12 4
en1 English rasalghul 2018-11-13 22:30:29 575 Initial revision (published)