Interview Question: Smallest Change
Vložit
- čas přidán 29. 08. 2024
- Coding interview question from www.byte-by-byt...
In this video, I show how to find the smallest number of coins required to make a given amount of change.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
Need an interview coach? Send in an application: www.byte-by-byte.com/coaching
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
Careful. In a competitive programming setting the recursive implementation will give you TLE. What you want to do is use dynamic programming and do it iteratively, storing the answers to smaller problems in an array
Yeah in an interview, that's not too much of a concern, but still a valid point/alternative solution
Hi what did you mean by TLE? too long execution? I'm an English learner thanks :)
Time Limit Exceeded
Nah, with the cache it will be almost as fast as iterative. However you will hit a stack overflow with large amounts.
For every coin, can't we just do num_coins = int(target/coin value) and then calculate remaining value by doing value = value - (coins * coin_value) until the num_coins = 1 ?
So, for example, if we take , coins to be 1, 4, 5 and value = 27; we start from largest coin value(to get min coins), that is, 5 and then do num_coin = int(27/5) = 5 coins; then do value = 27 - (5*5) = 27-25= 2. Repeat this for 2; we get zero 4 value coins and two 1 value coins and num_coins = 2/2 = 1. So, we stop the loop. Done!
Thanks Sam, You are awesome on explaining those dynamic programming concepts with examples.
wouldn't it be better if the breaking point was if (x < min(coins)) ? because if you get a coin system where there is no coin 1 you might not be able to get to 0
That would need to be handled separately because right now we're assuming that our return value is always an integer >= 0 that represents the number of coins. We'd need to handle the error case somehow where there is no valid way to make the change. You could do that for sure, but in this solution I just assumed that there's always a 1 cent coin.
nice tutorial. here is a python version with memoization
def make_change(total, coin_array, cache=None):
if not cache: cache = [0] * (total + 1)
if cache[total] > 0 or total == 0: return cache[total]
min_value = float('inf')
for coin in coin_array:
bal = total - coin
if bal >= 0:
count = 1 + make_change(bal, coin_array, cache)
if count < min_value: min_value = count
cache[total] = count
return min_value
much better than other youtube channels where they come up with some formula and never explain how they got that formula?
Thanks!
congratulations, I liked. Thank you for lightening us with your explanation!
There is a greedy algorithm which works well for some coin sets (e.g. the USA coin set) but may yield wrong results for the other ones. It is much less brain-damaging and very efficient. Here is the code (in C):
(please note that it can be improved to have run time complexity O(n) in the case the coin set is sorted in decreasing order)
/*
A greedy algorithm, works well for some coin sets (e.g. US), but may not work for others.
Time complexity: O(n^2), where n is a number of coins. No extra space required.
*/
static unsigned previous_biggest_value(const unsigned current_value, const unsigned values[], const size_t values_count)
{
size_t i;
unsigned max = 0;
for (i = 0; i < values_count; i++)
{
if (values[i] > max && (values[i] < current_value || current_value == 0))
{
max = values[i];
}
}
return max;
}
unsigned num_coins_greedy(unsigned amount, const unsigned values[], const size_t values_count)
{
unsigned curval, oldval, coins = 0;
if (values_count == 0)
{
return 0;
}
oldval = curval = 0;
while((oldval = curval, curval = previous_biggest_value(curval, values, values_count)))
{
unsigned ncoins;
if (oldval == curval) // skip duplicates
{
continue;
}
ncoins = amount/curval;
if (ncoins > 0)
{
amount -= ncoins*curval;
coins += ncoins;
if (amount%curval == 0)
{
break;
}
}
}
return coins;
}
What was the logic for the line: if(min > c + 1) min = c+1;
I don't understand the purpose of this line
The change for 32 could be made using 32 ones coins and also could be made using 6 fives and 2 ones. But the minimum number of coins would be 4 coins : 25+5+1+1. That's what the min is for.
@@AkshayKumar-xh2ob I think the reason for this condition if (min > c+1) min = c +1; is because if the value of min is greater than 1 or 2 don't return the min value which might be (7 ,32) in this case instead increase the coin count by 1.
It's c + 1 because you are doing it recursively, so once you enter into recursion your are getting rid of one coin, soyou have to add one to the min because you were using that coin.
great video, but int min = x, looks a bit cryptic, because int min doesn't depend on value x. min = MAX_INT is way more intuitive for this problem
I guess this doesn't work when coin is [2] and amount is 3. It returns 2 whereas it's not possible.
Can you also share solution for a problem if the x is 6 and coins are {1,3,4} as you mentioned initially in the video?
Which mechanical keyboard you are using ? Sound is sweet.
11:00 what if the smallest coin is 4 and x is starting as 3, it should return 0 but it returns 3 :/
How would I return -1, if there is no solution assuming we don't have a change of coin 1?
can you tell me what does the variable c store
Thank you. I really learn a lot from the java problems. :)
Can u pls explain in depth the time complexity of the recursive soln w/ memoization?
This is definitely not the optimal solution. The optimal solution is O(1). Or, in fact, it is O(f(coin system)) for some f not relevant to n.
exactly what I was thinking . why cant we just sort the coins array and then start dividing and store remaining change using mod and by the end return the coins ....
For US coin system, simple greedy approach works and is faster than this, but what if there was no 5 cent coin and smallest for 30 is 3 dimes not a quarter and 5 pennies?
This is my solution for python users and slightly different:
def change_making(coins, x, cache, idx):
if x == 0:
return cache
if coins[idx] > x:
return change_making(coins, x, cache, idx-1)
else:
x -= coins[idx]
cache.append(coins[idx])
return change_making(coins, x, cache, idx)
and, works for any kind of coin system
Can you please do this problem?
Given a dollar amount convert it into euro coins and bills . You are given the dollar amount as the argument, and said that the dollar to euro rate is 1.30. You are given that euro denomations are 500 bill, 200 bill, 100 bill, 50 bill, 20 bill, 10 bill, 5 bill, 2 bill, 1 bill, 50 cents, 25 cents, 10 cents, 5 cents, 2 cents, 1 cent. Convert that dollar amount into the least amount of bills and coins.
That is the same problem in disguise. Convert bills to coins (e.g. 1 bill = 100 coins).
Why not use tail recursion and math operators?
public static int minCoins(int money, int[] coins) {
Arrays.sort(coins);
// sort just to be sure the largest coin is the last in the list
return minCoins(money, coins, coins.length-1, 0);
}
// Tail Recursive version...
private static int minCoins(int money, int[] coins, int i, int count) {
if(i < 0) return count;
return minCoins(money % coins[i], coins, i-1, count + money / coins[i]);
}
Here you are assuming that the coins array is in descending order. Am I right?
yep
Thanks Sam! What is the time complexity of brute? I would think numCoins^inputX. inputX is maximum height. but ur dp book says inputX^numCoins..
Yep you're right. There's a typo in the book.
public void change(int x, int[] coins){
List changeList = new ArrayList();
for (int i = 0; i < coins.length; ){
if(x - coins[i] >=0){
changeList.add(coins[i]);
x = x - coins[i];
}
else
{
i++;
}
}
System.out.println(changeList.toString());
}
Can't we check the cached value, before 'for loop', like we had for base conditions.
yep
What if we need to find the list of used coins that were taken to make x? Here, our x is 32, we used these coins: [1, 1, 5, 25]. I've tried so many ways to get the list of used coins but it is not working. Can you please comment or suggest how should we do?
You'll need to keep track of the coins used in each path
@@ByteByByte And then check the paths to find out which one is the shortest ?
Great example to show a greedy algorithm would not work for this problem.
thanks!
Why don't use / and - to calculate the number of coin?
You could do that too
No recursion solution... because for me "76" would not work... indefinite hang..
public static int change(int x, int[] coins) {
int count = 0;
for (int i = 0; i < coins.length; i++) {
int times = x / coins[i];
x = x % coins[i];
while (times > 0) {
count += 1;
times--;
}
}
return count;
}
thnks for nice explanation...
you're welcome!
How this solution work for this input amount = 3, int[] coins = {2}?
public int coinChange(int[] coins, int amount) {
// base case
if(amount == 0) return 0;
int min = amount;
for(int coin: coins){
if(amount - coin >= 0){
int c = coinChange(coins, amount - coin);
if(min > c+1) {
min = c+1;
}
}
}
return min;
}
Is there a dynamic programming solution, make no use of recursion?
Yeah, take a look at my ebook www.dynamicprogrammingbook.com
Can somebody explain to me that for loop, how does it work ?
for( int coin : coins )
For each coin in coins. It's just a Java for-each loop
MMM got it, First time I see a for loop written that way, im in this tutorial, thanks for all this video ma, and for your help, Im a computer science student and im getting ready by studying for interviews and this are helping a lot, Im trying to do do them by myself first before looking at the solution. Any suggestion or advice i would appreciate it, thanks for everything
Not sure the reason for recursion or the cache or the Java :')
```
from collections import defaultdict
def getcoin(amt, coin_system):
# return the largest coin that is less than or equal the amount
return max(filter(lambda x: x 0:
coin = getcoin(amt, coin_system)
change[coin] += 1
amt -= coin
return change
```
or the if statements :D
Does that always work? What if I have coins = {1, 6, 10}?
I guess below code works for any denomination
int coins = 0;
int[] den = {1,10,25,5};
Arrays.sort(den);
while(x>0){
for(int i=den.length-1;i>=0;i--){
if(x-den[i] >=0){
coins++;
x=x-den[i];
//System.out.println(x);
break;
}
}
}
System.out.println(coins);
Does it work for any denomination? What if you have den = {1, 6, 10} and the input is 12?
A good follow up question could be - Can we have a coin system with -ve or zero coin value?
What if did the dynamic programming first in the interview ?:D
I'm an interviewer at Groupon. Usually, I prefer for the candidate to go through a naive solution. In fact, I ask for that. The reason is that it naturally leads me to talk about the run time. Also, in a real-life situation, unless is a known problem, you probably will go with a naive solution and then make it better. And in an interview, as an interviewer, I like to see how is that particular train on thoughts.
Hope my answer helps :)
Here's my solution:
class Solution {
Map map = new HashMap();
public int coinChange(int[] coins, int amount) {
if(map.containsKey(amount)) return map.get(amount);
if(amount == 0) return 0;
int min = Integer.MAX_VALUE;
for(int coin : coins) {
if(amount >= coin) {
int temp = coinChange(coins, amount - coin);
if(temp < min && temp >= 0) {
min = temp + 1;
}
}
}
if(min == Integer.MAX_VALUE){
min = -1;
}
map.put(amount, min);
return min;
}
}
why first solution has quadratic runtime?
input coins={2}, sum=3 - your program returns 2 which is a wrong answer.
What assumptions are we making about the input in the video?
How to solve correctly if coins{2} sum={3}????
@@ByteByByte That there's always a 1 cent coin?
What if coins = [25, 18, 17] and x = 35. Program returns 11 which is incorrect.
Iterative solution example :
private static int minimalCoin(int amount, int[] coins) {
int nbOperations = 0;
int i = 0;
while (amount > 0) {
while (amount >= coins[i]) {
nbOperations++;
amount = amount - coins[i];
}
i++;
}
return nbOperations;
}
public static void main(String[] args) {
int coins[] = {25, 10, 5, 1};
System.out.println(minimalCoin(127, coins) + " operations");
}
try for this input minimalCoin(6,new int[]{4,3,1});
follow up: what is the maximum number of coins required to make the change for the given amount?
You sound like Johnny Sins