Oracle Interview Question
Software DevelopersCountry: India
Interview Type: In-Person
Doesn't work for coins: {25, 10, 5}, count: {1,5,3}, sum:70
Expected: 6 , {25 + 10 + 10 + 10 + 10 + 5}
Output: 2
The solution is for number of ways to get required sum ,not minimum coins required to get sum.
So for 70 it would be {25 + 10 + 10 + 10 + 10 + 5} & {25+10+10+10+5+5+5}
based on limited knapsack problem.
public class CoinChangeLimitedSupply {
public static void main(String[] args) throws java.lang.Exception {
int[] coins = { 1, 2, 4, 8 };
int[] count = { 2, 2, 2, 2 };
int sum = 9;
int n = countWays(coins, count, sum);
System.out.println(n);
}
/**
* Coin change problem with finite number of coins available denominations
* of coins = {1,2,3} count of coins = ={1,1,3} find the number of ways for
* getting change for S=6
*/
public static int countWays(int[] coins, int[] count, int sum) {
int n = coins.length;
int[][] dp = new int[n + 1][sum + 1];
int ret = 0;
dp[0][0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = 0; i <= sum; i++) {
dp[j][i] += dp[j-1][i];
}
for (int k = 1; k <= count[j - 1]; k++) {
int initial = coins[j - 1] * k;
for (int i = initial; i <= sum; i++) {
dp[j][i] += dp[j-1][i - initial];
}
}
}
for(int i=0; i<=n; i++) {
for(int j=0; j<=sum; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println("");
}
// for (int i = 0; i <= n; i++) {
// ret += dp[i][sum];
// }
return dp[n][sum];
}
}
Top down DP. Time and space: O(number_of_coins * amount * max(count_of_coins) ).
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
class Coin
{
public:
Coin(int denom, int supply)
{
denom_ = denom;
supply_ = supply;
}
int denom_;
int supply_;
};
int WaysCount(vector<Coin> const &coins, int16_t amount, int16_t idx, int supply, unordered_map<uint64_t, int> &memo)
{
if (amount < 0 ||
idx >= coins.size() ||
supply < 0)
{
return 0;
}
if (amount == 0) {
return 1;
}
if (supply == 0) {
++idx;
if (idx >= coins.size()) {
return 0;
}
supply = coins[idx].supply_;
}
uint64_t memo_key = ((((uint64_t)amount << 16) | idx) << 32) | supply;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
int count = WaysCount(coins, amount - coins[idx].denom_, idx, supply - 1, memo) +
WaysCount(coins, amount, idx + 1, idx + 1 < coins.size() ? coins[idx + 1].supply_ : 0, memo);
memo[memo_key] = count;
return memo[memo_key];
}
int main()
{
unordered_map<uint64_t, int> memo;
vector<Coin> coins = {Coin(1, 1), Coin(2, 1), Coin(3, 3)};
cout << WaysCount(coins, 6, 0, coins[0].supply_, memo) << "\n";
return 0;
}
there is a pseudo polynomial algorithm for this. Basically you apply each coin n times
and mark the target value you get by adding up the number of ways you can get there.
for the sample:
dp[0][0..S] = 0
dp[0][0] = 1, base case
-- use coin with value 1
dp[1][0..S] = dp[0][0..S]
dp[1][1] = dp[0][1] + dp[0][0] + 1 = 1
-- use coin with value 2
dp[2][0..S] = dp[1][0..S]
dp[2][2] = dp[1][2] + dp[1][0] + 2 = 1
dp[2][3] = dp[1][3] + dp[1][1] + 2 = 1
-- use 1 coin with value 3
dp[3][0..S] = dp[2][0..S]
dp[3][3] = dp[2][3] + dp[2][0] + 3 = 2
dp[3][4] = dp[2][4] + dp[2][1] + 3 = 1
dp[3][5] = dp[2][5] + dp[2][2] + 3 = 1
dp[3][6] = dp[2][6] + dp[2][3] + 2 = 1
-- use 2 coins with value 3 = value 6
dp[4][0..S] = dp[2][0..S]
dp[4][6] = dp[3][6] + dp[3][0] + 6 = 2
result = dp[4][6] = 2
in c++ 11
#include <vector>
#include <iostream>
using namespace std;
typedef unsigned int uint;
unsigned int numberOfWaysForChange(const vector<pair<uint, uint>>& coins, uint S)
{ // pair<int, int>: 1st: value, 2nd: count
if (S < 1) return 0;
vector<int> dpc(S + 1, 0); // current
vector<int> dpl(S + 1, 0); // last
dpl[0] = 1;
for (const auto& coin : coins) {
for (uint value = coin.first, c = 0; c < coin.second; value += coin.first, ++c) {
for (uint s = 0; s < S; s++) {
if (dpl[s] == 0) continue;
dpc[s] = dpl[s];
if (s + value > S) continue;
dpc[s + value] = dpl[s + value] + dpl[s];
}
swap(dpl, dpc);
}
}
return dpl.back();
}
int main()
{
cout << numberOfWaysForChange({ {1,1},{2,1},{3,3} }, 6) << endl;
}
DP Soln - O(N^3)
- sudip.innovates September 29, 2017