Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
This is a DP solution. Call it like the recursive solution above.
int count(vector<int>& coins, int sum) {
int size = coins.size();
vector<int> table(sum+1);
table[0] = 1;
for (int i=0; i<size; i++) {
for (int j=coins[i]; j<=sum; j++) {
table[j] += table[j-coins[i]];
}
}
return table[sum];
}
For 5 the total combinations without duplicates is 8 and for 4 it is 5
Here is the code using dynamic programming
#include<stdio.h>
#include<stdlib.h>
int noOfDenominations(int *dp,int *denom,int value,int length1)
{
if(value==0)
return 0;
if(value<0)
return 0;
if(dp[value]!=0)
return dp[value];
int i;
for(i=0;i<length1;i++)
{
int diff=value-denom[i];
if(diff==0)
dp[value]=dp[value]+1;
else if((value-denom[i])>=denom[i])
dp[value]=dp[value]+noOfDenominations(dp,denom,value-denom[i],length1);
}
return dp[value];
}
int main()
{
int value=4;
int denominations[]={1,2,3};
int *dp=(int *)calloc(value+1,sizeof(int));
printf("%d",noOfDenominations(dp,denominations,value,3));
}
public static void main(String[] args) {
final int[] coins = new int[] { 1, 2,3 };
System.out.println(" Combinations :" + getCoinCombinations(0, coins, 5));
}
static int getCoinCombinations(final int start, final int[] coins,
int amount) {
int result = 0;
if (amount == 0) {
return 1;
}
for (int i = start; i < coins.length; i++) {
if (amount >= coins[i]) {
result += getCoinCombinations(i, coins, amount - coins[i]);
}
}
return result;
}
public static int findPossibleWays(int val , int [] denominations){
int [] dp = new int [val+1];
dp[0] = 0;
for (int i =1; i<=val ;++i){
for (int j =0 ;j<denominations.length ;++j){
if (i>=denominations[j]){
dp [i] =dp[i]>dp[i-denominations[j]]+1?dp[i]:dp[i-denominations[j]]+1;
}
}
}
return dp[val];
}
Right, this does not work.
Why?
Because this counts 1,1,2 more than once, example: {1,1,2}, {1,2,1}
I just fixed the code, please help to test
public static int findPossibleWays(int val , int [] denominations){
int [] dp = new int [val+1];
dp[0] = 1;
for (int i =1 ;i<=val ;++i){
for (int j = 0;j<denominations.length ;++j){
if(i>=denominations[j]&&dp[i-denominations[j]]>0){
dp[i]++;
}
}
}
return dp[val];
}
Assuming denominations have single digit numbers for the convenience of printing -
#include<stdio.h>
#include<stdint.h>
#include<string.h>
#include<stdlib.h>
#define STR_SIZE 35;
#define ndenoms 3
char* appendStr(char *str,char c)
{
int l;
char* pstr = NULL;
l=strlen(str);
pstr = (char*)malloc(35*sizeof(char));
strcpy(pstr,str);
pstr[l]=c;
pstr[l+1]='\0';
return pstr;
}
void findAllpossibleWays(int lastInt, int amt, int *denom,int demonlen ,char* str)
{
int l,i,num;
char* pstr=NULL;
if(amt<=0){
if(amt==0)
{
printf("%s success \n", str);
}
else
{
printf("FAIL");
}
return;
}
else
{
for(i=0;i<demonlen;i++)
{
num = denom[i];
if(amt>=num && lastInt<=num)
{
pstr=appendStr(str,num+48);
//printf("%d,",num);
findAllpossibleWays(num,amt-num,denom, demonlen, pstr);
free(pstr);
}
}
}
}
int main()
{
int amount = 5;
int denom[ndenoms]={1,2,3};
char str[1]= "\0";
findAllpossibleWays(0,amount,denim,ndenoms,str);
}
for convenience i took denominations as boolean array
Split(int amount, bool[] denominations){
int[,] dp = new int[amount + 1, denominations.Length];
for (int i = 0; i < denominations.Length; i++)
dp[0, i] = 1;
for (int i = 1; i <= amount; i++)
for (int j = 1; j < denominations.Length; j++){
dp[i, j] = dp[i, j - 1];
if (denominations[j] && i>=j)
dp[i, j] += dp[i - j, j];
}
return dp[amount, denominations.Length-1];
}
The question says find all possible ways, and not the number.
Here is non-optimal recursive, generational python code. Dynamic programming can be used to generated all the combinations too.
def combinations(N, coins):
if len(coins) == 1:
if N % coins[0] != 0:
return
else:
yield [coins[0]]*(N/coins[0])
return
if N < 0:
return
for s in combinations(N, coins[1:]):
yield s
for s in combinations(N-coins[0], coins):
yield [coins[0]] + s
#include <vector>
#include <iostream>
using namespace std;
int FindCombination(int amount, const vector<int>& domination, int max_dom_index, vector<int>* combination) {
if (amount == 0) {
int comb_size = combination->size();
if (comb_size == 0) // if original amount is 0, the combination count may be zero or infinite big number, which depends on your definition.
return 0;
// find a combination, output the combination.
for (int i = 0; i < comb_size-1; ++i) {
cout << (*combination)[i] << ",";
}
cout << (*combination)[comb_size-1] << endl;
return 1;
}
int ret = 0;
// backtracking by trying domination in descending order, thus eliminates duplications.
for (int i = max_dom_index; i >= 0; --i) {
if (amount >= domination[i]) {
combination->push_back(domination[i]);
ret += FindCombination(amount-domination[i], domination, i, combination);
combination->pop_back();
}
}
return ret;
}
int FindAllCombinations(int amount, const vector<int>& domination) {
if (domination.size() == 0)
return 0;
vector<int> combination;
return FindCombination(amount, domination, static_cast<int>(domination.size())-1, &combination);
}
int main (){
vector<int> dom; // assuming dominations have already been sorted.
dom.push_back(1);
dom.push_back(2);
dom.push_back(3);
int num = FindAllCombinations(7, dom);
cout << "====================================" << endl;
cout << "There are " << num << " combinations." << endl;
return 0;
}
#include <iostream>
using namespace std;
int findWay(int amount, int den[], int maxDen)
{
if (maxDen == 0) return 1;
int sum = 0;
for (int i = amount/den[maxDen]; i>=0; i--)
sum += findWay(amount-(i*den[maxDen]), den, maxDen-1);
return sum;
}
int main() {
int myDen[3] = {1, 2, 3};
cout<<"There are "<<findWay(5, myDen, 2)<<" ways."<<endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class DenominationsOfCoins {
Set<Integer> mAllowedDenominations;
DenominationsOfCoins(){
mAllowedDenominations = new TreeSet<Integer>();
mAllowedDenominations.add(1);
mAllowedDenominations.add(2);
mAllowedDenominations.add(3);
}
public static void main(String[] args){
DenominationsOfCoins obj = new DenominationsOfCoins();
obj.findPossibleCombiations(5);
}
int findPossibleCombiations(int num){
List<String> possibilities = doFindPossibleCombiations(num, 0);
for(String str:possibilities){
System.out.println(str);
}
return possibilities.size();
}
List<String> doFindPossibleCombiations(int num, int sumWith){
List<String> possibilities = new ArrayList<String>();
for(int denom:mAllowedDenominations){
if(denom > num){
break;
}
if(denom < sumWith){
continue;
}
int remainder = num - denom;
if(remainder==0){
possibilities.add(String.format("%d", denom));
break;
} else if(remainder >= denom){
List<String> possibilitiesWithRemainder = doFindPossibleCombiations(remainder, denom);
for(String str:possibilitiesWithRemainder){
possibilities.add(String.format("%d, %s", denom, str));
}
}
}
return possibilities;
}
}
DFS
enum{ONE=1,TWO,THREE};
void find_path(int remain, int type, vector<int>&res)
{
if(remain < type)
return;
if(remain-type == 0)
{
//found one solution print
for(size_t i = 0; i < res.size();i++)
{
cout<<res[i]<<" ";
}
cout<<type<<endl;
return ;
}
res.push_back(type);
for(int i=1;i<=type;i++){find_path(remain-type, i, res);}
res.pop_back();
}
int main()
{
vector<int> res;
find_path(5, ONE, res);
find_path(5, TWO, res);
find_path(5, THREE, res);
}
This code is in java. Logic is simple, using recursion.
public void printAllDenom(final List<Integer> numbers, int sum, List<Integer> result, int index)
{
if (sum < 0) return;
if (index > numbers.size() - 1) return;
if (sum == 0)
{
System.out.println(result); // When sum is 0, we have one solution in result list.
return;
}
if (numbers.get(index) != -1)
{
printAllDenom(numbers, sum, result, index + 1);
result.add(numbers.get(index));
printAllDenom(numbers, sum - numbers.get(index), result, index);
result.remove(result.size() - 1);
}
}
#procedure for generating subsets
out = []
def subset(s,i,ss) :
global out
if i == len(s):
return
else :
ss.append(s[i])
out.append(list(ss))
i = i+1
subset(s,i,ss)
ss.pop()
subset(s,i,ss)
#intialising variables
s = []
ss = []
target = 5
denom = [1,2,3]
#generate the list [1,1,1,1,1,2,2,3]
for var in denom :
fac = target / var
for i in range(0,fac) :
s.append(var)
#generate the all subsets of list [1,1,1,1,1,2,2,3]
subset(s,i,ss)
#remove duplicate lists in the above generated subsets
out = set(tuple(x) for x in out)
out = [list(x) for x in out]
#increment the count if the sum of the subset is 5
cnt = 0
for x in out :
if sum(x) == target :
cnt = cnt + 1
print cnt
import math
def findAllDenomination(val, allDenominations):
possibleDenominations = []
if val == 0:
return possibleDenominations
tempDenominations = allDenominations.copy();
theDenomination = tempDenominations.pop();
highestDenominations = math.trunc(val/theDenomination);
if len(tempDenominations) == 0:
if val%theDenomination == 0:
currentDenominations = [];
for i in range(0, highestDenominations):
currentDenominations.append(theDenomination);
possibleDenominations.append(currentDenominations);
else:
for i in range(0, highestDenominations+1):
if (val - theDenomination*i) == 0:
currentDenominations = [];
for j in range(0, i):
currentDenominations.append(theDenomination);
possibleDenominations.append(currentDenominations);
else:
allPossibleLowerDenominations = findAllDenomination(val - theDenomination*i, tempDenominations)
if len(allPossibleLowerDenominations) != 0:
currentDenominations = [];
for j in range(0, i):
currentDenominations.append(theDenomination);
for lowerPossDenominations in allPossibleLowerDenominations:
lowerPossDenominations.extend(currentDenominations);
possibleDenominations.append(lowerPossDenominations);
return possibleDenominations
possDenominations = findAllDenomination(5, [1,2,3])
print(possDenominations)
int getCount(int[] denom, int value) {
return getCount(denom, 0, value);
}
int getCount(int[] denom, int index, int reqValue) {
int value = 0;
int count = 0;
if (index == denom.length) {
return 0;
}
while(value < reqValue)
{
value += denom[index];
}
if (reqValue == value)
count++;
value -= denom[index];
while(value >= 0) {
count += getCount(denom, index+1, reqValue-value);
value -= denom[index];
}
return count;
}
a recursive solution in java.
*assume denom is sorted or we can just sort it
public static void getForms(int n, ArrayList<Integer> denom, int start, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
if(n==0){
result.add(new ArrayList<Integer>(current));
}
else{
for(int i=start; i<denom.size(); i++){
if(n>=denom.get(i)){
current.add(denom.get(i));
getForms(n-denom.get(i), denom, i, current, result);
current.remove(current.size()-1);
}
}
}
}
public static void main(String[] args){
ArrayList<Integer> denom = new ArrayList<Integer>();
denom.add(1); denom.add(2); denom.add(3);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
getForms(5, denom, 0, new ArrayList<Integer>(), result);
int i=1;
}
//Note denominations should be sorated ascending
class Finder{
int[][] dp; // initialized by -1
int[] denominations;
int find(int amount, int[] denominations){
this.amount = amount;
this.denominations = denominations;
this.dp = new int[amount][denominations.length]
for(int i = 0; i < amount; i++){
for(int j = 0; j < denominations.length; j++){
dp[i][j] = -1;
}
}
return _find(amount, 0);
}
private int _find(int amount, int index){
int result = 0;
if(amount == 0){
dp[amount][index] = 1;
return 1;
}else if(amount < 0){
dp[amount][index] = 0;
return 0;
}
if(dp[amount][index] != -1){
return dp[amount][index];
}
for(int i=index;i < denominations.length;i++){
result += _find(amount-denominations[i], i+1);
}
dp[amount][index] = result;
return result;
}
}
A recursive solution.
- Chiharu December 16, 2013