AjaySabarish's blog

Google Onsite problem
By AjaySabarish, history, 3 years ago, In English

You are given an integer array Inventories representing the ribbon inventories, where Inventories[i] represents the length of the ith ribbon, and an array of orders.

Each order in orders is an array of integers, representing the ribbons needed with certain lengths for that order. For example, if order = [1,2], then that means this order need a ribbon with length 1 and a ribbon with length 2.

You may cut any of the ribbons in the inventory into any number of segments of positive integer lengths, or perform no cuts at all.

However, you cannot combine two ribbons in the inventory to form a longer ribbon and fullfil an order. Each segment/ribbon in the inventory cannot be reused. The question is, what is the maximum number of orders that can be fulfilled?

Example 1:

Input: Inventories = [1,8,7], orders = [[1, 2], [4, 3, 6]]

Output: 2

Explanation:

First cut inventories[1] into [2,6], then the inventory becomes [1, 7, 2, 6]. Use inventories[0] and inventories[2] for the first order. The rest of the inventories are [7,6], then cut the ribbon with the length of 7 into 4 and 3 to fulfill the second order. So in total 2 orders are fulfilled.

Example 2:

Input: Inventories = [1,2,3], orders = [[3, 3], [4]]

Output: 0

Explanation:

None of the orders can be fulfilled. Notice we cannot combine inventories[0] and inventories[1] for orders[0].

Example 3:

Input: Inventories = [3], orders = [[2]]

Output: 1

Explanation:

Cut the ribbon into 2 and 1, and use the first segment for that order.

I have been breaking my head over this, I thought of some greedy approaches, sorting orders by the max ribbon required by each item and processing it. Eg: [[4,3,6], [1,2]] becomes [[1,2],[4,3,6]]. But this fails when order max is less but the number of items in the order is huge.

Does anyone have any approach ?

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

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

Any constraint?

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

    Interview problems don't have constraints, you have to optimize it, but you have a polynomial soln ?

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

      Nvm, wrong approach

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

        You mean, you'll have 2^n combinations, in each combination you will see if the corresponding bit mask is satisfied ? But how would you check it ? I mean which inventory item will you map to which order item ?

        A corner case: Inventory : [4,6], Order [ [ 3, 3, 4 ] ] , ans is 1.

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

          If you have a list of ribbons lets say x[] and want to satisfy a single list of order, you have to use bitmask dp, accroding to me. Like the checking part. Let dp[i][j] denote if upto ith ribbon can staisfy mask j [Here I am talking of a single list not multiple]. Then transition are

          dp[i][j]=dp[i-1][j]
Let s be a submask of j
dp[i][j]|=(dp[i-1][s^j] && sum[s]<=x[i]) basically we want to satisfy all set bits in mask s using x[i], hence its sum must be <= x[i].
Here we are doing submask enumeration.

          finally answer (true or false) lies in dp[n-1][(1<<sz)-1]; This you can do for all mask of the order list. But I know its slow but will work.

          → Reply
»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

it is a multi knapsack DP, just change the classic 0/1 knapsack for multiple bags.

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

    Why the hell is this downvoted, you can ask,if you guys don't understand or found this wrong.

    Anyways I will explain in details so basically your dp states will be total number of bags , now so your states dp would look something like
    dp[capacity 1][capacity 2][capacity 3]...[capacity n]
    This would be not feasible to implement unless you linearize the dp container.
    Now as we do in general knapsack we have to chose a combination that in which container would we put the element , so net complexity will become $$$ O(product (capacity) * product (elements))$$$
    This is pseudo polynomial solution .

    Of course we could also use exponential solution and memoise it, this would be better in interview both for implementation and ease of explanation.

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

      How do you choose which ordered ribbon is taken from which inventory ribbon?

      If inventory = [5, 5] and orders = [[1,1],[4,4]], the only way to fill this is take 0th order from both inventory ribbon and 1st order again from both inventory ribbon. If we try to take 0th order from 1st ribbon only, we can't satisfy 1st order.

      How are your transitions for the dp states?? By "bags" you mean inventory ribbons, right?

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

        It does not matter actually because let's say when you take 1 1 from 5 5 so new state will be 4 4 but if you take from only one bag it will be 3 5 , so both the cases are handled as we do in knapsack.

        For implementation My transition would be in incremental order for iterative version for(item in listitems)
        for(0 to capacity_1 ).....for(0 to capacity_n)
        transition or update from prevdp to newdp
        It's just modification of 0/1 knapsack basically.
        Also while doing transition we are assuming that currently product1 in item is used for bag1 and then again a for loop but update will only happen when we are at the last for loop when we used all the product in item , now as we updating new dp from previous dp it will handle both the case
        Also i have to maintain one stack to update past product states as i am doing this iteratively so i also have to update the branxh it was coming from hence i said recursion would be much better here to update. I am not sure if i am explaining this properly but let me know

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

The simplest (and highest time complexity solution) I can think of is..

Spoiler

We can maybe optimize it a little more by pruning cases where some order is fulfilled partially. But I can't think of any other optimized approach.

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

    You can memoise the states and then your solution is same as i explained , rec(i+1,0) rec(i,j+1) is same as implementing multiple for loops

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

      Yeah, I realized that after reading your reply.

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

Hello.

I think there isn't any exact algorithm in polynomial-time because the partition problem can be reduced to this.

Suppose there is an exact algorithm for our problem in polynomial-time and we want to know if the array $$$a_1, a_2, \dots, a_n$$$ can be partitioned into two subsets with equal sums or not? We can simply check that with these inputs:

Inventories = $$$[\frac{\sum_{i=1}^n a_i}{2}, \frac{\sum_{i=1}^n a_i}{2}]$$$

orders = $$$[[a_1], [a_2], \dots, [a_n]]$$$

We know there isn't any exact algorithm in polynomial-time for the Partition problem, So there isn't any polynomial-time algorithm for our problem.

I think this problem is similar to the knapsack or partition problem.

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

    Yes you can Simply see the case of one bag and one product in each item , then it's classic knapsack with maximum selection of items given the bag capacity

    Edit : wait above case i mentioned, even tho it can be solved using knapsack but it is not needed.just smallest weight items selected greedily to get maximum quantity would work, we can prove using exchange arguments that selecting smaller would be better.

    → Reply