Goldman Sachs Interview Question for Developer Program Engineers


Country: India
Interview Type: Written Test




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

- Anonymous January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice!

- Victor January 12, 2015 | Flag
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

- Rahul January 10, 2015 | Flag Reply
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;
}

- autoboli January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ali January 10, 2015 | Flag
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;
}

- Darkhan.Imangaliev January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@ Darkhan.Imangaliev : this is recursion not dp

- aka January 13, 2015 | Flag
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

- Darkhan.Imangaliev January 16, 2015 | Flag
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.

- aka January 16, 2015 | Flag
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;
}

- aka[1] January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka[1] January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Darkhan.Imangaliev January 16, 2015 | Flag
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;
}

- Gayathri January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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???

- anonymous February 02, 2015 | Flag
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;
}

- wHack23 January 16, 2015 | Flag Reply
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

- Deepak January 20, 2015 | Flag Reply
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);
}
}

- Pradeep kumar R S January 20, 2015 | Flag Reply
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("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);
}
}

- Pradeep kumar R S January 20, 2015 | Flag Reply
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
{

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

- Pradeep kumar R S January 20, 2015 | Flag Reply
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");
		}
			
			
	}

}

- Utsav Parashar March 04, 2015 | Flag Reply
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;
}
}

- Sanky April 19, 2015 | Flag Reply
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;
}
}

- Sanky April 19, 2015 | Flag Reply
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));
		}

	}

}

- Tarun April 26, 2015 | Flag Reply
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));
		}

	}

}

- Tarun April 26, 2015 | Flag Reply
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));
		}

	}

}

- Tarun Jain April 26, 2015 | Flag Reply
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;

}
}
}

- mandy April 26, 2016 | Flag Reply
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");
		}
	}
}

- Anonymous August 07, 2016 | Flag Reply
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;
}
}

- rathor.rajeev August 20, 2016 | Flag Reply
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;
}

- Abhishek Kumar November 06, 2016 | Flag Reply
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;
}

- Abhishek Kumar November 06, 2016 | Flag Reply


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