## Ebay Interview Question for SDE-2s

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

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

dp

``````public int optimalPay(int [] coins , int money){
int [] dp = new int [money+1];
dp [0] = 0;
dp [1] = 1;
for (int i = 2; i<=money;++i){
dp[i] = i;
for (int j= 0; j<coins.length;++j){
if (i>=coins[j]){
dp[i]= dp[i-coins[j]]+1<dp[i]? dp[i-coins[j]]+1:dp[i];
}
}
}

return dp[money];``````

}

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

``````int purchaseAmt;
cin>>purchaseAmt;
int balAmt = 100 - purchaseAmt;
int coinArr[4] = {25,10,5,1};
int coinCntArr[4]={0,0,0,0};
int k=0;
while(balAmt)
{
while(balAmt>=coinArr[k])
{
balAmt = balAmt -coinArr[k];
coinCntArr[k]=coinCntArr[k]+1;

}
k++;

}

for(int t=0;t<4;t++)
cout << "\n coins used are "<< coinCntArr[t] << " : "<< coinArr[t]<< "cents ";``````

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

We have to use dynamic programming approach

int[] coinsArray = new int[5] { 1, 2, 5, 10, 20 };

``````private int GetMinNo(int iAmount)
{
array = new int[coinsArray.GetLength(0) + 1, iAmount + 1];

for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
array[i, j] = 0;

if(i == 1)
{
array[i, j] = j;
}
}
}

for (int iCoin = 2; iCoin < array.GetLength(0); iCoin++)
{
for (int amount = 0; amount < iAmount + 1; amount++)
{
array[iCoin, amount] = Math.Min(array[iCoin-1, amount], amount / coinsArray[iCoin - 1] + array[iCoin-1, amount % coinsArray[iCoin - 1]]);
}
}

return array[array.GetLength(0)-1, array.GetLength(1)-1];

}``````

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

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

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

``````package com.knowledgebase.company.ebay;

import java.util.ArrayList;
import java.util.List;

/**
* Given 78 cents (target) you need to tell how many ways it is possible to make
* the change using 25 cents(quarter), 10 cents(nickel), 5cents(dime),
* 1cents(penny)
*
*/
public class FindChange {
public static void main(String argv[]) {
System.out.println(findChange(91).toString());
System.out.println(findChange(78).toString());
System.out.println(findChange(36).toString());
System.out.println(findChange(49).toString());
}

private static List<Integer> findChange(int num) {
List<Integer> list = new ArrayList<Integer>();
int sub = num;
while((sub - 25) > 0) {
sub = sub - 25;
}
while((sub -10) > 0) {
sub = sub -10;
}
while((sub-5) > 0) {
sub = sub -5;
}
while((sub-1) >= 0) {
sub = sub -1;
}
return list;
}
}``````

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

public class GetOptimalChange {
int[] coinsAvailable = { 200, 50, 25, 10, 5, 1 };
boolean foundChange = false;

public void getOptimalChange(int cents, int start, int len, int[] outArray) {
if (cents == 0) {
for (int i = 0; i < len; i++) {
System.out.print(outArray[i] + " ");
;
}
foundChange = true;
return;
}
if (foundChange)
return;
while (coinsAvailable[start] > cents
&& (start + 1) < coinsAvailable.length)
start++;
for (int i = start; coinsAvailable[i] <=cents; i++) {
outArray[len] = coinsAvailable[i];
if (i < coinsAvailable.length) {
getOptimalChange(cents - coinsAvailable[i], i, len + 1,
outArray);
}
if (i == coinsAvailable.length - 1) {
break;
}
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
GetOptimalChange gOC = new GetOptimalChange();
int[] outArray = new int[200];
gOC.getOptimalChange(250, 0, 0, outArray);
}

}

Comment hidden because of low score. Click to expand.

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.