## Oracle Interview Question for Software Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

DP Soln - O(N^3)

``````public static void main(String[] args) throws java.lang.Exception {
int[] coins = { 1, 2, 3 };
int[] count = { 1, 1, 3 };
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[sum + 1][n + 1];

int ret = 0;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= count[j - 1]; k++) {
if (i > coins[j - 1] * k)
dp[i][j] += dp[i - coins[j - 1] * k][j - 1];

if (i == coins[j - 1] * k)
dp[i][j] += 1;

}
}
}
for (int i = 0; i <= n; i++) {
ret += dp[sum][i];
}
return ret;
}``````

Comment hidden because of low score. Click to expand.
0

Doesn't work for coins: {25, 10, 5}, count: {1,5,3}, sum:70

Expected: 6 , {25 + 10 + 10 + 10 + 10 + 5}
Output: 2

Comment hidden because of low score. Click to expand.
0

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}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Doesn't work for coins with same number of count. For example if I want to run it for coins = {1,2,4,8} and count = {2,2,2,2}, it gives output as 2 whereas it should be 3

Comment hidden because of low score. Click to expand.
1
of 1 vote

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];
}
}

Comment hidden because of low score. Click to expand.
0

I see the solution provided here is functional.

My questions is:
(1) - how do we (can we) modify to get optimal coins ?
(2) - how do we modify to get a list of the individual coins in the payout solution.

Many thanks!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.