Блог пользователя alex_ita

Автор alex_ita, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Use two pointer approach.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Do we have constraints on maximum value of each coin?

»
4 года назад, # |
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$$$

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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