### alex_ita's blog

By alex_ita, history, 5 months ago,

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!

• +6

 » 5 months ago, # |   -14 Use two pointer approach.
•  » » 5 months ago, # ^ |   0 I don't think there exists a solution for this. Could you explain your approach?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » » 5 months ago, # ^ |   0 Ye, it's not just subarray but a subset. I think they wanted me to solve it for subarray, but made a mistake and said subset, omg...
 » 5 months ago, # |   0 You can sort the array and return the (sorted) prefix whose sum is less than M
•  » » 5 months ago, # ^ |   +3 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.
•  » » » 5 months ago, # ^ |   0 You are right, I miss understood the statement and tought we are looking for the greatest subset in size.
 » 5 months ago, # |   +30 Do we have constraints on maximum value of each coin?
•  » » 5 months ago, # ^ | ← Rev. 3 →   +3 -10⁹ up to 10⁹
 » 5 months ago, # | ← Rev. 3 →   -26 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 >= 0$ To get the subset, we can, for example, store an array $p_i -$such j that minimises $dp_i$
 » 5 months ago, # | ← Rev. 2 →   0 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.
•  » » 5 months ago, # ^ |   +14 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!
•  » » » 5 months ago, # ^ |   +3 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.
 » 5 months ago, # |   0 Auto comment: topic has been updated by alex_ita (previous revision, new revision, compare).
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 And sometimes in real life an exact solution is also unnecessary and some approximate Hash Code solution is sufficient ;)