Amazon Interview Question: You are given a fixed number ... | Glassdoor.co.in

# You are given a fixed number of 5 rupee, 10 rupee, 20 rupee

and 50 rupee stamps. Now given an amount for sending a parcel, you should design an algorithm to come out with the minimum number of stamps that should be used for attaining that amount. For example, if the parcel costed 30 rupees, it could be attained using one 20 rupee stamp and one 10 rupee stamp OR using three 10 rupee stamps OR using one 20 rupee stamp and two 5 rupee stamps OR using one 10 rupee stamp and four 5 rupee stamps OR using two 10 rupee stamps and two 5 rupee stamps. However, the minimum number of stamps is the case of one 20 rupee stamp and one 10 rupee stamp where only two stamps are used. The case where no solution is possible should also be handled, for example, a parcel amount of exactly 33 rupees cannot be attained.

1

The solution is attained using dynamic programming. The basic idea is that the minimum number of stamps used for attaining an amount x, is 1+minimum of (minimum number of stamps for attaining x-5, minimum number of stamps for attaining x-10, minimum number of stamps for attaining x-20,minimum number of stamps for attaining x-50). You can try to solve this first by assuming that an unlimited number of 5 rupee, 10 rupee, 20 rupee and 50 rupee stamps are available. And then you can take into account that only a fixed number of these stamps are available.

Interview Candidate on 13-Oct-2012
0

And what is the time involved to get this done? I really liked the question.Simple to read but involves good amount of logic. I ve written down the algorithm but i believe i took more time than i initially thought i would take.

Future Amazon job seeker on 31-Oct-2012
0

I understand what the interviewer is trying to test and I know how to solve it, but what about more realistic scenario where parcel postage cost would be beyond given values like 3 units of currency or 37 units of currency.

Puzzled on 06-Nov-2012
2

In this specific case, dynamic programming is overkill. There's a better optimal substructure here: The stamp with greatest value less than parcel cost minus stamp values already committed minimize the total of stamps.

Greedy Algorithm on 29-Jan-2013
2

1. find the stamp &lt;= cost from highest stamp cost
2. num of found_stamp = found_stamp/cost, rem_stamp = found_stamp % cost
3. Do 1, then 2 until rem_stamp ==0 (done) or rem_stamp &lt; least stamp available (not possible case)

Try on 05-Mar-2013
0

In the previous ans, after step 3 if rem_stamp !=0, go back to step 1, find next_stamp &lt; cost (but smaller than value of found_stamp in previous iteration)

Try on 05-Mar-2013
0

i=0;
boolean solPossible = false;
do
{
if(cost % notes[i] == 0)
solPossible = true;
else
i++;
}
while(!solPossible &amp;&amp; (i

Handling error case (Ex: 33) on 14-Mar-2013
0

void sendParsal(int cost)
{
int[] avlstm={50,20,10,5};
int i=0;
while(cost&gt;=5)
{
while(cost&gt;=avlstm[i])
{
System.out.println(avlstm[i]);
cost=cost-avlstm[i];
}
i++;
}
if(cost!=0)
{
System.out.println("Solution not possible.");
}
}

Nishant on 22-Jun-2015
0

void Foo(int cost)
{
if (cost % 5 != 0)
Console.WriteLine("Not possible");
else if (cost stampCosts = new List() { 50, 20, 10, 5 };
int count = 0;
while (cost &gt; 0)
foreach (int stampCost in stamptCosts)
if (cost &gt;= stampCpst)
{
cost -= stampCost;
Console.WriteLine("Stamp: " + stampCost);
count++;
break;
}
}
Console.WriteLine("Count: " + count);

}

Steve on 16-Feb-2019