Coin change, no solution?

Revision en2, by alex_ita, 2020-08-18 02:56:05

Hello. I recently had an interview and have been given a weird problem. I have a number M (up to 10⁹) and array of size 1000. I have to return SUBSET whose sum is the largest possible but not greater than M. Naturally, I wanted to code it like coin change or knapsack, but it fails in either memory or time. Any ideas?

FOUND IT: They actually gave me a problem from Google HashCode... It doesn't have even a valid solution, only one to approximate. I told them it's not possible to solve it in these constraints, they told me I should come up with a solution... Shame on you GSA Capital!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English alex_ita 2020-08-18 02:56:05 272
en1 English alex_ita 2020-08-17 14:58:49 345 Initial revision (published)