## Interview Question

• 0

Country: United States

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

``````#include <iostream>
#include <vector>

#include <cassert>

using namespace std;

int main(int argc, char** argv) {

cout << "Enter a total amount to make, in cents" << endl; // to ensure whole numbers
int total; // ought to not use floating point for currency, but for practical purposes lets just use it.
cin >> total;
// Assume number is OK (i.e. there are no more than 2 decimal places, it is not negative, etc)

if(total < 0) {
cerr << "cannot have a negative total!" << endl;
return 1;
}

cout << "total: " << total << endl;
vector<int> coin_values = {25, 10, 5, 1};  // to find the minimal number of coins,
// this list must be in descending order
vector<int> coins_needed;
for(auto v : coin_values) {
unsigned int need = total / v;
total -= need * v;
coins_needed.push_back(need);
}

assert(coin_values.size() == coins_needed.size());
for(auto i = 0; i < coin_values.size(); ++i) {
cout << "Number of " << coin_values[i] << " cent coins needed: " << coins_needed[i] << endl;
}
return 0;
}``````

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

your code fails for the second set of coin values (12 = 2 x 6 and not 1 x 10 + 3 x 1 as your code finds).

a brute force approach would be:

for a number n, try coin with value v_i exactly floor(n/v_i) times. running time is thus

n/v1 * n/v2 * n/v3 * ... * n/v_k

so O(n^k).

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

``````import java.util.HashMap;
import java.util.Map;

public class Q3 {

static int a[] = { 25, 10, 6, 1 };
//the coin value to number of occurrence. example for 112 you get {6=2, 25=4}
static Map<Integer, Integer> smallestCandidate = new HashMap<Integer, Integer>();

public static void main(String[] args) {
permuteCoins(112, new HashMap<Integer, Integer>(), 0);
System.out.println(smallestCandidate);
smallestCandidate.clear();

permuteCoins(36, new HashMap<Integer, Integer>(), 0);
System.out.println(smallestCandidate);
smallestCandidate.clear();

permuteCoins(47, new HashMap<Integer, Integer>(), 0);
System.out.println(smallestCandidate);
smallestCandidate.clear();
}

/**
* find all possible combinations of coins that adds to the a given number
*
*/
private static void permuteCoins(int number,
Map<Integer, Integer> currentResult, int index) {
if (number <= 0) {
// Compare the current combination of coins of the smallest
// candidate
if (smallestCandidate.isEmpty()
|| getSize(smallestCandidate) > getSize(currentResult)) {
smallestCandidate.clear();
smallestCandidate.putAll(currentResult);
}
return;
}
for (int i = index; i < a.length; i++) {
if (a[i] <= number) {
int numOfCoin = number / a[i];
Map<Integer, Integer> thisResult = new HashMap<Integer, Integer>(
currentResult);
thisResult.put(a[i], numOfCoin);
permuteCoins(number % a[i], thisResult, i + 1);
}
}
}

private static int getSize(Map<Integer, Integer> r) {
int size = 0;
if (!r.isEmpty()) {
for (Integer v : r.values()) {
size += v;
}
}
return size;
}
}``````

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

The above seems so complicated for this question? Maybe I misunderstood the question but heres mine:

public class CoinCounter{

public static void main(String []args){
System.out.println("Hello World");

countCoin(126);
}

private static void countCoin(int n) {
int quarters, dimes, nickels, pennies;

quarters = n / 25;
n = n - (quarters * 25);
dimes = n / 10;
n = n - (dimes * 10);
nickels = n / 5;
n = n - (nickels * 5);
pennies = n;

print("quarters:" + quarters +
", dimes:" + dimes +
", nickels:" + nickels +
", pennies:" + pennies);
}

private static void print(String s) {
System.out.println(s);
}

private static void print(char c) {
System.out.print(String.valueOf(c));
}
}

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

This is how I solved it as well. Far less memory and resource usage as compared to the other solutions.

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

you misunderstood the question. the above solution works for 25, 10, 5, 1 but not for 25, 10, 6, 1 since for 12 cents your solution would be 1x10 cent and 2x1 cent whereas the optimal solution is 2x6 cents.

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

``````int[] coins = {25,10,6,1};

int mainFunction(int change)
{
return MinCoin(change, 0);
}

int MinCoin(int change, int count)
{
if(change<=0) return count;
int min = INT_MAX;
for(int i=0;i<coins.length;++i)
{
if(change>=coins[i])
{
int c = MinCoin(change-coins[i], count+1);
min = Min(c, min);
}
}

return min;
}``````

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

can be optimized using DP.

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

A pretty simple dp algorithm:

``````sub dp_count_coins {
my (\$sum, @denoms) = @_;

# initialize dp table to length of \$sum + 1, set all elements to 999 (i.e. not a low number)
my @dp_table = (999) x (\$sum + 1);

# starting solution, there are 0 ways to count a 0 cents
\$dp_table[0] = 0;

foreach my \$i ( 1 .. \$sum ) {
foreach my \$j ( 0 .. \$#denoms ) {
if ( \$i >= \$denoms[\$j] && 1 + \$dp_table[\$i - \$denoms[\$j]] < \$dp_table[\$i] ) {
\$dp_table[\$i] = 1 + \$dp_table[\$i - \$denoms[\$j]]
}
}
}

return \$dp_table[\$sum];
}``````

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.