Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
import java.util.HashMap;
public class CoinCombo {
public static void main(String[] args) {
int coins[] = {10, 50, 100, 500};
int qty [] = {5,3,2,2};
printSum(coins,qty);
}
static void printSum(int coins[], int qty[]){
int value=1;
int sum=0;
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
map.put(5, 6);
if(coins == null || qty == null){
return;
}
for(int i=0;i<=5;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=2;k++){
for(int l=0;l<=2;l++){
sum=10*i+50*j+100*k+500*l;
System.out.println(i+" " +j+" "+k+" "+l+" = "+sum);
if(map.containsKey(sum)){
//System.out.println(map.get(sum));
map.put(sum,map.get(sum)+1);
}else{
map.put(sum,value);
}
}
}
}
}
System.out.println(map);
}
}
using backtracking and recursion we can do this with simple code.Time complexity is 2^(total quantity of coins), in this case it is 12
public class CoinChangeQuantityGiven {
public static void generateSums(int[] coins,int[] quantity,int i,int sum,Set<Integer> set){
if(i==coins.length){
set.add(sum);
return;
}
if(quantity[i]==0){
set.add(sum);
generateSums(coins, quantity, i+1, sum,set);
}else{
set.add(sum);
quantity[i]=quantity[i]-1;
generateSums(coins, quantity, i, sum+coins[i],set);
//backtrack. now increase the quantity since we havent used the ith coin and moving to next coin
quantity[i]=quantity[i]+1;
generateSums(coins, quantity, i+1, sum, set);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] coins={10,50,100,500};
int[] quantity={5,3,2,2};
Set<Integer> set=new HashSet<>();
generateSums(coins, quantity, 0, 0,set);
System.out.println(set);
}
}
def get_all_sums(ex_coins, quantity):
def get_as_list(ex_coins, quantity):
result = []
for i in range(len(ex_coins)):
result.extend([ex_coins[i]] * quantity[i])
return result
def extend_sums(sums, n):
res = set()
for s in sums:
res.add(n + s)
res.add(n)
return sums.union(res)
coins = get_as_list(ex_coins, quantity)
return reduce(extend_sums, coins, set())
public class CoinCombo {
public static void main(String[] args) {
int coins[] = {10, 50, 100, 500};
int qty [] = {5,3,2,2};
printSum(coins,qty);
}
static void printSum(int coins[], int qty[]){
if(coins == null || qty == null){
return;
}
//N * N coins only...
for(int i=0;i <coins.length; i++){
int baseTempQty = qty[i];
//iterate on coin Quantity for base Coin
for(int baseCoinQty=1; baseCoinQty<=baseTempQty;baseCoinQty++){
int baseCombo = coins[i]*baseCoinQty;
System.out.println("use coin "+ coins[i]+" Quantity="+baseCoinQty+" Total= "+baseCombo);
//iterate on coin other than base coin
for(int j=i+1;j<coins.length;j++){
int secTempQty = qty[j];
//iterate on coin Quantity for second Coin
for(int secCoinQty=1; secCoinQty<=secTempQty;secCoinQty++){
int secCombo = coins[j]* secCoinQty + baseCombo;
System.out.println("use coin "+ coins[i]+" baseCoinQty="+baseCoinQty
+" and coins ="+coins[j] +" secCoinQty="+secCoinQty
+" Total= "+secCombo);
}
}
}
}
}
}
public class CoinCombo {
public static void main(String[] args) {
int coins[] = {10, 50, 100, 500};
int qty [] = {5,3,2,2};
printSum(coins,qty);
}
static void printSum(int coins[], int qty[]){
if(coins == null || qty == null){
return;
}
//N * N coins only...
for(int i=0;i <coins.length; i++){
int baseTempQty = qty[i];
//iterate on coin Quantity for base Coin
for(int baseCoinQty=1; baseCoinQty<=baseTempQty;baseCoinQty++){
int baseCombo = coins[i]*baseCoinQty;
System.out.println("use coin "+ coins[i]+" Quantity="+baseCoinQty+" Total= "+baseCombo);
//iterate on coin other than base coin
for(int j=i+1;j<coins.length;j++){
int secTempQty = qty[j];
//iterate on coin Quantity for second Coin
for(int secCoinQty=1; secCoinQty<=secTempQty;secCoinQty++){
int secCombo = coins[j]* secCoinQty + baseCombo;
System.out.println("use coin "+ coins[i]+" baseCoinQty="+baseCoinQty
+" and coins ="+coins[j] +" secCoinQty="+secCoinQty
+" Total= "+secCombo);
}
}
}
}
}
}
import java.util.HashMap;
public class CoinCombo {
public static void main(String[] args) {
int coins[] = {10, 50, 100, 500};
int qty [] = {5,3,2,2};
printSum(coins,qty);
}
static void printSum(int coins[], int qty[]){
int value=1;
int sum=0;
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
map.put(5, 6);
if(coins == null || qty == null){
return;
}
for(int i=0;i<=5;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=2;k++){
for(int l=0;l<=2;l++){
sum=10*i+50*j+100*k+500*l;
System.out.println(i+" " +j+" "+k+" "+l+" = "+sum);
if(map.containsKey(sum)){
//System.out.println(map.get(sum));
map.put(sum,map.get(sum)+1);
}else{
map.put(sum,value);
}
}
}
}
}
System.out.println(map);
}
}
import java.util.*;
public class CoinSum
{
private static int [] coin_values;
private static int [] coin_quantity;
private static int coin_type;
private static int count = 0;
private static HashMap<Integer, ArrayList<Integer>> result_stacks = new HashMap<>();
public static void main(String []args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the no. of type of coins");
coin_type = sc.nextInt();
coin_values = new int[coin_type];
coin_quantity = new int[coin_type];
System.out.println("Enter the value of coins");
int i = coin_type;
while(i > 0) {
coin_values[coin_type-i] = sc.nextInt();
i--;
}
System.out.println("Enter the quantity of coins");
i = coin_type;
while(i > 0) {
coin_quantity[coin_type-i] = sc.nextInt();
i--;
}
sc.close();
calculateSum(0);
ArrayList<Integer> results = result_stacks.get(0);
for (int result : results) {
System.out.println(result);
}
}
private static void calculateSum(int type) {
if (type < coin_type) {
ArrayList<Integer> new_results = new ArrayList<>();
for (int i=1; i <= coin_quantity[type]; i++) {
//System.out.println(++count);
int sum = i * coin_values[type];
calculateSum(type + 1);
ArrayList<Integer> next_level_results = result_stacks.get(type + 1);
if (next_level_results != null) {
for (int result : next_level_results) {
new_results.add(sum + result);
}
} else {
new_results.add(sum);
}
}
result_stacks.put(type, new_results);
}
}
}
+ (NSSet<NSNumber*>*) coinComboWith:(NSArray<NSNumber*>*) values counts:(NSArray<NSNumber*>*) counts{
NSSet<NSNumber*>* result = [NSSet setWithObject:@(0)];
for(int i = 0; i < counts.count; i++){
NSUInteger value = values[i]. unsignedIntegerValue;
NSUInteger count = counts[i].unsignedIntegerValue;
NSMutableSet<NSNumber*>* stepResult = [result mutableCopy];
for(NSUInteger j = 0; j <= count; j++){
NSInteger coinSum = j * value;
for(NSNumber* prevStepValue in result){
NSUInteger prevStepValueI = prevStepValue.unsignedIntegerValue;
[stepResult addObject:@(coinSum + prevStepValueI)];
}
}
result = stepResult;
}
return result;
}
I think we can also do memorization to avoid repeating tons of operations. I didn't check the code but you get the idea:
private Set<Integer> sums;
private int[] coinValues, quantity;
private int size;
private HashSet<Integer>[] memorization;
public Set<Integer> getPossibleSums(int[] coinValues, int[] quantity){
this.coinValues = coinValues;
this.quantity = quantity;
this.size = coinValues.length;
sums = new HashSet<Integer>();
memorization = new HashSet<Integer>[size];
possibleSums(0, 0);
return sums;
}
public void possibleSums(int n, int sum){
if(n != size){
if(memorization[n] == null || !memorization[n].contains(sum)){
int coinValue = coinValues[n];
for(int i = 0; i <= quantity[n]; i++){
int nextSum = sum + i * coinValue;
possibleSums(n + 1, nextSum);
if(memorization[n + 1] == null)
memorization[n + 1] = new HashSet<Integer>();
memorization[n + 1].add(nextSum);
}
}
}else{
sums.add(sum);
memorization
}
}
public List<int> CoinsSums(int[] coins, int[] quantities)
{
if (coins == null && quantities == null)
return null;
return GetSums(coins, quantities, 0, new Dictionary<int, List<int>>());
}
static List<int> GetSums(int[] coins, int[] quantities, int n, Dictionary<int, List<int>> cache)
{
var res = new List<int>();
if (n == quantities.Length)
{
return new List<int> { 0 };
}
if (cache.ContainsKey(n))
{
return cache[n];
}
for (var i = 1; i <= quantities[n]; i++)
{
var val = i * coins[n];
res.Add(val);
for (var j = n + 1; j < quantities.Length; j++)
{
var values = GetSums(coins, quantities, j, cache);
foreach (var s in values)
{
res.Add(s + val);
}
}
}
cache.Add(n, res);
return res;
}
public static void main(String[] args) {
int val[]={2,5};
int quan[]={2,3};
HashSet<Integer> set=new HashSet<Integer>();
findSum(val,quan,set,0,0);
}
private static void findSum(int[] val, int[] quan, HashSet<Integer> set, int sum,int ind) {
set.add(sum);
if(ind>=val.length) return;
for(int i=0;i<=quan[ind];i++){
sum+=val[ind]*i;
findSum(val, quan, set, sum, ind+1);
sum-=val[ind]*i;
}
}
def possible_sums(coins, cache):
if len(coins) == 0:
return [0]
key = len(coins)
if key not in cache:
cache[key] = []
coin = coins[0]
for i in xrange(coin[0] + 1):
coin_sum = coin[1]*i
other_sums = possible_sums(coins[1:], cache)
for os in other_sums:
cache[key].append(os + coin_sum)
return cache[key]
coins = [(5, 10), (3, 50), (2, 100), (2, 500)]
print possible_sums(coins, dict())
O(2^n)
public class CoinAllPossibleSum {
static int count = 0;
public static void main(String[] args) {
int[] coins={10,20};
int[] quantity={5,3};
//int[] coins={10, 20, 40};
//int[] quantity={2, 2, 1};
Set<Integer> set=new HashSet<>();
generateSums(coins, quantity, 0, 0,set);
System.out.println(set);
System.out.println(count);
}
private static void generateSums(int[] coins, int[] quantity, int sum, int pos, Set<Integer> set) {
count = count + 1;
set.add(sum);
if(pos == coins.length) return;
for(int q=1; q <= quantity[pos]; q++) {
//sum = sum + coins[pos];
generateSums(coins, quantity, sum + (q * coins[pos]), pos + 1, set);
}
//sum = sum - (coins[pos] * quantity[pos]);
}
}
I did it with and without dynamic programming in Ruby
def sums coins, quants, pos = 0, count = 0
res = [0]
res += sums(coins, quants, pos, count+1).map{ |el| el += coins[pos]} if count < quants[pos]
res += sums(coins, quants, pos+1, 0) if pos < coins.length - 1
res.uniq.sort.reverse
end
def sums_dp coins, quants, hash = {}, pos = 0, count = 0
res = [0]
if count < quants[pos]
value = hash[[pos, count+1]] || sums(coins, quants, hash, pos, count+1).map{ |el| el += coins[pos]}
res += value
end
if pos < coins.length - 1
value = hash[[pos+1, 0]] || sums(coins, quants, hash, pos+1, 0)
res += value
end
hash[[pos, count]] = res.uniq.sort.reverse
end
A coin of 500 (cents/pence/whatever)? That reminds me of a guy who
forged a $700 banknote. He went to a bank and changed it for two $350 notes.
#include "iostream"
#include "set"
int main()
{
int coins[] = { 1, 5, 10, 50 };
int quant[] = { 5, 3, 2, 2 };
int N = sizeof coins / sizeof coins[0];
std::set<int> sums;
sums.insert(0);
for (int i = 0; i < N; i++)
{
std::set<int> upd_sums;
for (int j = 0; j <= quant[i]; j++)
{
for (auto it = sums.begin(); it != sums.end(); ++it)
{
upd_sums.insert(*it + j * coins[i]);
}
}
std::swap(sums, upd_sums);
}
for (auto it = sums.begin(); ++it != sums.end(); ) // Skip 0
{
std::cout << *it << ' ';
}
std::cout << std::endl << "Total of " << sums.size() - 1 << " combinations" << std::endl;
return 0;
}
I found 3 solutions. The best one is the iterative solution. Written in Javascript
/*
Best solution: We take one coin at a time.
Then we add to the result set every value already stored in the set with the coin value
*/
function iterativeSolution(coins, qty){
qty = qty.slice(); // Copy of the qty because we dont want to modify the array passed by reference
function getOneCoin(c, q){
for (var i = 0 ; i < c.length; i++){
if (q[i] !== 0){
q[i]--;
return coins[i];
}
}
}
var result = new Set();
while(Math.max(...qty) !== 0){ // While there is at least one coin
var coin = getOneCoin(coins, qty);
[...result].forEach(sum=>{ // we add to the result set every value already stored in the set plus the coin value
result.add(sum + coin);
});
result.add(coin); // And finally we add the coin value
}
return result;
}
// Not so efficient solution
function memoSolution(coins, qty){
function mergeSets(set1, set2){
var big = (set1.size > set2.size) ? set1 : set2;
var small = (set1.size > set2.size) ? set2 : set1;
for (var item of small)
big.add(item);
return big;
}
var memo = {};
function possibleSums(coins, qty, sum){
if (memo[qty.toString()])
return memo[qty.toString()];
if (Math.max(...qty) === 0)
return new Set();
var resultSet = new Set();
for (var i = 0; i < coins.length; i++){
if (qty[i] > 0){
var newQty = qty.slice();
newQty[i]--;
var partialSet = possibleSums(coins, newQty, sum + coins[i]);
memo[newQty.toString()] = partialSet;
partialSet.add(coins[i]);
partialSet.add(coins[i] + sum);
resultSet = mergeSets(partialSet, resultSet);
}
}
memo[qty.toString()] = resultSet;
return resultSet;
}
return possibleSums(coins, qty, 0);
}
// Bad solution
function recursiveSolution(coins, qty){
function mergeSets(set1, set2){
var big = (set1.size > set2.size) ? set1 : set2;
var small = (set1.size > set2.size) ? set2 : set1;
for (var item of small)
big.add(item);
return big;
}
function possibleSums(coins, qty, sum){
if (Math.max(...qty) === 0)
return new Set();
var resultSet = new Set();
for (var i = 0; i < coins.length; i++){
if (qty[i] > 0){
var newQty = qty.slice();
newQty[i]--;
var partialSet = possibleSums(coins, newQty, sum + coins[i]);
partialSet.add(coins[i]);
partialSet.add(coins[i] + sum);
resultSet = mergeSets(partialSet, resultSet);
}
}
return resultSet;
}
return possibleSums(coins, qty, 0);
}
// Testing
var c = [10, 50, 100, 500];
var q = [5, 3, 2, 2];
console.log(iterativeSolution(c,q).size);
console.log(memoSolution(c,q).size);
console.log(recursiveSolution(c,q).size);
/*
Given a list of coin values, and quantity of each type of coin. Write a
program to return the set of all possible sums which can be made using those
coins.
ex. coins = [10, 50, 100, 500]
quantity = [5, 3, 2, 2]
sum could be 400 , 300 ,200 , 100
*/
#include <stdlib.h>
#include <iostream>
using namespace std;
int main(){
int coins[4] = {500,100,50,10};
int quantity[4] = {2,2,3,5};
int answer[4];
int sum;
cout<<"enter the sum: ";
cin>>sum;
for (int i=0;i<4;i++){
if (coins[i]<=sum){
int temp = quantity[i];
int temp1 = 0;
while (temp != 0 && sum >= coins[i]){
sum = sum-coins[i];
temp1++;
temp--;
}
answer[i] = temp1;
}
else{
answer[i]=0;
}
}
if (sum!=0){
cout<<"no solution available"<<endl;
}
else{
for (int i=0;i<4;i++){
cout<<coins[i]<<" ";
cout<<answer[i]<<endl;
}
cout<<endl;
}
return(0);
}
/*
Given a list of coin values, and quantity of each type of coin. Write a
program to return the set of all possible sums which can be made using those
coins.
ex. coins = [10, 50, 100, 500]
quantity = [5, 3, 2, 2]
sum could be 400 , 300 ,200 , 100
*/
#include <stdlib.h>
#include <iostream>
using namespace std;
int main(){
int coins[4] = {500,100,50,10};
int quantity[4] = {2,2,3,5};
int answer[4];
int sum;
cout<<"enter the sum: ";
cin>>sum;
for (int i=0;i<4;i++){
if (coins[i]<=sum){
int temp = quantity[i];
int temp1 = 0;
while (temp != 0 && sum >= coins[i]){
sum = sum-coins[i];
temp1++;
temp--;
}
answer[i] = temp1;
}
else{
answer[i]=0;
}
}
if (sum!=0){
cout<<"no solution available"<<endl;
}
else{
for (int i=0;i<4;i++){
cout<<coins[i]<<" ";
cout<<answer[i]<<endl;
}
cout<<endl;
}
return(0);
}
public static void main(String[] args){
int[] coins = {10, 50, 100, 500};
int[] quantity = {5, 3, 2, 2};
Set<Integer> sums = new HashSet<Integer>();
possibility(coins, quantity, 0, 0, sums);
System.out.println(sums);
}
public static Set<Integer> possibility(int[] coins, int[] quantity, int index, int sum, Set<Integer> sums){
sums.add(sum);
int n = coins.length;
if(index > n-1)
return sums;
for(int i = index; i < n; i++){
int count = quantity[i];
for(int j = 1; j <= count; j++){
sums = possibility(coins, quantity, i+1, sum+coins[i]*j, sums);
sums = possibility(coins, quantity, i+1, sum, sums);
}
}
return sums;
}
- mrsurajpoudel.wordpress.com November 18, 2016unordered_set<int> possible_sums(int i, vector<int>& coins, vector<int>& quantity) { if(i == int(coins.size())) return unordered_set<int>{0}; auto remaining = possible_sums(i + 1, coins, quantity); unordered_set<int> ret_set; for(int q = 0; q <= quantity[i]; q++) { for(int next_sum : remaining) { int curr = next_sum + q * coins[i]; if(ret_set.find(curr) == ret_set.end()) ret_set.insert(curr); } } return ret_set; } int main(int argc, char** argv) { vector<int> coins{10, 50, 100, 500}; vector<int> quantity{5, 3, 2, 2}; auto ret = possible_sums(0, coins, quantity); for(int r : ret) { cout << r << " "; } cout << "\n"; }