Microsoft Interview Question Software Engineer in Tests
I think for getting the maximum no of denominations, we should subtract the given number with every denominations and then doing this process again and again until you are left with 0.
This does not work. For example: x = 1100 = 1000*1 + 100*1, according to your method, we have 1000 and 100 denominations, but x = 1100 = 1000*1 + 10*9 + 1*10, we have 1000,10 and 1 denominations. We need to find all combinations of denominations, then find a maximum set.
You got me wrong , when you are subtracting, then subtract from the lowest denominations, so as for your example x = 1000 , you start with subtracting $1, $2, $5 and so on again and again thereby increasing the counts of the denominations.
Hope this clears
denominations: d[0]<d[1]<...<d[n-1] and d[0] = 1;
pseudo code:
initial x[i] to zero for all i
for(i=0; x>=d[i]; i=(i+1)%n)
x -= d[i];
count[i]++;
count[0] += x;
HashTable<Float,Integer> getDenominations (float num)
{
Hashtable<Float,Integer> table = new Hashtable<Float,Integer>();
int size =10;
if (num<0.01) // 1 cent being the smallest denomination
return null;
int[] denominations = new int[size];
denominations = {0.01, 0.05, 0.10, 0.25, 0.50, 1, 5, 10, 20, 100};
int i =0;
int count = 0;
while(i<size&& num >0.01)
{
if (num<denominations[0])
return table;
if(i =size && num > 0)
i =0;
if(num-denominatios[i]>0)
{
num = num - denominations[i];
if (table.contains(denominatios[i))
{
count = table.get(denominations[i]);
count ++;
table.put(denominations[i], count)
}
else
{
table.put(denominations[i],1)
}
}
i++;
}
else
{
i = size - 1; //to again loop through it
}
return table;
}
can you please explain the problem a little bit more?
- test January 19, 2010what do you mean "maximum no. of denomination."?