Google Interview Question
Software Engineer / DevelopersCountry: United States
Yes, it is a knapsack problem and can be solved by DP.
F(n, amount) = F(n-1, amount) || F(n-1, amount-coins[n])
typedef enum State
{
Contains,
NotContains,
NotFound
};
void FindConins(int coins[], int num, int amount)
{
State** result = new State*[num];
for(int i = 0; i < num; ++i)
result[i] = new State[amount];
if(amount <= 0)
return;
result[0][0] = Contains;
result[0][1] = NotFound;
for(int i = 0; i < 21; ++i)
{
for(int j = 1; j < amount; ++j)
{
if((i-1 >= 0) &&(result[i-1][j] == Contains || result[i-1][j] == NotContains))
result[i][j] = NotContains;
else if((i-1 >= 0 && j-coins[i] >= 0) &&(result[i-1][j-coins[i]] == Contains || result[i-1][j-coins[i]] == NotContains))
result[i][j] = Contains;
else
result[i][j] = NotFound;
}
}
int i = 0;
for(; i < 21; ++i)
{
if(result[i][amount -1] != NotFound)
{
break;
}
}
while(amount > 0)
{
if(result[i][amount -1] == Contains)
{
printf("%d\t", coins[i]);
amount -= coins[i];
}
--i;
}
for(int i = 0; i < num; ++i)
delete[] result[i];
delete[] result;
}
Assuming denomination to be 25 cents(quarters), 10 cents(dimes), 5 cents(nickels) and 1 cent(pennies). Printing number of ways possible to make change for "n" cents:
Algorithm : We know that makeChange(100):
= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)
Can we reduce this further? Yes!
= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1
Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.
Code:
#include<stdio.h>
int makeChange(int n, int denom) {
int next_denom = 0;
switch (denom) {
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
return 1;
}
int i,ways = 0;
for (i = 0; i * denom <= n; i++) {
ways += makeChange(n - i * denom, next_denom);
}
return ways;
}
int main(){
int n = 100;
printf("%d",makeChange(n, 25));
return 1;
}
The unlimited version is
for d in denominations:
for a ascending in amounts:
feasible[a] = feasible[a] or feasible[a - d]
With ascending iteration, we can add d to sub-solutions that already use d. The limited version is
for d in coins:
for a descending in amounts:
feasible[a] = feasible[a] or feasible[a - d]
With descending iteration, every sub-solution a - d does not include that particular coin.
Undoubtedly there is a more efficient algorithm if there are a large number of coins of each denomination.
Start with highest denomination, check how much you can much change you can make with it, if you can't goto next smallest one, if you use it as much as possible and for remaining amount, goto next smaller denomination. This is the greedy solution.
Consider the case of coins with dominations of 99 cents, 3 cents, and 1 cents. This algorithm can't generate 1 dollars (100 cents)
DP is a overkill in this scenario. Memoization is better approach. As DP solve all the possible sub-problems whether needed or not. Memoization is same old recursive approach which note down what is already solved.
So, we have:
v = {1, 5, 10, 25, 50, 100} // domincations US exmaple
c = {2, 4, 2, 4, 1, 2} // count of each coin in the pocket.
It can be represented as:
a = {1,1, 5,5,5,5, 10, 10, } // all coin domination their count times.
F(n, AMOUNT) = true if a[n] == AMOUNT // exact domination
F(n, AMOUNT) = false if n == 0 or AMOUNT < 0 // no coins available
F(n, AMOUNT) = F(n-1, AMOUNT) OR F(n-1, AMOUNT-a[n])
So, you need to have an array of size results[n][AMOUNT], each element can contains 3 values:
UNKNOWN
TRUE
FALSE
bool F(int n, int amount)
{
if (n == 0 || amount < 0)
{
return false;
}
if (amount == a[n])
{
return true;
}
if (result[n][amount] == UNKNOWN)
{
result[n][amount] = F(n-1, AMOUNT) || F(n-1, AMOUNT-a[n]);
}
return result[n][amount];
}
<pre lang="" line="1" title="CodeMonkey97168" class="run-this">import java.util.ArrayList;
import java.util.List;
/**
*
* @author Pragalathan
*/
class CoinDenomination {
static class Coin {
int value;
int count;
public Coin(int value, int count) {
this.value = value;
this.count = count;
}
@Override
public String toString() {
return "(" + value + "x" + count + ")";
}
}
Coin[] coins;
public CoinDenomination(Coin[] coins) {
this.coins = coins;
}
List<Coin> getChange(int amount) {
List<Coin> change = new ArrayList<Coin>();
getChange(amount, 0, change);
return change;
}
private boolean getChange(int balance, int coinIndex, List<Coin> change) {
if (coinIndex >= coins.length) {
return false;
}
Coin coin = coins[coinIndex];
int count = Math.min(coin.count, balance / coin.value);
for (int i = count; i >= 0; i--) {
int newBalance = balance - i * coin.value;
if (newBalance == 0) {
change.add(new Coin(coin.value, i));
return true;
}
if (getChange(newBalance, coinIndex + 1, change)) {
if (i > 0) {
change.add(new Coin(coin.value, i));
}
return true;
}
}
return false;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int[] values = {1, 5, 10, 25, 50, 100};
int[] counts = {3, 4, 2, 4, 1, 2};
Coin[] coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
CoinDenomination cd = new CoinDenomination(coins);
int amount = 33;
System.out.println(amount + ": " + cd.getChange(amount));
values = new int[]{1, 10, 25, 50, 100};
counts = new int[]{3, 3, 4, 1, 2};
coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
cd = new CoinDenomination(coins);
amount = 205;
System.out.println(amount + ": " + cd.getChange(amount));
}
}
</pre><pre title="CodeMonkey97168" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey97457" class="run-this">import java.util.HashMap;
import java.util.LinkedList;
/**
* @author j
* You have coins with different denominations and you have limited number of each denominations (some maybe zero),
* how will you determine if you can supply the given change. DP , are you sure? think again.
*/
class G87CoinComposition {
/**
* @param n
* @param k
* @param coin
* @param coinUsed - output,
* @returns the # of minimal coins used, in coinUsed you get the combination of the coins to build n....
* this routine is using Dynamic Programming to build the optimal solution
* c[i] minimum number of coins we need to build for i;
* c[i] = infinity i < 0
* c[i] = 0; j = 0
* c[i] = 1+ minimum {c[i] - d[j]} 0 <= j < den.length...
*/
public static int computeMinNumberCoinsForChangeSolution(int n, int k, int[] coin, LinkedList<Integer> coinUsed) {
int[] c = new int[n+1];
int[] d = new int[n+1];
c[0] = 0;
d[0] = 0;
for (int i = 1; i <= n; i++) {
c[i] = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
if (coin[j] <= i && 1 + c[i - coin[j]] < c[i]) {
c[i] = 1 + c[i - coin[j]];
d[i] = coin[j];
}
}
}
buildCoinUsedForChange(d, n, coinUsed);
return c[n];
}
private static void buildCoinUsedForChange(int[] d, int i, LinkedList<Integer> coinUsed){
if(i > 0){
buildCoinUsedForChange(d, i-d[i], coinUsed);
coinUsed.add(d[i]);
}
}
/**
* @param coinUsed
* @param limit contains the constrains for coin selections, key = coin, value = max number possible
* @return true for success , false otherwise
*/
public static boolean checkForMinChange(int n, int k, int[] coin, LinkedList<Integer> coinUsed, HashMap<Integer, Integer> limit){
computeMinNumberCoinsForChangeSolution(n, k, coin, coinUsed);
for(Integer cu: coinUsed){
if(!limit.containsKey(cu)) return false;
int v = limit.get(cu)-1;
if( v <=0){
limit.remove(cu);
} else {
limit.put(cu, v);
}
}
return true;
}
public static void main(String[] args) {
int[] coin = { 1, 5, 10, 20, 25, 50 };
LinkedList<Integer> coinUsed = new LinkedList<Integer>();
HashMap<Integer, Integer> limit = new HashMap<Integer, Integer>();
for (int i = 0; i < coin.length; i++) {
limit.put(coin[i], 10);
}
System.out.println(checkForMinChange(183, coin.length, coin, coinUsed, limit));
for(Integer cu: coinUsed){
System.out.printf("%d ", cu);
}
// Simulate negative case, limit the usage for 1 cent to only one coin
coinUsed = new LinkedList<Integer>();
for (int i = 0; i < coin.length; i++) {
limit.put(coin[i], 10);
}
limit.put(1, 1);
System.out.println("\n"+checkForMinChange(183, coin.length, coin, coinUsed, limit));
for(Integer cu: coinUsed){
System.out.printf("%d ", cu);
}
}
}
</pre><pre title="CodeMonkey97457" input="yes">
</pre>
public static void main(String[] args) {
int [] D = {50, 25, 10, 1};
int [] limit = {2, 1, 2, 5};
makeChangeLimitedCoins(D, limit, 30);
}
public static void makeChangeLimitedCoins(int [] D, int [] S, int N) {
int [] C = new int [N+1];
C[0] = 0;
int len = D.length;
int [][] track = new int[N+1][len];
for (int i=0; i<len; i++) {
track[0][i] = S[i];
}
for (int j=1; j<=N; j++) {
C[j] = Integer.MAX_VALUE;
for (int k=0; k<len ; k++) {
if (j >= D[k] && (C[j-D[k]] < Integer.MAX_VALUE) && (track[j-D[k]][k] > 0)) {
if ((C[j] > 1+C[j-D[k]])) {
C[j] = 1 + C[j-D[k]];
track[j][k] = track[j-D[k]][k] - 1;
} else {
track[j][k] = track[j-D[k]][k];
}
} else if (j < D[k] ){
track[j][k] = track[0][k];
}
}
}
System.out.println("Printing Coin Value and Change:");
for (int i=1; i<=N; i++) {
if (C[i] == Integer.MAX_VALUE) {
System.out.println(i + ":" + " Not Possible");
} else {
System.out.println(i + ":" + C[i]);
}
}
System.out.println();
for (int i=0; i<=N ;i++) {
System.out.print(i + ": ");
for (int j=0; j<len; j++) {
System.out.print(track[i][j] + " ");
}
System.out.println();
}
}
There is a minor error in this code for the line
track[j][k] = track[j - D[k]][k] - 1;
It should assign the whole sub-problem solution from track[j-D[k]] to track[j], not only with the kth coins.
There are multiple errors in this code as I walked through it. But it was useful for understanding. IMO the logic should be
for (int j=1; j<=N; j++) {
// if we just use the previous row, we will have one more cent left over
C[j] = C[j-1] + 1;
for (m=0; m<len; m++) {
track[j][m] = track[j-1][m] - 1;
}
// try to do better by spending a coin from an earlier solution
for (int k=0; k<len ; k++) {
if (j >= D[k]
// row j-D[k] contains a solution
&& (track[j-D[k]][k] > 0)
// row j-D[k] has a coin of denomination k available
&& C[j] > C[j-D[k]]) {
// the solution from the earlier row beats our current best in this row
// copy all values from earlier row:
for (m=0; m<len; m++) {
track[j][m] = track[j-D[k]][m] - 1;
}
C[j] = C[j-D[k]];
}
else if (j < D[k] ){
track[j][k] = track[0][k];
}
}
}
public static boolean possibleSum(int [] array, int sum) {
if (sum == 0) return true;
if (sum < 0) return false;
if (array.length == 0) return false;
// if a is part of solution
int [] sub = Arrays.copyOfRange(array, 1, array.length);
if (possibleSum(sub, sum - array[0])) {
return true;
// not include this one
} else {
return possibleSum(sub, sum);
}
}
I did not get the question, properly.
But if we are to get the change in minimum number of coins for an amount, then we can store the values from 0 to (LCM of all denominations) by checking all combinations.
Above that we will just
find for amount % LCM, which we already have,
+ (amount/LCM)*(LCM/maxDenom).
I think both greedy and dynamic are work.
greedy:
int getMaxDenomination(map<int, int> m, int change) {
int max = -1;
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
if (it->second > 0 && it->first > max && it->first <= change) {
max = it->first;
}
}
return max;
}
bool supply(map<int, int> m, int change) {
assert(change > 0);
int max = getMaxDenomination(m, change);
if (max != -1) {
if (change - max > 0) {
m[max] = m[max] - 1;
return supply(m, change - max);
} else {
return true;
}
} else {
return false;
}
}
void main() {
map<int, int> m;
m[1] = 2; // has 2 pennies
m[5] = 3;
m[25] = 4;
m[50] = 12;
m[100] = 1;
cout << supply(m, 20) << endl;
}
Here is the one in C#.
public bool MakeChanges(int[] coinType, int[] coinNumber, int change)
{
return this.MakeChanges(coinType, coinNumber, change, 0);
}
protected bool MakeChanges(int[] coinType, int[] coinNumber, int change, int index)
{
if (change < 0)
{
throw new ArgumentException();
}
if (change == 0)
{
return true;
}
else
{
int totalCoin = 0;
for (int i = 0; i < coinType.Length; i++)
{
totalCoin += coinType[i] * coinNumber[i];
}
if (change > totalCoin)
{
return false;
}
if (change == totalCoin)
{
return true;
}
else
{
//Less than total
for (int i = index; i < coinType.Length; i++)
{
int temp = coinNumber[i];
for (; coinNumber[i] >= 0; )
{
coinNumber[i]--;
bool result = MakeChanges(coinType, coinNumber, change, i);
if (result)
{
return result;
}
}
coinNumber[i] = temp;
}
}
}
return false;
}
Test Code:
/// <summary>
///A test for MakeChanges
///</summary>
[TestMethod()]
public void MakeChangesTest()
{
Google1 target = new Google1();
int[] coinType = {25, 10, 5, 1};
int[] coinNumber = {3, 9, 9, 9};
int change = 142;
bool expected = true; // TODO: Initialize to an appropriate value
bool actual;
actual = target.MakeChanges(coinType, coinNumber, change);
Assert.AreEqual(expected, actual);
for (int i = 0; i < coinNumber.Length; i++)
{
Console.WriteLine(coinNumber[i]);
}
}
#include <iostream>
using namespace std;
bool coinChange(int set[],int count[],int m,int sum){
if(m<=0&&sum>0||sum<0)
return false;
if(sum==0)
return true;
if(set[m-1]<=sum&&count[m-1]>0){
bool ans1=coinChange(set,count,m-1,sum);
if(ans1)return ans1;
--count[m-1];
bool ans2=coinChange(set,count,m,sum-set[m-1]);
if(!ans2)++count[m-1];
return ans2;
}
return coinChange(set,count,m-1,sum);
}
int main() {
int set[]={3,7,11,16};
int count[]={1,2,3,4};
cout<<coinChange(set,count,4,26);
return 0;
}
#include <iostream>
using namespace std;
int numOfWays(int n, int coin) {
if(coin == 1) return 1;
int i, ways = 0, maxNum = n /coin, nextCoin = ( coin == 25 ? 10 : (coin == 10 ? 5 : (coin == 5 ? 1 : 1)));
for(i = 0; i <= maxNum; i++)
ways += numOfWays(n - i * coin, nextCoin);
return ways;
}
int main() {
int n;
cin >> n;
cout << numOfWays(n, 25);
return 0;
}
This looks like a good case of where greedy *would* work, Anon. Care to explain why not?
Well...actually this Example should be a good case to use greedy. For 40 and {25,15}, first time get one 25 and then get one 15. That's it!
Hey I think it is a typical case of unbounded knapsack with limits on the number of coins in each denomination to be chosen
- Sriram November 15, 2011