## Ebay Interview Question for SDE-2s

Team: Traffic
Country: United States
Interview Type: In-Person

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

Why everybody makes the simple question so complicated?

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

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

instead of: printf("%d quarters, %d nickels, %d dimes, %d pence\n",
a, b, c, rc);
should be: printf("%d quarters, %d dimes, %d nickels, %d pence\n",
a, b, c, rc);

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

25a+10b+5c+d=78
find combinations for a=0...3

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

Here using DP
set DP[0] = 1;
int f[4]{25,10,5,1};
for(int i=0;i<4;i++)
{
for(int j=0;j<=78;j++)
if(j+f[i] <= 78)
DP[j+f[i]]+=DP[j];
}
print DP[78];

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

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

}``````

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

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

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

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

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

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

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

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

@stchief: I changed the code to take care of cases where n-v[i]=v[i]. Can u pls check now?

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

count(10) != count(5) +1. The method f(n) = f(coin) + f(n -coin) does not stand

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

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

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

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

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

just call
final int[] coins = new int[] { 1, 5, 10, 25 };
getCoinCombinations(0, coins, 78));

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

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,

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

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

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

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

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

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

}

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

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

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

This code does not work at all, try to input amount 5 you will your answer is wrong.

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

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){
}
if(sum >= 10){
}
if(sum >= 5){
}
if(sum >= 1){
}
}

@SuppressWarnings("unchecked")
private void add(ArrayList<Coin> coins, int sum, Coin coin) {
coins = (ArrayList<Coin>) coins.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 + "";
}
}
}
}``````

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.