## Goldman Sachs Interview Question for Developer Program Engineers

• -1
of 1 vote

Country: India
Interview Type: Written Test

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

How is 16 false? it can be made by 2*5+2*3

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

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.

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

Very nice!

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

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

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

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.

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

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

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

@ Darkhan.Imangaliev : this is recursion not dp

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

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

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

@Darkhan.Imangaliev: now when you said i looked into your code and found that i missed your reusing-the-already-calculated result. So yes my mistake and you are right that this indeed is dp.

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

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

Comment hidden because of low score. Click to expand.
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;
}``````

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

your solution works very slow, try to cache already calculated results, in this case you get O(n) solution

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

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

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

you can get 16 but not by your code. And how can the reminder of N/3 greater than 2 and be divisible by 5???

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

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

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

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

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

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

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

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("5*"+countOfCoin1+"+ 3*"+countOfCoin2);
}
public static void main(String [] args)
{
int M=5,N=3;
exactChange(16,M,N);
}
}

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

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
{

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

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

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

}

}``````

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

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

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

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

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

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

}

}``````

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

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

}

}``````

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

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

}

}``````

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

int n = 19;
if(n%5==0 || n%3==0)
{
System.out.println("----good");
}

for (int i=1;i<n/5;i++)
{
System.out.println("i= " + i );
int b= 5*i;
int a = n%b;
System.out.println("a=" + a);
if ( a > 3){

if (a%3==0)
{
System.out.println("good");
break;

}
}
}

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

``````public class MakingDenominationOfARandomNum {

public static void main(String[] args) {
int n = 3;
if(n%5==0 || n%3==0){
System.out.println("true");
return;
}
int k = n%5;
if(k%3==0){
System.out.println("true");
}else{
System.out.println("false");
}
}
}``````

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

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

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

``````public boolean isSumOfCoins(int s) {
int c3, c5;

c3 = ((n%5)<<1)%5;
c5 = n/5 - ((n%5)%3);

if(c3 < 0 || c5 < 0) return false;
else return true;
}``````

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

``````public boolean isSumOfCoins(int n) {
int c3, c5;

c3 = ((n%5)<<1)%5;
c5 = n/5 - ((n%5)%3);

if(c3 < 0 || c5 < 0) return false;
else return true;
}``````

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.