Had a beginner interview question re: getting change in bills

Career Advice
1

Write a method that takes an integer and returns the smallest number of bills in US currency that could make up that integer value.

The currency denominations will be: 1, 5, 10, 20, 50, and 100.

So for example, If the input integer is 26, then the output would be 3: a 20, a 5, and a 1. 3 bills, so return the number 3.
If the input is 156, then the output would be 4: a 100, a 50, a 5, and a 1. 4 bills, so return the number 4.

Initially I wrote it using a while loop nested in a for loop, then refactored it to ES6 using map. How could I refactor my answer to be better?

let getNumBills = (amount) => {
    if(amount <= 0) return 0;
    let billCount = 0;
    const billDenominations = [100, 50, 20, 10, 5, 1];
    billDenominations.map(e => {
        while(amount >= e) {
            billCount++;
            amount -= e;
            if(amount == 0) return(billCount);
        }
    });
    return(billCount);
}
2

I think the way you did it before with a greedy algorithm clearly laid out reads better.

With the simple for loop and a nested while loop the intent is very clear.

I don’t feel like a map is appropriate in this case, even if it’s technically correct, because they’re more often associated with a pure function applied across the array. I think you reimplimented a kind of reduce with this.

But I’m still an amateur with JS, and ES6 performance might throw everything I said out of the window - I simply don’t know.

1 Like
4

Right, I’m also new to ES6 but I was trying to show that I knew a little bit of it.

Maybe a forEach would have been better as I’m not generating a new array. The result is the same but I think it’s the better answer.

5

I think using the / and % operators would make sense instead of using a while loop. That is to say, instead of

while(amount >= e) {
  billCount++;
  amount -= e;
  if(amount == 0) return(billCount);
}

you could place

billCount += Math.floor(amount / e)
amount %= e

Note that you’re while loop is doing the exact same stuff, but using / and % instead of implementing those yourself might make it run faster since it’ll be implemented natively.

Afterwards, I’d think about using a reduce if you really want to demonstrate your ES6 skills, but in real code I’d think it’d be a bit pointless. This is the sort of thing I’d do for reduce:

return billDenominations.reduce((billCount, currentDenomination) => {
    let oldAmount = amount;
    amount %= currentDenomination
    return billCount + Math.floor(oldAmount / currentDenomination) 
})

The temporary variable is what makes it look not nice.

One other tip I have is to change e to denomination – descriptive variable names are always better, I think.

(I’ve never had a job interview, so I don’t know if any of this is actually what an interviewer would look for)

3 Likes
6

Was this for a Junior Developer position? It’s interesting to me that I have the skills necessary to complete that coding challenge.

I still feel like I’m a few months short of being ready for the Job hunt.

7

Great suggestions, I was trying to implement % but didn’t get quite there so I struck with the while loop.

Was this for a Junior Developer position? It’s interesting to me that I have the skills necessary to complete that coding challenge.

It was the preliminary question to get the interview. The actual interview is Monday and consists of 6 questions.

8

If I was interviewing, I’d ask why you used map, what the purpose of map is/what it does, and if you think that’s the right tool. Re ES6: arrow functions were added as part of ES6, and the way you’ve used them is fine, but I’d query why you switch between the other ES6 additions let and const, and if you can describe in which situations you would ideally use them. It’s interesting and gives quite a lot to talk about, but be careful about just putting things in because they seem “more ES6-ey”.

So the way you’ve used map is kinda contrary to its purpose: you’re using it to just iterate over a list, and during that iteration, update a mutable variable. Map is designed to take a list, and run a mapping function over each item in turn, returning a new list of the same length but with transformed values. forEach is better in your case here, because it’s designed for side effects.

A lot of the ES6 changes have made it easier to write code in a functional style, which I think is maybe what you actually mean, but your solution isn’t really functional per se, and even if you want to write functional code, wrapping the for/while solution in a function achieves that.

The for loop/while loop combo is probably best in this case (recursion also works very well, and would give the cleanest solution, but isn’t performant in most JS engines)

9

Agree with you DanCouper.

This would be the recursive implementation:

const getNumBills = (amount, [x, ...xs]) => !x || !amount ? 
    0 : amount >= x ? 
    getNumBills(amount - x, [x, ...xs]) + 1 : getNumBills(amount, xs);

getNumBills(236.5, [100, 50, 10, 5, 1, 0.5])
// => 8
10

I saw this while doing CS50, here’s the solution implemented in C, tho here it count’s the amount of each bill instead of a number of bills: https://github.com/CoreData/cs50/blob/master/pset1/greedy.c

You can see the whole problem here: https://www.youtube.com/watch?v=9dZzyl7dCuw

Might give you some ideas :wink:

11

Hmm, recursive is pretty easy to make clean, especially with ES6 default parameters and destructuring. The line length gets a bit long though

function getNumBills(amount, [bill, ...bills] = [100, 50, 10, 5, 1, 0.5], count = 0) {
  if (amount === 0 || bill == undefined) return count;
  return getNumBills(amount % bill, bills, Math.floor(amount / bill) + count);
}

Written like that so easy to modify to also include number of each bill denomination:

function getNumBills(amount, [bill, ...bills] = [100, 50, 10, 5, 1, 0.5], acc = {total: 0, denominations: []}) {
  if (bill == undefined) return acc;

  const {total, denominations} = acc;
  const remainder = amount % bill;
  const count = Math.floor(amount / bill);

  return getNumBills(
    remainder,
    bills,
    {
      total: total + count,
      denominations: [{denomination: bill, count}, ...denominations]
    }
  )
}

So eg:

> getNumBills(267)
{
  "total": 7,
  "denominations": [
    {"denomination": 0.5, "count": 0},
    {"denomination": 1, "count": 2},
    {"denomination": 5, "count": 1},
    {"denomination": 10, "count": 1},
    {"denomination": 50, "count": 1},
    {"denomination": 100, "count": 2}
  ]
}

reduce is likely to give nicer solutions I guess

2 Likes
12

That recursive function is so sexy.

1 Like
13

Simply due to the output of this function, I like this one the best. It’s just great.

Talking about the original question, though, would a basic function suffice? Or would an interviewer expect a sexier function like mentioned above?

Here’s what I had in mind:

console.log(getNumBills(267));

function getNumBills(val) {
  let count = 0;
  
  while(val > 0) {
    // Subtract the greatest denomination that fits inside the current value, so we can find the next one
    val -= calcCurrentNum(val);
    // Increment the count - this is the value that we are looking for (once val is 0)
    count++;
    // Catch for endless loops in case there's a bug
    if (count > 100) return;
  }
  
  // Return the value of the greatest denomination that fits inside the given value
  function calcCurrentNum(val) {
    let bills = [1,5,10,20,50,100];
    // Start with the last index first, and cascade down to the lowest index.
    // If the given index fits inside the given value, then return the value of that index
    for (let i = bills.length; i > 0; i--) {
      if (val >= bills[i - 1]) return bills[i - 1];
    }
  }
  
  return count;
}
14

Heh, no, a basic function would definitely suffice, a for/while loop combo is great. The main language I use day-to-day doesn’t have loops, so the recursive solution is one I would normally use (that is the basic solution), but it’s not a good solution for JS*. If I used that, it would look like I was trying to be cute, or I didn’t quite understand JS. It would be a good conversation starter, but it’s not something that should generally be used imo.

* Recursion is not performant in JS. Also JS does not have tail call optimisation (which would help make it performant), and there are no plans to implement it. Even proper tail calls (which would prevent blowing the stack when recursing), which are in the ES2015 spec, seem to have little chance of being implemented by any major vendor.

2 Likes