Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
Given a sum s that can be combined by 5s and 3s there exist non-negative integers x,y such that s = 5*x + 3*y. From this if follows that (s-5*x)%3 = 0. You can check all possible x and examine the modulo.
A sample code is shown below:
public boolean isSumOfCoins(int s) {
int final A = 5;
int final B = 3;
if (s%A == 0 || s%B == 0)
return true;
for (int x = 0; x<s/A; x++)
if ((s-A*x)%B == 0)
return true;
return false;
}
Nice Job. it takes O(n/5)=O(n)
As both 3 and 5 are prime numbers, another approach can be finding prime factors of n. It can be done by O(lgn*sqrt(n)). If n has prime factors greater than 5 then it can not be spiltted.
If not, the number of necessary coins is number of 2s power 2 multiply by number of 3s and 5s. Of course this doesn't give minimum number of coins (e.g. 30 is 10x3 rather than 6x5), which can be modified with another pass.
dp way
private boolean dp(int s){
if (s < 0) return false;
if (s == 0) return true;
if (dp[s] != -1) return dp[s] == 1;
if (dp(s - 3)) return dp[s] = 1;
if (dp(s - 5)) return dp[s] = 1;
return dp[s] = 0;
}
recursion with memoization is the same as dp.
The idea behind dp is to solve subproblems and do not repeat your calculations. The same idea here, compose solution from smaller problems and cache results
Simple recursion code.
int foo(int sum)
{
if (sum == 0)
return 1;
if (sum < 0)
return 0;
printf("%d\n", sum);
if (foo(sum-5))
return 1;
if (foo(sum-3))
return 1;
return 0;
}
generic solution for any number with infinite supply:
int foo(int *a, int sum,int size)
{
int i;
if (sum == 0)
return 1;
if (sum < 0)
return 0;
for (i=0;i<size;i++)
if (foo(a, sum-a[i], size))
return 1;
return 0;
}
int main()
{
int i;
int a[] = {7, 8};
printf("%d\n", foo(a, 18, SIZE(a)));
printf("%d\n", foo(a, 19, SIZE(a)));
printf("%d\n", foo(a, 20, SIZE(a)));
printf("%d\n", foo(a, 21, SIZE(a)));
printf("%d\n", foo(a, 22, SIZE(a)));
return 0;
}
if(N is divisible by 5) || (N/5's remainder is divisible by 3)
return true;
else if(N is divisible by 3) || (N/3's remainder is divisible by 5)
return true;
else
return false;
C code:
bool is_N_formable(int N)
{
int x, y;
x = N%5;
if((x == 0) || (x%3 == 0))
return true;
y = N%3;
if((y == 0) || (y%5 == 0))
return true;
return false;
}
For any value that can be represented using more than 4 3R coins, you can alternatively represent it with every 5 3R coins being replaced with 3 5R coins. Therefore any value that can be represented with any number of both 3R and 5R coins can be represented using only 4 or less 3R coins. If we consider this the canonocal representation of the value, the portion of the value in this canonical representation that can be represented by 3R coins can only be 0, 3, 6, 9, or 12. Also the remaining portion of the value must be a multiple of 5 as it will be made up entirely of 5R coins. So for any value which can be represented using 3R and 5R coins the value minus 0, 3, 6, 9, or 12 must be a multiple of 5.
boolean check(int val) {
if (val < 0)
return false;
for (int i = 0, i < 15, i+=3)
if (i <= val && ((val - i)%5)==0)
return true;
return false;
}
Or for the simplest solution.
boolean check(int val) {
if (val < 0 || val == 1 || val == 2 || val == 4 || val == 7)
return false;
return true;
}
this can be solved by constructing a min heap tree with left child as root+3 and right child as root+5 till a leaf node becomes greater than the required sum . then search if any of the leaf nodes are equal as the required sum . if not , return false . I think complexity is logn + time to construct the tree
public class ExactChange
{
public static void exactChange(int totalAmount,int coin1,int coin2)
{
int countOfCoin1=0,countOfCoin2=0;
while(totalAmount >= 0 )
{
countOfCoin1=totalAmount/coin1;
totalAmount=totalAmount%coin1;
if(totalAmount<coin1)
{
break;
}
}
while(totalAmount >=0 )
{
countOfCoin2=totalAmount/coin2;
totalAmount=totalAmount-coin2;
if(totalAmount==0)
{
break;
}
else
{
totalAmount =totalAmount + coin1;
countOfCoin1--;
}
}
System.out.println("5*"+countOfCoin1+"+ 3*"+countOfCoin2);
}
public static void main(String [] args)
{
int M=5,N=3;
exactChange(16,M,N);
}
}
public class ExactChange
{
public static void exactChange(int totalAmount,int coin1,int coin2)
{
int countOfCoin1=0,countOfCoin2=0;
while(totalAmount >= 0 )
{
countOfCoin1=totalAmount/coin1;
totalAmount=totalAmount%coin1;
if(totalAmount<coin1)
{
break;
}
}
while(totalAmount >=0 )
{
countOfCoin2=totalAmount/coin2;
totalAmount=totalAmount-coin2;
if(totalAmount==0)
{
break;
}
else if( countOfCoin1!=0)
{
totalAmount =totalAmount + coin1;
countOfCoin1--;
}
else
{
System.out.println("Change cannot made");
}
}
System.out.println("5*"+countOfCoin1+"+ 3*"+countOfCoin2);
}
public static void main(String [] args)
{
int M=5,N=3;
exactChange(16,M,N);
}
}
public class ExactChange
{
public static void exactChange(int totalAmount,int coin1,int coin2)
{
int countOfCoin1=0,countOfCoin2=0;
int amount=totalAmount;
while(totalAmount >= 0 )
{
countOfCoin1=totalAmount/coin1;
totalAmount=totalAmount%coin1;
if(totalAmount<coin1)
{
break;
}
}
while(totalAmount >=0 )
{
totalAmount=totalAmount-coin2;
countOfCoin2++;
if(totalAmount==0)
{
break;
}
else if( countOfCoin1!=0 )
{
totalAmount =totalAmount + coin1;
countOfCoin1--;
}
else
{
System.out.println("Change cannot made");
break;
}
}
if(amount==((coin1*countOfCoin1)+(coin2*countOfCoin2)))
System.out.println(coin1+"*"+countOfCoin1+"+"+coin2+"*"+countOfCoin2);
}
public static void main(String [] args)
{
int M=5,N=10;
exactChange(25,M>N?M:N,M<N?M:N);
}
}
package com.utsav.jpm;
import java.util.Scanner;
public class CoinDivision {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int money = in.nextInt();
int remFive = money % 5;
if((remFive == 0) || (money % 3 == 0) ){
System.out.println("True");
} else if(remFive % 3 == 0){
System.out.println("True");
} else {
System.out.println("False");
}
}
}
package currencychange;
public class CurrencyChange {
public static void main(String[] args) {
CurrencyChange c = new CurrencyChange();
boolean isPossible = c.isChangePossible(8);
System.out.println(isPossible);
}
public boolean isChangePossible(int amount){
boolean changePossible = false;
if(amount %3 ==0 || amount % 5==0){
return true;
}else{
while(amount >= 1) {
amount = amount -5;
if(amount %3 ==0 || amount % 5 ==0){
changePossible = true;
break;
}
}
}
return changePossible;
}
}
package currencychange;
public class CurrencyChange {
public static void main(String[] args) {
CurrencyChange c = new CurrencyChange();
boolean isPossible = c.isChangePossible(16);
System.out.println(isPossible);
}
public boolean isChangePossible(int amount){
boolean changePossible = false;
if(amount %3 ==0 || amount % 5==0){
return true;
}else{
while(amount >= 1) {
amount = amount -5;
if(amount %3 ==0 || amount % 5 ==0){
changePossible = true;
break;
}
}
}
return changePossible;
}
}
Java code -
public class ChangeVendor {
public static boolean denomination1(int numb, int den1, int den2) {
int bigDenomination = (den1 > den2) ? den1 : den2;
int bigDenominationCount = 0;
int smallDenomination = (den1 < den2) ? den1 : den2;
int smallDenominationCount = 0;
if (den1 > den2) {
bigDenomination = den1;
smallDenomination = den2;
} else {
bigDenomination = den2;
smallDenomination = den1;
}
// Using Greedy algorithm to get as much max value using bigger
// denomination
while ((bigDenominationCount * bigDenomination) < numb) {
bigDenominationCount++;
}
while (bigDenominationCount > 0 && smallDenominationCount >=0) {
smallDenominationCount++;
if ((bigDenominationCount * bigDenomination) + (smallDenomination * smallDenominationCount) > numb) {
bigDenominationCount--;
}
// if Sum of both the denomination is equal to amount and count of both denomination >0
if ((bigDenominationCount * bigDenomination) + (smallDenomination * smallDenominationCount) == numb && bigDenominationCount > 0 && smallDenominationCount>0) {
System.out.print(" Rs. " + bigDenomination + " = " + bigDenominationCount);
System.out.print(" Rs. " + smallDenomination + " = " + smallDenominationCount);
return true;
}
}
return false;
}
public static void main(String[] args) {
for (int i = 1; i < 100; i++) {
System.out.println(" Num = " + i + " " + denomination1(i, 3, 5));
}
}
}
public class ChangeVendor {
public static boolean denomination1(int numb, int den1, int den2) {
int bigDenomination = (den1 > den2) ? den1 : den2;
int bigDenominationCount = 0;
int smallDenomination = (den1 < den2) ? den1 : den2;
int smallDenominationCount = 0;
if (den1 > den2) {
bigDenomination = den1;
smallDenomination = den2;
} else {
bigDenomination = den2;
smallDenomination = den1;
}
// Using Greedy algorithm to get as much max value using bigger
// denomination
while ((bigDenominationCount * bigDenomination) < numb) {
bigDenominationCount++;
}
while (bigDenominationCount > 0 && smallDenominationCount >=0) {
smallDenominationCount++;
if ((bigDenominationCount * bigDenomination) + (smallDenomination * smallDenominationCount) > numb) {
bigDenominationCount--;
}
// if Sum of both the denomination is equal to amount and count of both denomination >0
if ((bigDenominationCount * bigDenomination) + (smallDenomination * smallDenominationCount) == numb && bigDenominationCount > 0 && smallDenominationCount>0) {
System.out.print(" Rs. " + bigDenomination + " = " + bigDenominationCount);
System.out.print(" Rs. " + smallDenomination + " = " + smallDenominationCount);
return true;
}
}
return false;
}
public static void main(String[] args) {
for (int i = 1; i < 100; i++) {
System.out.println(" Num = " + i + " " + denomination1(i, 3, 5));
}
}
}
public class ChangeVendor {
public static boolean denomination1(int numb, int den1, int den2) {
int bigDenomination = (den1 > den2) ? den1 : den2;
int bigDenominationCount = 0;
int smallDenomination = (den1 < den2) ? den1 : den2;
int smallDenominationCount = 0;
if (den1 > den2) {
bigDenomination = den1;
smallDenomination = den2;
} else {
bigDenomination = den2;
smallDenomination = den1;
}
// Using Greedy algorithm to get as much max value using bigger
// denomination
while ((bigDenominationCount * bigDenomination) < numb) {
bigDenominationCount++;
}
while (bigDenominationCount > 0 && smallDenominationCount >=0) {
smallDenominationCount++;
if ((bigDenominationCount * bigDenomination) + (smallDenomination * smallDenominationCount) > numb) {
bigDenominationCount--;
}
// if Sum of both the denomination is equal to amount and count of both denomination >0
if ((bigDenominationCount * bigDenomination) + (smallDenomination * smallDenominationCount) == numb && bigDenominationCount > 0 && smallDenominationCount>0) {
System.out.print(" Rs. " + bigDenomination + " = " + bigDenominationCount);
System.out.print(" Rs. " + smallDenomination + " = " + smallDenominationCount);
return true;
}
}
return false;
}
public static void main(String[] args) {
for (int i = 1; i < 100; i++) {
System.out.println(" Num = " + i + " " + denomination1(i, 3, 5));
}
}
}
Tested with Data: 29, 31,7,13 etc.
public static void main(String[] args) {
int num =7;
int f = 3;
int s = 5;
Coin coin = misc.coinCount(num, f, s);
if(coin==null){
coin = misc.coinCount(num, s, f);
}
if(coin!=null){
System.out.println(" Coint "+coin.countX+" Second "+coin.countY);
}else{
System.out.println(" Not Possible");
}
}
public Coin coinCount(int num, int f,int s){
Coin coin = new Coin(0, 0);
while(num!=0 && num>0){
if(num%f==0){
coin.countX+=num/f;
return coin;
}else if(num%s==0){
coin.countY+=num/s;
return coin;
}else if(num == 0){
return coin;
}else {
coin.countX+=1;
num = num-f;
}
}
if(num<0){
return null;
}
return coin;
}
}
class Coin{
public int countX;
public int countY;
public Coin(int countX, int countY) {
super();
this.countX = countX;
this.countY = countY;
}
}
Complexity O(1): since the GCD of the numbers is 1, any sufficiently large number can be formed with them. In fact, by examining the possible numbers it's easy to see that 8,9 and 10 can be formed with those coins. Since one of the coins is 3, any number after those can be formed too (8 + n*3, 9 + n*3 or 10 + n*3). So just return true for any number above 8 and memorize the result for the numbers below.
- Anonymous January 11, 2015