Uber interview problem

Revision en1, by rasalghul, 2018-11-13 22:30:29

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

------------------------------------------------------ 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)