## Google Interview Question for Software Engineer / Developers

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

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(55);

}
}

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

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)

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

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.

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

Goal is to minimize the number of coins. What part of it din't u understand?

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

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

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

dynamic programming for smallest number of coins problem.

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

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).

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

coins/bills={ \$1,\$5,\$7,\$10 }

Gimme \$14.

greedy : \$10 + 4 x \$1
Dyna : \$7+\$7

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

onestopinterviewprep.blogspot.com/2014/03/vending-machine-problem-dynamic.html

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.