Ebay Interview Question SDE-2s
Team: Traffic
Country: United States
Interview Type: In-Person
public int findNumber2(int amount, int[] coins)
{
int a, b, c, d, count = 0;
a = amount / coins[0];
b = amount / coins[1];
c = amount / coins[2];
d = amount / coins[3];
for (int i = 0; i <= a; i++)
{
for (int j = 0; j <= b; j++)
{
for (int k = 0; k <= c; k++)
{
for (int l = 0; l <= d; l++)
{
if ((coins[0] * i + coins[1] * j + coins[2] * k + coins[3] * l) == amount)
count++;
}
}
}
}
return count;
}
/* here is my c++ solution */
#include <iostream>
using namespace std;
int coins[]={25,10,5,1};
int change[4]={0}; //number of quarters, dime, nickels, and pennies
void print_change(int amount, int d);
int main()
{
int amount = 78;
print_change(amount,0);
}
void print_change(int amount, int d)
{
int i;
if(d == 3){
change[d] = amount;
for(int j=0; j<4; j++){
cout << "[" << coins[j] << "]" << ":" << change[j] << "\t";
}
cout << endl;
return;
}
// "amount/coins[d]" is the number of current coin number. (0: quarter, 1:dime, 2:nickel, 3:penny)
//recursively try with possible number of coins
for(i = 0; i <= amount/coins[d]; i++){
change[d]+= i;
print_change(amount-coins[d]*i, d+1);
change[d] -= i;
}
}
public int makeChange(int n,int denom)
{
int next=0;
if (denom = 25) next = 10;
else if (denom = 10) next = 5;
else if (denom = 5) next = 1;
else (denom = 1) return 1;
int ways = 0;
for (int i=0;i*denom<=n;i++)
{
ways += makeChange(n-i*denom,next);
}
return ways;
}
system.out.println(makeChange(78,25));
have used recursion here..can be improved by using dp.
#include<iostream>
#include<conio.h>
using namespace std;
int count(int n){
if(n<0) return 0;
if(n==0) return 1;
if(n==1) return 1;
if(n>25){
if(n==50) return count(25)+1;
return count(n-25)+count(25);
}
if(n>10){
if(n==25) return 1+count(n-10)+count(10);
if(n==20) return 1+count(10);
return count(n-10)+count(10);
}
if(n>5){
if(n==10) return 1+count(5);
return count(n-5)+count(5);
}
if(n>1){
if(n==5) return 1+count(n-1);
return count(n-1);
}
}
int main(){
int n;
cout<<"enter the value"<<endl;
cin>>n;
int c=count(n);
cout<<c;
getch();
return 0;
}
take a look at count(10) in your code
count(10) = 1 + count(5) + count(5)
count(5) = 1 + count(4) = 2
so count(10) = 5;
but actually 10 has 4 combinations:
10
5, 5
5, 1,1,1,1,1
1,1,1,1,1,1,1,1,1,1
@stchief: I changed the code to take care of cases where n-v[i]=v[i]. Can u pls check now?
Solution in Python :
# Find the differnce between money and coins use the ones which give min
# Chanage
coins = [25,10,5,1]
coins.sort()
money = 78
def count(money , coins ):
if money == 0 or len(coins) == 0:
return 0
change = []
number = len(coins)
i = 0
while i < number:
minCoin = coinWithMinDifference(money,coins)
i = i + 1
if minCoin is not 0:
change.append(minCoin)
money = money - minCoin
i = 0
print change
def coinWithMinDifference(money,coins):
final = 0
diff = money
for coin in coins:
minus = money - coin
if minus > -1:
if minus < diff:
final = coin
return final
count(money,coins)
static int getCoinCombinations(final int start, final int[] coins,
int amount) {
int result = 0;
if (amount == 0) {
return 1;
}
for (int i = start; i < coins.length; i++) {
if (amount >= coins[i]) {
result += getCoinCombinations(i, coins, amount - coins[i]);
}
}
return result;
}
f(n) = 0 when n < 0
f(0) = 1 to ease the computation
f(n) = f(n-1) + f(n-5) + f(n-10) + f(n-25) - f(n - 1 -5) - f(n -1 - 10) + f(n -1 -5-10) - f(n-1-25) - f(n-5-25) - f(n-25-10) + f(n-25-5-1) + f(n-25-5-10) + f(n -25-1-5-10)
f(n-c) : the number of combinations including at least one coin c
f(n-c1-c2): the intersection of f(n-c1) and f(n-c2), the number of combinations including at least one coin c1 and one coin c2,
a solution for more general situation.
int count(int left, vector<int> coins, int curidx)
{
if(left == 0) return 1;
if(curidx >= coins.size()) return 0;
int res = 0;
for(int i = 0;;++i)
{
if(i*coins[curidx] <= left)
res+= count(left-i*coins[curidx],coins,curidx+1);
}
return res;
}
cout << count(28,<25,10,5,1>,0);
int GetTotalWaysCount(int sum, int denom[], int index, int output[], int m)
{
//base
if(index >= SIZE)
return 0;
if(sum < 0)
return 0;
if(sum == 0)
{
for(int i = 0; i< m; i++)
cout << output[i] << ",";
cout <<endl;
return 1;
}
int ways = 0;
output[m] = denom[index];
ways = GetTotalWaysCount(sum - denom[index],denom, index,output, m+1) + GetTotalWaysCount(sum, denom, index + 1,output,m);
return ways;
}
public class CountNumberWays {
public void printNumberOfWays(int totalPennies) {
int[] coinsArray = { 1, 5, 10, 25 };
int[] numberOFWays = new int[totalPennies + 1];
numberOFWays[0] = 1;
for (int i = 0; i < coinsArray.length; i++) {
for (int j = coinsArray[i]; j <= totalPennies; j++) {
numberOFWays[j] += numberOFWays[j - coinsArray[i]];
}
}
System.out
.println("Number of different ways $2 be made using any number of coins is "
+ numberOFWays[totalPennies]);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int totalPennies = 78;
CountNumberWays cNW = new CountNumberWays();
cNW.printNumberOfWays(totalPennies);
}
}
Its a copy of getting change of coins....can be solved using dynamic programming
public static int findNumber(int amount, int[] coins)
{
int[] result; // to store the result for all amounts
int[] mySol; // temporary store the results for an specific amount with all coins
result = new int[amount+1];
mySol = new int[coins.length];
result[0] = 0;
for(int j=1; j<=amount; j++) //This for loop will calculate for all amount till given amount
{
for(int k=0; k<coins.length; k++)
mySol[k] = -1; // store all coin values as -1
for(int k=0; k<coins.length; k++)
{
if(coins[k] <= j)
{
mySol[k] = result[j-coins[k]] + 1; // Store result with one specific one coin and value of pevious amount
}
}
result[j] = -1;
for(int k=0; k<coins.length; k++)
{
if(mySol[k] > 0)
{
if(result[j] == -1 || mySol[k] < result[j])
result[j] = mySol[k];
}
}
}
return result[amount];
}
It's not the best thing, but it gave me the answer 2200
public class ChangeOf78 {
public static void main(String[] args) {
new Go();
}
private static class Go{
private final Coin coin25 = new Coin(25, 2);
private final Coin coin10 = new Coin(10, 3);
private final Coin coin5 = new Coin(5, 5);
private final Coin coin1 = new Coin(1, 7);
private HashMap<Integer, ArrayList<Coin>> coinsMap = new HashMap<>();
public Go(){
calculateChange(new ArrayList<Coin>(), 25);
System.out.println(Math.pow(coinsMap.size(), 3) + 3);
}
private void calculateChange(ArrayList<Coin> coins, int sum){
if(sum == 0){
int key = 1;
for (Coin coin : coins) {
key *= coin.id;
}
coinsMap.put(key, coins);
return;
}
if(sum >= 25){
add(coins, sum, coin25);
}
if(sum >= 10){
add(coins, sum, coin10);
}
if(sum >= 5){
add(coins, sum, coin5);
}
if(sum >= 1){
add(coins, sum, coin1);
}
}
@SuppressWarnings("unchecked")
private void add(ArrayList<Coin> coins, int sum, Coin coin) {
coins = (ArrayList<Coin>) coins.clone();
coins.add(coin.clone());
calculateChange(coins, sum - coin.value);
}
private class Coin{
int id;
int value;
public Coin(int value, int id) {
this.id = id;
this.value = value;
}
@Override
public Coin clone() {
return new Coin(value, id);
}
@Override
public String toString() {
return value + "";
}
}
}
}
Why everybody makes the simple question so complicated?
- uuuouou December 14, 2013int howManyWays(int total) { int a, ra, b, rb, ways = 0; for(a = total/25; a >= 0; --a){ ra = total - 25 * a; for(b = ra/10; b >= 0; --b){ rb = ra - 10 * b; ways += rb/5 + 1; } } return ways; } void printAllWays(int total) { int a, ra, b, rb, c, rc; for(a = total/25; a >= 0; --a){ ra= total - 25 * a; for(b = ra/10; b >= 0; --b){ rb = ra - 10 * b; for(c = rb/5; c >= 0; --c){ rc = rb - 5 * c; printf("%d quarters, %d nickels, %d dimes, %d pence\n", a, b, c, rc); } } } }