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.

View Allnum of num

Senior Software Engineer Interview Hyderabad

AmazonAnswer## 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.

9 Answers

▲

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.

▲

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.

▲

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.

▲

2

▼

1. find the stamp <= 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 < least stamp available (not possible case)

▲

0

▼

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

▲

0

▼

i=0;

boolean solPossible = false;

do

{

if(cost % notes[i] == 0)

solPossible = true;

else

i++;

}

while(!solPossible && (i

▲

0

▼

void sendParsal(int cost)

{

int[] avlstm={50,20,10,5};

int i=0;

while(cost>=5)

{

while(cost>=avlstm[i])

{

System.out.println(avlstm[i]);

cost=cost-avlstm[i];

}

i++;

}

if(cost!=0)

{

System.out.println("Solution not possible.");

}

}

▲

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 > 0)

foreach (int stampCost in stamptCosts)

if (cost >= stampCpst)

{

cost -= stampCost;

Console.WriteLine("Stamp: " + stampCost);

count++;

break;

}

}

Console.WriteLine("Count: " + count);

}

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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.