Oracle Interview Question for Software Developers


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

- sudip.innovates September 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- foo.bar August 05, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- Anonymous November 07, 2019 | Flag
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

- Guri September 27, 2020 | Flag
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;
}

- Alex September 27, 2017 | Flag Reply
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;
}

- Chris September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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];
}
}

- Pranav Gupta October 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- bobandverns October 30, 2020 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More