rasalghul's blog

Uber interview problem
By rasalghul, history, 6 years ago, In English

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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rasalghul (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Try the following dynamic programming solution: — dp[no_dishes][sum_protein][sum_fat]=0 or 1-is it possible to have a subset from first no_dishes with fat content equal to sum_fat and total protein equal to sum_protein.The reccurence would be dp[no_dishes][sum_protein][sum_fat]=(dp[no_dishes-1][sum_protein-Protein_i][sum_fat-Fat_i] or dp[no_dishes-1][sum_protein][sum_fat]).This is caused by the fact that we can choose to take the current dish or not.Finally,check if there is any dp[N][sum_protein][sum_fat]==1 and sum_protein/sum_fat==T.The complexity is O(n^3*max_fat*max_protein) which I believe is good for these constraints.

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Here is the code of your problem using the similar idea of Bodo

→ Reply