## Ebay Interview Question

SDE-2s**Team:**Traffic

**Country:**United States

**Interview Type:**In-Person

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

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

```
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;
list.add(25);
}
while((sub -10) > 0) {
sub = sub -10;
list.add(10);
}
while((sub-5) > 0) {
sub = sub -5;
list.add(5);
}
while((sub-1) >= 0) {
sub = sub -1;
list.add(1);
}
return list;
}
}
```

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

}

}

dp

}

- Scott January 23, 2014