Ebay Interview Question
SDE-2sTeam: 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