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!
Use two pointer approach.
I don't think there exists a solution for this. Could you explain your approach?
If it is contiguous sub-array, then two pointer approach works. But as i noticed just now, it need not be contiguous. So idk then
You can sort the array and return the (sorted) prefix whose sum is less than M
This does not work. Let's say the array is [1,2,4,10,100] and M is 108. According to your approach, the answer will be {1,2,4,10} which gives a sum of 17, but the answer is {1,2,4,100} which gives a sum of 107.
You are right, I miss understood the statement and tought we are looking for the greatest subset in size.
Do we have constraints on maximum value of each coin?
-10⁹ up to 10⁹
I think dp should work here:
Let $$$dp_i$$$ be the smallest difference between M and some sum of elements on prefix $$$[1, i]$$$ including the $$$i^{th}$$$ element.
Transition: $$$dp_0 = M, dp_i = min(dp_j - ar_i)$$$ for all such j, that $$$dp_j - ar_i \gt = 0$$$
To get the subset, we can, for example, store an array $$$p_i - $$$such j that minimises $$$dp_i$$$
To be honest, I don't think a simple solution exists. At least a complicated one or no solution exists at all. Lets say we will choose 4 coins. We can use meet in the middle for around $$$O(n^2)$$$ (extra constant time for binary search) solution. How about 16 coins? Maybe apply multiple meet in the middle or square root decomposition? Not sure to be honest. But the enormous amount of memory consumption would be so huge which won't be solvable by this method. There must be a constraint/part of statement you forgot to mention.
Edit: I am not really experienced so, the above message is according to my knowledge. Please anyone who has a solution, comment down.
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!
Wow, the recruiters themselves didn't even use part of their brain to think that the problem is not solvable or at least, read about Google Hashcode? That is a shame.
Did you ask interviewers about time limit? The knapsack solution easily passes within 1 hour TL, and it even might be fine. You know, sometimes in real life you are not llimited with 2 seconds and 512 MB. Maybe that's what they wanted to hear.
And sometimes in real life an exact solution is also unnecessary and some approximate Hash Code solution is sufficient ;)