Google Interview Question Software Engineer / Developers
5of 5 votesWrite the code for a change vending machine.
The goal of this problem is to give back the smallest number of coins. This solution only works for US currency, or currencies with nice increments. For instance, if the nickel (5 cents) did not exist and you wanted to give back 30 cents, it would return 25 + 1 + 1 + 1 + 1 + 1, instead of 10 + 10 + 10, which is preferred.
You need a recursive solution that will enumerate all possibilities and select the shortest past (i.e. least number of coins)
First of all I have written the program for dollars and the same can be applied or extended to cents or any other currency.
The answer to the next part of the question where 30 is divided as 25+1+1+1+1+1 is not true. If u go thru the logic properly u will see that u get 30 = 10+10+5+5 which is what a coin vending machine actually gives.
package google;
public class ChangeVendingMachine {
private boolean isPossible(int amt){
if(amt == 5 || amt == 10 || amt == 20 || amt == 50 || amt ==100){
return true;
}
return false;
}
private int getHighestPossible(int amt){
assert(!(amt == 0));
if(amt > 100){
return 100;
}
else if(amt > 50){
return 50;
}
else if(amt > 20){
return 20;
}
else if(amt > 10){
return 10;
}
else if(amt >= 5){
return 5;
}
else{
System.out.println("Cant return any more notes!");
return 0;
}
}
public void getChange(int amt){
if(amt == 0){
System.out.println("Amount is Zero!");
return;
}
while(amt > 0){
if(amt == 5){
System.out.println(amt);
amt = amt - 5;
return;
}
int mid = amt/2;
if(isPossible(mid) == true){
System.out.println(mid);
amt = amt - mid;
}
else {
int highPossible = getHighestPossible(mid);
System.out.println(highPossible);
amt = amt - highPossible;
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ChangeVendingMachine obj = new ChangeVendingMachine();
obj.getChange(30);
}
}
*****************output******************
10
10
5
5
Its not DP, its the greedy approach u have to take here!!
lets say change = money u have to return (lets say it is just cents for now i.e. the amt < 100 cents)
Let the coins available are of 5 cents, 1 cent and 10 cents.
1. #10s = change / 10;
change = change % 10 //IMP STEP
2. #5s = change/5;
change = change%5;
3. #1s = change.
Thats it. If the amount is dollars and cents, convert everything into cents. (the amt to be returned and the bills that are available ($1, $5 etc).
package google;
- Java Coder October 12, 2008public class ChangeVendingMachine {
private boolean isPossible(int amt){
if(amt == 5 || amt == 10 || amt == 20 || amt == 50 || amt ==100){
return true;
}
return false;
}
private int getHighestPossible(int amt){
assert(!(amt == 0));
if(amt > 100){
return 100;
}
else if(amt > 50){
return 50;
}
else if(amt > 20){
return 20;
}
else if(amt > 10){
return 10;
}
else if(amt >= 5){
return 5;
}
else{
System.out.println("Cant return any more notes!");
return 0;
}
}
public void getChange(int amt){
if(amt == 0){
System.out.println("Amount is Zero!");
return;
}
while(amt > 0){
if(amt == 5){
System.out.println(amt);
amt = amt - 5;
return;
}
int mid = amt/2;
if(isPossible(mid) == true){
System.out.println(mid);
amt = amt - mid;
}
else {
int highPossible = getHighestPossible(mid);
System.out.println(highPossible);
amt = amt - highPossible;
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ChangeVendingMachine obj = new ChangeVendingMachine();
obj.getChange(55);
}
}