Minimum Cost To Buy Oranges
You are given a bag of size 'W' kg and provided with the costs of packets with different weights of oranges as a list/array with the name 'cost'. Every i-th position in the cost denotes the price of 'i+1' kg packet of oranges.

If at any point in time the i-th cost is -1, it means that 'i+1' kg packet of orange is unavailable.

You are required to find the minimum total cost to buy exactly 'W' kg oranges and if it's not possible to buy precisely W kg oranges then print -1. There is an infinite supply of all available packet types.

Note :

Array index 'i' denotes the cost of (i+1)kg packet. Example: cost[0] is the cost of a 1kg packet of oranges.

Input Format :

The first line of each test case contains two single space-separated integers 'N' and 'W' where 'N' denotes the size of the array/list(cost), and 'W' is the bag's size. The second line of each test case contains 'N' single space-separated integers denoting the values of the cost.

Output Format :

Print the minimum cost to buy exactly W kg oranges. If it's impossible, print "-1".

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Minimum Cost To Buy Oranges

You are given a bag of size 'W' kg and provided with the costs of packets with different weights of oranges as a list/array with the name 'cost'. Every i-th position in the cost denotes the price of 'i+1' kg packet of oranges.

If at any point in time the i-th cost is -1, it means that 'i+1' kg packet of orange is unavailable.

You are required to find the minimum total cost to buy exactly 'W' kg oranges and if it's not possible to buy precisely W kg oranges then print -1. There is an infinite supply of all available packet types.

Note :

Array index 'i' denotes the cost of (i+1)kg packet. 
Example: cost[0] is the cost of a 1kg packet of oranges.

Input Format :

The first line of each test case contains two single space-separated integers 'N' and 'W' where 'N' denotes the size of the array/list(cost), and 'W' is the bag's size.

The second line of each test case contains 'N' single space-separated integers denoting the values of the cost.

Output Format :

Print the minimum cost to buy exactly W kg oranges. If it's impossible, print "-1".

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= N <= 1000
1 <= W <= 1000
-1 <= cost[i] <= 1000000

Time Limit: 1sec

Accepted Answer

This problem was actually a variation Unbounded Kanpsack Problem . I first gave the interviewer a naive recursive
approach and then later optimised it using memoisation .

Naive Recursive Approach :

1) Create a recursive function ( int minCost(cost, idx , w) ) which returns the optimal answer for an array which starts
with index idx and for a given weight w.

2) Now for every index idx , if cost[idx]!=-1 then I have three options :

option1 -> Take that particular element and then recursively call for the whole array again (we won't increment idx
here as we can take an element infinitley many times) with the same idx and a reduced weight w-idx-1(assuming 0-
based indexing) . i.e.,
option1=cost[idx]+minCost(cost,idx,w-idx-1);

option2 -> Take that particular element and then recursively call for the rest of the array with index as idx+1 and a
reduced weight w-idx-1(assuming 0-based indexing) . i.e.,
option2=cost[idx]+minCost(cost,idx+1,w-idx-1);

option3-> Do not take that element at all and then recursively call for the rest of the array with index as idx+1 but with
the same weight w.
option3=minCost(cost,idx+1,w);

Now , return the min({op1,op2,op3})

3)If cost[idx]==-1 , we have only one option - To not take that element at all and then recursively call for the rest of the
array with index as idx+1 but with the same weight w.
i.e. return minCost(cost,idx+1,w)

4)Base Cases :
a) If weight , w==0 then we can simply return 0 (do not take any element)
b) If index >= cost.size() or weight<0 , then simply return the max value of integer (INT_MAX in C++)

TC : O(3^n)
SC:O(n*w)

Dynamic Programmming (Using Memoisation ) :

As we can observe , this problem has both optimal substructure as well as optimal subproblem properties and hence
can be easily memoised using a map (key->pair of index and weight , value->answer for this state) i.e.
dp[{idx,w}= min({op1,op2,op3})
Check if we have previously visited this state or not . If yes simply return the dp value

TC : O(n*w)
SC : O(n*w)

Accepted Answer

Recursive Approach

Write a recursive function minCostToBuyOrangesHelper(idx, requiredWeight, n) to return the Minimum cost to buy exactly requiredWeight Kg oranges with (idx+1) Kg to N kg packets.

Our minimum cost for weight W will be : minCostToBuyOrangesHelper(idx, W, n)
Now at any instant (idx, requiredWeight, n), we have two options:
1. The option of taking this packet:

cost[idx] + minCostToBuyOrangesHelper(idx, requiredWeight - (idx + 1), n, cost)

2. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

3. We will take the minimum of these two options as the minimum cost for instant minCostToBuyOrangesHelper(idx, requiredWeight, n)

4. Base cases are:

When requiredWeight is 0 then return 0.
if we reached the end and idx = n and requiredWeight != 0 then return maximum value (INT_MAX) as now it’s impossible to buy the requiredWeight.
If requiredWeight != 0 and requiredWeight < (idx+1) then return maximum value (INT_MAX) as it’s impossible to buy requiredWeight from greater weight packets.
4. Also, take care of packets which are not available. The minimum cost for those idx will have only one option:
1. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

Space Complexity: OtherExplanation:

O(W), where ‘W’ is the required weight.

The recursive call stack can have a maximum depth of ‘W’ as the recursion call will return after requiredWeight become 0 or ( idx+1 > requiredWeight ).

Time Complexity: OtherExplanation:

O((2^W)*N), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

There are 2 possibilities for each requiredWeight value which gives us the complexity O(2^W) and this requiredWeight can occur with ‘N’ different packets so, Overall Time Complexity is O((2^W)*N).

Accepted Answer

Memoization

We will write a recursive function minCostToBuyOrangesHelper(idx, requiredWeight, n) to return the Minimum cost to buy exactly requiredWeight Kg oranges with (idx+1) Kg to N kg packets. Then we will use a Dynamic Programming approach to memoize the calls in a DP matrix minCost[idx][requiredWeight] which will save the results of calls and will return the result when we again try to call for the same values.

Our minimum cost for weight W will be : minCostToBuyOrangesHelper(idx, W, n)

Now at any instant (idx, requiredWeight, n), we have two options:
1. The option of taking this packet:

cost[idx] + minCostToBuyOrangesHelper(idx, requiredWeight - (idx + 1), n, cost)

The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

We will take the minimum of these two options as the minimum cost for instant minCostToBuyOrangesHelper(idx, requiredWeight, n) and will save this in our DP matrix minCost[idx][requiredWeight] (initially filled with -1s).
Base cases are:
1. If answer is already present in minCost[idx][requiredWeight] then return the same value.
2. When requiredWeight is 0 then return 0.
3. If we reached the end and idx = n and requiredWeight != 0 then return maximum value (INT_MAX) as now it’s impossible to buy the requiredWeight.
4. If requiredWeight != 0 and requiredWeight < (idx+1) then return maximum value (INT_MAX) as it’s impossible to buy requiredWeight from greater weight packets.
If dp[idx][requiredWeight] is not equal to -1, then we will return it.
Also, take care of packets that are not available. The minimum cost for those idx will have only one option:
1. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

5. Before returning the answer, store it in the dp array.

Space Complexity: OtherExplanation:

O(N*W), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

As we are using DP Matrix of size N*W.

Time Complexity: OtherExplanation:

O(N*W), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

As we are using Dynamic Programming Approach and at max, we can have N*W different calls so, Overall Time Complexity is O(N*W)

Accepted Answer

Iterative DP

We will write an iterative DP where minCost[i][j] denotes the minimum cost of buying exactly 'j' kg Oranges with 1 to 'i’ kg packets of oranges.

The base cases are:
We will be Initializing 0th row with INF (Max Value) as we can’t buy any oranges with a packet having weight ‘0’ kg.
1. We Initializing 0th column with 0 as cost of filling 0kg at any point in 0.
Now iterating over ‘i’ for different weights of packets (from i = 0 to i = n) we will iterate for buying exactly ‘j’ kg Oranges (from j = 0 to j = w). So transition relations are:
1. If 'i' kg packet of orange is unavailable then, for all values of j :

minCost[i][j] = minCost[i - 1][j]

If i > j means capacity of the bag is less then weight of item then:

minCost[i][j] = minCost[i - 1][j];

2. If i <= j get minimum cost either by including it or excluding it:

minCost[i][j] = min(minCost[i - 1][j], minCost[i][j - i] + cost[i - 1]);

3. So finally we have our minimum cost in minCost[n][w]. If it’s equal to INF (Max Value), then return -1 else return the result.

Space Complexity: OtherExplanation:

O(N*W), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

As we are using DP Matrix of size N*W.

Time Complexity: OtherExplanation:

O(N*W), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

As we are using Dynamic Programming Approach and we are looping over all the values of ‘j’ (Required Weight) for all the values of ‘i’ (packets of different weight) so Overall Time Complexity is O(N*W)

Accepted Answer

Space Optimised Iterative DP

We will write an iterative DP using 1D DP array where minCost[i] denotes Minimum cost of buying exactly 'i' kg Oranges with all the packets of oranges.

The base cases are:
1. Initializing minCost[0] = 0 for buying exactly 0 kg oranges.
2. Initializing all other values in minCost[] with the INF (Max Value).
Now iterating over ‘j’ for buying exactly ‘j’ kg Oranges (from j = 0 to j = w), we will iterate for different weights of packets ‘i’ (from i = 0 to i = n). So transition relations are:
1. If 'i' kg packet of orange is unavailable then, for all values of j :

continue without changing minCost as they can’t contribute to minimizing cost.

If i > j means capacity of the bag is less then weight of item then:

continue without changing minCost as they can’t contribute to minimizing cost.

2. If i <= j get minimum cost either by including it or excluding it:

minCost[i] = min(minCost[i], minCost[i - j] + cost[j - 1]);

3. So finally we have our minimum cost in minCost[w]. If it’s equal to INF (Max Value), then return -1 else return the result.

Space Complexity: OtherExplanation:

O(W), where ‘W’ is the required weight.

As we are using 1D DP Array of size W.

Time Complexity: OtherExplanation:

O(N*W), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

As we are using Dynamic Programming Approach and we are looping over all the values of ‘i’ (packets of different weight) for all the values of ‘j’ (Required Weight) so, Overall Time Complexity is O(N*W).

You are given a bag of size 'W' kg and provided with the costs of packets with different weights of oranges as a list/array with the name 'cost'. Every i-th position in the cost denotes the price of 'i+1' kg packet of oranges.

If at any point in time the i-th cost is -1, it means that 'i+1' kg packet of orange is unavailable.

You are required to find the minimum total cost to buy exactly 'W' kg oranges and if it's not possible to buy precisely W kg oranges then print -1. There is an infinite supply of all available packet types.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Walmart Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Walmart Software Developer