alex_ita's blog

Coin change, no solution?
By alex_ita, history, 4 years ago, In English

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!

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

Comments Comments (14)
| Write comment?
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Use two pointer approach.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think there exists a solution for this. Could you explain your approach?

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

      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

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can sort the array and return the (sorted) prefix whose sum is less than M

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, I miss understood the statement and tought we are looking for the greatest subset in size.

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

Do we have constraints on maximum value of each coin?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -26 Vote: I do not like it

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

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

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.

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

    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!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    And sometimes in real life an exact solution is also unnecessary and some approximate Hash Code solution is sufficient ;)

    → Reply