Interview Question
Country: United States
import java.util.HashMap;
import java.util.Map;
public class Q3 {
static int a[] = { 25, 10, 6, 1 };
//the coin value to number of occurrence. example for 112 you get {6=2, 25=4}
static Map<Integer, Integer> smallestCandidate = new HashMap<Integer, Integer>();
public static void main(String[] args) {
permuteCoins(112, new HashMap<Integer, Integer>(), 0);
System.out.println(smallestCandidate);
smallestCandidate.clear();
permuteCoins(36, new HashMap<Integer, Integer>(), 0);
System.out.println(smallestCandidate);
smallestCandidate.clear();
permuteCoins(47, new HashMap<Integer, Integer>(), 0);
System.out.println(smallestCandidate);
smallestCandidate.clear();
}
/**
* find all possible combinations of coins that adds to the a given number
*
*/
private static void permuteCoins(int number,
Map<Integer, Integer> currentResult, int index) {
if (number <= 0) {
// Compare the current combination of coins of the smallest
// candidate
if (smallestCandidate.isEmpty()
|| getSize(smallestCandidate) > getSize(currentResult)) {
smallestCandidate.clear();
smallestCandidate.putAll(currentResult);
}
return;
}
for (int i = index; i < a.length; i++) {
if (a[i] <= number) {
int numOfCoin = number / a[i];
Map<Integer, Integer> thisResult = new HashMap<Integer, Integer>(
currentResult);
thisResult.put(a[i], numOfCoin);
permuteCoins(number % a[i], thisResult, i + 1);
}
}
}
private static int getSize(Map<Integer, Integer> r) {
int size = 0;
if (!r.isEmpty()) {
for (Integer v : r.values()) {
size += v;
}
}
return size;
}
}
The above seems so complicated for this question? Maybe I misunderstood the question but heres mine:
public class CoinCounter{
public static void main(String []args){
System.out.println("Hello World");
countCoin(126);
}
private static void countCoin(int n) {
int quarters, dimes, nickels, pennies;
quarters = n / 25;
n = n - (quarters * 25);
dimes = n / 10;
n = n - (dimes * 10);
nickels = n / 5;
n = n - (nickels * 5);
pennies = n;
print("quarters:" + quarters +
", dimes:" + dimes +
", nickels:" + nickels +
", pennies:" + pennies);
}
private static void print(String s) {
System.out.println(s);
}
private static void print(char c) {
System.out.print(String.valueOf(c));
}
}
This is how I solved it as well. Far less memory and resource usage as compared to the other solutions.
int[] coins = {25,10,6,1};
int mainFunction(int change)
{
return MinCoin(change, 0);
}
int MinCoin(int change, int count)
{
if(change<=0) return count;
int min = INT_MAX;
for(int i=0;i<coins.length;++i)
{
if(change>=coins[i])
{
int c = MinCoin(change-coins[i], count+1);
min = Min(c, min);
}
}
return min;
}
A pretty simple dp algorithm:
sub dp_count_coins {
my ($sum, @denoms) = @_;
# initialize dp table to length of $sum + 1, set all elements to 999 (i.e. not a low number)
my @dp_table = (999) x ($sum + 1);
# starting solution, there are 0 ways to count a 0 cents
$dp_table[0] = 0;
foreach my $i ( 1 .. $sum ) {
foreach my $j ( 0 .. $#denoms ) {
if ( $i >= $denoms[$j] && 1 + $dp_table[$i - $denoms[$j]] < $dp_table[$i] ) {
$dp_table[$i] = 1 + $dp_table[$i - $denoms[$j]]
}
}
}
return $dp_table[$sum];
}
- Anonymous May 13, 2014