Coin Change Problem: Python interview with a Google engineer

Поделиться
HTML-код
  • Опубликовано: 23 дек 2024

Комментарии • 686

  • @interviewingio
    @interviewingio  3 года назад

    Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&

  • @darrorpsk6148
    @darrorpsk6148 5 лет назад +968

    Haven't finished this video yet, but i must say i absolutely love how the interviewer is trying to get the interviewee on the right track with his questions. Wanted to clap out loud for the interviewer here.

    • @norpriest521
      @norpriest521 5 лет назад +2

      You should watch video where someone quit Google to become his own man.
      This video is nothing.

    • @michal304
      @michal304 5 лет назад +4

      @@norpriest521 Could you give an example? I would really like to see that!

    • @norpriest521
      @norpriest521 5 лет назад +2

      @@michal304
      Just search RUclips "Why I left Google"
      You'll see so many videos about that 😂

    • @sinanyaman2007
      @sinanyaman2007 5 лет назад +26

      this is not a Google interview, this is a mock interview. You register to some website and they get you ready for a real interview with these mock interviews. That is why the guy is so helpful :)

    • @annekedebruyn7797
      @annekedebruyn7797 5 лет назад +14

      Python engineers are always cool.
      Maybe it's because we are always being bullied for being pseudo code. :(

  • @TheHaters112
    @TheHaters112 5 лет назад +704

    No.1 rule of coding in a team is;
    Don't be smart. Keep it simple.

    • @jakobzc5805
      @jakobzc5805 5 лет назад +17

      One of my professors said "never hire a programmer that uses recursion for !5" or something like that.

    • @Spaced92
      @Spaced92 5 лет назад +11

      @@jakobzc5805 Recursion is not smart at all, ignoring it being more memory intensive, because it gives you the answer and not the solution there's a certain point for a programmer where recursion becomes easier.

    • @osquigene
      @osquigene 5 лет назад +10

      @@Spaced92 Recursion is simpler to write (and read) in many cases, that's the only reason why it's used at all. On the other hand it can slow things down and use more memory indeed. But most of the time, you don't care about speed or memory. The only thing that you need to take care of when writing a recursive function is that call stack may explode (depending on the language and how deep the recursion goes). In python, recursion is particularly dangerous because there is no optimisation behind it at all (even tail recursive function won't be interpreted as a recursive piece of code and over a depth of a few thousands crack, your code breaks).

    • @draakisback
      @draakisback 5 лет назад +2

      @@osquigene depends on the stack. If I was implementing this coin algorithm in elixir I would use recursion and it would be extremely efficient

    • @osquigene
      @osquigene 5 лет назад

      @@draakisback real recursion can't be more performant than a simple loop. Make sure you are writing a real recursive function and not a tail recursive one (because tail recursive functions will often be transformed to a simple loop by your compiler). I don't know anything about elixir so I can't tell how/when such optimization are made, but I guess you can figure this out :)

  • @soledapper
    @soledapper 5 лет назад +244

    I've watched this Google Interviewer many times, and you can tell that he wants to set his interviewees up for success. You can tell he's doing this to become a better interviewer

    • @googleuser7771
      @googleuser7771 5 лет назад +3

      So everyone gets the job?

    • @martinwujkowski2270
      @martinwujkowski2270 5 лет назад +7

      @@googleuser7771 you can still get to know skills of the interviewee anyways

    • @youngcitybandit
      @youngcitybandit 5 лет назад +11

      @@googleuser7771 Are you trolling or are you genuinely that stupid? This is a practice interview and so obviously it would be nice to help the interviewee improve on their skills. On top of that, the interviewer is to try to see the thought process of the interviewee in solving the answer. Some questions you might get stuck on due to nervousness or a little misunderstanding, and so you give them hints and see what they do

    • @andoniades
      @andoniades 5 лет назад +3

      True, he's patient and helping him out. Also getting him to talk so he can understand the interviewee's thought process.

    • @SouravendraKrishnaDeb
      @SouravendraKrishnaDeb 4 года назад

      @@googleuser7771 if you've ever interviewed you should be aware that interviewers aren't out to eat you. They're very professional and helpful.

  • @xxoan.1613
    @xxoan.1613 5 лет назад +282

    "i don't think this is gonna give me the optimal solution"
    "it will, in fact"
    10/10

    • @pounet2
      @pounet2 5 лет назад +10

      Except it is not ! At least in the general case.
      First you should define what "optimality" should be in this case. Putting this question aside, let's say the machine has only quarters and dimes (even in infinite amount) but no nickels and no pennies.
      For 30 cents, with the proposed method, you first give back a quarter and then you get stuck... what is hardly optimal considering than there exists a solution :
      3 dimes.
      I'm just at the beginning of the video, but as far as I understand the problem, it is an integer linear program. Well known not to be completely trivial (not sure it is a NP problem but whatever...). So I'll use a library like Pulp to solve it with minimal coding. If such a library is not available, you will have to implement a solution from scratch (for instance a backtracking algorithm... but other methods are possible).
      Let's see what comes next :)
      OK... now the interviewer reckons that the initial solution is not optimal for any set of coins. Not my example, but well... and they have defined the aim (minimize the number of returned coins). Nice. I guess in this case (if no library is allowed), I will implement a recursive algorithm... let's see.

    • @pounet2
      @pounet2 5 лет назад

      @UCmLUWwyB8tygqXBMA4JacBw Don't know exactly what you mean. I don't say that a recursive algo would be the most efficient (I'm pretty sure its not), but it is simple to write. Something like this:
      def num_coins(cents):
      coins=[25,10,5,1]
      val=cents
      for coin in coins:
      val=min(val,num_coins(cents-coin))
      return val+1
      Done :)
      But you are right : even without considering the efficiency, it is clearly not the best. For large values of cents, it will quickly exceed the size allowed by python for the stack.

    • @theomc1488
      @theomc1488 5 лет назад

      @@pounet2 yeah theres simple algorithms which state that simplly going through decreasing quantities and checking which values fit is not the optimal solution.

    • @pounet2
      @pounet2 5 лет назад

      It is a fun problem. Moreover, it brings back some memories. It is one of the first problem given to my class by our math teacher when I still was in high-school learning basic coding (in Pascal if I remember correctly). Same problem but with a finite number of coins in the machine (I guess this problem is probably tackled during the video... really have to watch it to the end).
      My solution was the one proposed at the beginning (greedy algo). I was quite proud of myself :) Then the math teacher asked me if it was optimal... I didn't thought much about it at the time. I was thinking : "Of course, it should be optimal, it is such a simple and beautiful solution... how could it not be". It was the very first time I heard about the optimality of an algorithm.
      Many years after, I find myself thinking about this problem again... and discovering that I was not right ;)

    • @aidan5577
      @aidan5577 5 лет назад

      I read this msg while the video played it lmao

  • @cthecheese1620
    @cthecheese1620 5 лет назад +17

    These interviews are helping me focus on my own solutions while others talk about the same problem, thank you!

  • @crlfff
    @crlfff 5 лет назад +300

    He was making it more complicated than it really was

    • @rban123
      @rban123 5 лет назад +5

      Zeppelin waaaaaay more complicated

    • @DanteEhome
      @DanteEhome 5 лет назад +11

      I think just divide it and find remainder should be an easier approach. But maybe his approach can be adapted to other currencies? idk.

    • @HoRNET_FPV
      @HoRNET_FPV 5 лет назад +14

      Dude, took me like 10 line of codes and 3 min, if this is was real I'd hire myself haha

    • @rban123
      @rban123 5 лет назад +3

      Antoine Parra same here, this was excruciating to watch

    • @rico454
      @rico454 5 лет назад

      DIE HAPPY is it java?

  • @aaronpcjb
    @aaronpcjb 5 лет назад +6

    That interviewer sounds like such a lovely person. I'm glad the interviewee eventually twigged he wanted to hear "Least Common Multiple".

  • @adamgarcia3273
    @adamgarcia3273 5 лет назад +101

    Interviewer: hello, thank y-
    Me: ok so "Hello world"

  • @xReisk
    @xReisk 5 лет назад +167

    WHo ever created this webpage/channel, its a genius! thanks for sharing, will checkout the website later!

    • @evelynrthomas9982
      @evelynrthomas9982 5 лет назад +4

      It was 68 but I added my like. You're welcome.

    • @xReisk
      @xReisk 5 лет назад

      @@evelynrthomas9982 Nice! :D

    • @BsiennKhan
      @BsiennKhan 5 лет назад +2

      I don't like odd numbers, so made it 90 likes

    • @Zaluskowsky
      @Zaluskowsky 5 лет назад

      @@BsiennKhan i helped you out there because it was stingy 93

  • @Satialfactory
    @Satialfactory 5 лет назад +157

    Interviewee: "I don't know why this is happening"
    Interviewer: "I don't know why this is happening"

  • @aznhomeboi10
    @aznhomeboi10 5 лет назад +228

    I would say rather than thinking about optimal solution straight off the bat go for actually solving the problem and then optimize your solution.

    • @thecodingfoundation
      @thecodingfoundation 5 лет назад +8

      Agreed

    • @norpriest521
      @norpriest521 5 лет назад +6

      @@thecodingfoundation
      Nah

    • @thecodingfoundation
      @thecodingfoundation 5 лет назад +10

      @@norpriest521 ok

    • @michak1456
      @michak1456 5 лет назад +32

      in many cases optimizing requires a completely different approach to the problem, for example when you want to achieve better
      computational complexity

    • @thecodingfoundation
      @thecodingfoundation 5 лет назад +23

      @@michak1456 yeah but first priority should be creating something that works, then optimize after.

  • @haha-ui3fp
    @haha-ui3fp 5 лет назад +5

    As many have correctly pointed out the dynamic solution is incorrect. This is easily seen for values 36,37,55,80, Actually there is 2 mistakes in it: one I believe is simply a typo - in the innermost loop num_of_coins is indexed with [cents - coins_j * j ] instead it should be [i - coins_j * j]. This correction alone makes it so that for the given numbers and with later discussed optimization (bringing all values below 50 before using dp algorithm) it would produce correct results, while technically being still incorrect.
    The more important logical problem is that the line "coins_j = i / j" is still essentially greedy. E.g. in case of 55 it will try with 2 quarters + num_of_coins[5] and on next iteration 5 dimes + num_of_coins[5], but the algorithm will never try 1 quarter + num_of_coins[30] (=3 dimes). Therefore it won't get the correct answer for arbitrary coin composition and sum paid.

  • @cleverclover7
    @cleverclover7 5 лет назад +41

    I really appreciate these. The discussion afterward was good too. There are lots of reasons a person might not perform well in an interview like this, irrespective of how good they would be at the job. Fitzgerald only wrote 5 novels, Koontz has written over 80 - speed isn't everything.

    • @jflopezfernandez
      @jflopezfernandez 5 лет назад

      That's a great point

    • @samarthkapuria
      @samarthkapuria 5 лет назад +3

      Writing a novel has absolutely nothing to do with programming. Extremely bad analogy I'm sorry.

    • @cleverclover7
      @cleverclover7 5 лет назад +10

      @@samarthkapuria Of course programming is almost nothing like writing a novel, but the analogy is not about the work it is about the type of people who are good at certain types of work with different constraints.

    • @samarthkapuria
      @samarthkapuria 5 лет назад +1

      @@cleverclover7 yeah but writing is an art. Programming has very little to do with art. You need to solve a problem fast. Getting a better program at a later time is not as beneficial as solving the problem faster in most cases, especially this scenario I believe.

    • @sananyuzb
      @sananyuzb 5 лет назад +2

      In case of Google interview : on each round candidate has 45 minutes to solve the question and during that time, he/she should give correct approach and write code on whiteboard. It is very challenging. And when they say "you write code very slow" it means that candidate could not able to complete the question in 45 minutes, but it does not mean that he is weak. Recruiters git feedback from interviewers, and if they see that candidate could not able to solve in 45 minutes, they just do not give offer, that is all, they are not interested how smart candidate is, they just see feedback and make decision based on feedback. And also another point is that, during that type of interviews each candidate can have different difficulty questions. I mean one candidate can get easy and medium questions, and another get medium and hard. So probably the first candidate will pass, although the second candidate could be more suitable for role, but he got unlucky and got difficult questions.

  • @587Nishant
    @587Nishant 5 лет назад +1

    Loved the question.
    Here's my answer with Recursion
    #1 quarter - 25,1 nickle (5), 3 pennies (1) [dime 10]
    register = {'quarter':0,'nickle':0,'dime':0,'pennies':0}
    def getCents(num,coins = 0):
    if (num == 0):
    return register,coins
    if(num >= 25):
    div,mod = divmod(num,25)
    register['quarter'] = div
    coins += div
    coins = getCents(mod,coins)
    elif(num >= 5):
    div,mod = divmod(num,5)
    register['nickle'] = div
    coins += div
    _,coins = getCents(mod,coins)
    else:
    register['pennies'] = num*3
    coins += num*3
    return register,coins
    getCents(31)

  • @LeonardoDonelli
    @LeonardoDonelli 5 лет назад +34

    The interviewee algorithm for the second case (no nickels) is incorrect. The Google engineer almost caught it, but gave an incorrect counter example that worked by chanche. In the end didn't recognize the issue and accepted the solution as correct.
    The counter example he could've used at 24:25 is 55, or 80, or a number of others.
    For example with 55, following the interviewee incorrect algorithm:
    * Two quarters, 5 leftover which can be given with 5 coins: 2 + 5 = 7
    * 5 dimes, 5 leftover which can be given with 5 coins: 5 + 5 = 10
    * 55 pennies with no leftover = 55
    So his algorithm would return 7: 2 quarters and 5 pennies. The real solution for 55 is is 5: 1 quarter and 3 dimes. His solution is incorrect because he always tries the maximum amount of the current denomination and then checks the leftover, but in some cases (like 55) he shouldn't take the maximum of any denomination.

    • @ThaAidry
      @ThaAidry 5 лет назад +14

      The difficulty of the problem went from 0-100 real quick.

    • @benbishop7512
      @benbishop7512 5 лет назад +1

      The solution for 55 is 4 not 5.

    • @matisluzi1137
      @matisluzi1137 5 лет назад +1

      The correct answer for 55 is 3: 2x25 and 1x5 (2 quarters and 1 nickel)

    • @benbishop7512
      @benbishop7512 5 лет назад +7

      Matis Matis incorrect. There are no nickles.

    • @LeonardoDonelli
      @LeonardoDonelli 5 лет назад +2

      @@benbishop7512 yeah you're right, it's a typo in my answer, 3 dimes and 1 quarter so 4 coins.

  • @aryatalera1552
    @aryatalera1552 3 года назад +2

    I have a question about this breaking point. The interviewer says that the LCM is something where we can easily use the quarter without blocking us from getting the best solution.
    But that won't be true, for example 56
    Using that LCM, what we would do is first remove the 50 using 2 quarters and then be left with 6 which we would have to use 6 pennies for resulting in 8 as our answer but actually we can use 1 quarter, 3 dimes and 1 penny, resulting in 5 as our answer.
    If there is a problem in my understanding of the question, pls tell me.

  • @DestinyIsDecided
    @DestinyIsDecided 5 лет назад +13

    34:50 Answer because the LCM(Least Common Multiple) of 10 and 25 is 50 -> basically you can use 2 quarter cents instead of 5 dimes if its 50, thats the break point

    • @DestinyIsDecided
      @DestinyIsDecided 5 лет назад +2

      @John Brocksman ​ Say you need to give change using "A" and "B" (A>B like quarter>dime). The least number you for which you can always use "A" is the LCM of A and B (lets say C is the LCM of A and B), this is the statement I made before,
      The reason is to give change for amount C you can either use A*X or B *Y (because A and B both can divide C, lets say C/A= X and C/B = Y and since A is greater than B, X would be less than Y) So using X coins of A would be better to reduce the number of coins we are using.
      Can we use A if the change is below C? We can , but it depends on the situation. You have to use special logic, as he did in the video before 34:00 minutes,
      lets see for 43 and 47 cents which are below 50(LCM of 25 and 10)
      1. for 43 you need 1x25cents, 1x10cents, 8x1cents = 10 coins,
      or you can use 4x10cents, 3x1cents = 7 coins, so you would avoid using 25cents
      2. for 47 cents you need 1x25cents, 2x10cents, 2x1cents = 5 coins,
      or you can use 4x10cents, 7x1cents = 11 coins, so in this case you will use 25 cents coin
      lets see for 51 and 71 which are above 50 (LCM of 25 and 10)
      3. for 51 you need 2x25 cents, 1x1cent = 3 coins
      or you can use 5x10cents, 1x1cent= 6 coins
      4. for 71 you need 2x25 cents, 2x10cents, 1x1cent = 5 coins
      or you can use 7x10cents, 1x1cent= 8 coins
      In case 3 and 4 you can replace 5x10 cents with 2x25 cents always, you will have less number of coins when you use the higher value, and the replacement happpens at the LCM number.

    • @kieranmoynihan1161
      @kieranmoynihan1161 5 лет назад +1

      @@DestinyIsDecided Try 55

    • @DestinyIsDecided
      @DestinyIsDecided 5 лет назад

      ​@@kieranmoynihan1161 It would be similar to case 3 in above comment
      for 55 you need 2x25 cents, 5x1cent = 7 coins
      or you can use 5x10 cents, 5x1cent = 10 coins
      So you would use 25 cents to reduce the number of coins

    • @kieranmoynihan1161
      @kieranmoynihan1161 5 лет назад +3

      @@DestinyIsDecided That's where you're wrong. 55 can be made with 1x25 + 3x10, meaning only 4 coins.

    • @DestinyIsDecided
      @DestinyIsDecided 5 лет назад +1

      @@kieranmoynihan1161 Haha, you got me I forgot about that.
      But my point is still true. As you are using a 25cent coin, bcz the number 55 is greater than the LCM 50.
      So I am not wrong (as the question is do we need 25cent coin for sure), I just missed the least coins answer.

  • @alissondamasceno2010
    @alissondamasceno2010 5 лет назад +2

    I took a slightly different approach to return a list of coin names, instead of their count (before watching the entire vid):
    coins = {
    "Quarter" : 25,
    "Dime" : 10,
    "Nickel" : 5,
    "Pennies" : 1,
    }
    def num_coins(cents, coins):
    exchange = []
    rest = cents
    coin_idx = 0

    while rest > 0:
    coin_name = list(coins.items())[coin_idx][0]
    this_coin = (cents // coins[coin_name])
    for coin in range(this_coin):
    exchange.append(coin_name)
    rest = cents % coins[coin_name]
    cents -= this_coin*coins[coin_name]
    coin_idx += 1
    return exchange

  • @BayMacDre415
    @BayMacDre415 5 лет назад +2

    The problem with removing the nickel is you eliminate your ability to make common factor. 25 is a more efficient way to get to the number 50, which is also a multiple of 10. Quarters can get to 50cents more efficiently than dimes, but times are a higher resolution unit so they can do the fine adjustment. However, if a number is less than 50 but close to a common multiple of 10 (if you're over 50 you simply subtract 50 and use the remainder) then you use dimes.
    Just divide by quarters first, and then divide by dimes (unless it's over 50 then divide the remainder after you take out two quarters). If the most efficient solution requires one quarter with a combination of dimes, that will result from the first test.

    • @z08840
      @z08840 3 года назад

      it's incorrect - at 49 you still better use 25 => 1*25+2*10+4*1 - and the last with 1s (4*1) gives a clue where breaking point is - you still better use 25 up to (and including) 45, but from 44 by using 25 you will need 9 of 1s, so you better use 10s - 4*10+4*1 - to calculate breaking point - 25+10+(10-1) = 44

  • @Entellex
    @Entellex 5 лет назад +9

    I just used multiple while loops. I am not sure if the point of the interview was to make the code complex or if you had specific rules.
    change_due = 67
    quarters = 0
    dimes = 0
    nickels = 0
    pennies = 0
    while change_due > 0:
    while change_due >= 25:
    quarters += 1
    change_due -= 25

    while change_due >= 10:
    dimes += 1
    change_due -= 10

    while change_due >= 5:
    nickels += 1
    change_due -= 5

    while change_due >= 1:
    pennies += 1
    change_due -= 1

    print(change_due)
    print(quarters)
    print(dimes)
    print(nickels)
    print(pennies)

    • @hellstormangel
      @hellstormangel 5 лет назад +1

      why not clean it up as follows:
      change_due = 67
      change = [25, 10, 5, 1]
      coins = [0,0,0,0]
      for idx, coin in enumerate(coins):
      if change_due = coin:
      coins[idx] += 1
      change_due -= coin
      return len(coins), coins

    • @stifer0X0
      @stifer0X0 5 лет назад +2

      The first part of the question was just a warm up question. While what you are doing is correct for this example, it will not work in general with a different set of coin denominations, nor will your approach give the correct minimum number of counts for a different set of denominations.

    • @nityacohen2950
      @nityacohen2950 5 лет назад

      The video's answer is better. I originally tried something similar but with if statements.
      That code is a lot slower. If the input is 10000000, the runtime will clearly be longer than the video's solution of 4.

  • @JJ-Bond
    @JJ-Bond 5 лет назад +65

    Sounds like the same guy from Google again

  • @klab3929
    @klab3929 5 лет назад +12

    I have no clue how to approach any of these problems... but im still watching lol

  • @abhaykanwasi881
    @abhaykanwasi881 2 года назад +1

    Is it only me who get different output at 8:10 timing in video I get output 4.04 but they get 3 as output Or it is because of python version I'm using is different from what they are using.

  • @code-911
    @code-911 4 года назад

    This interviewee starts to code out without even discussing the next approach properly. Breaks the fundamental idea. But kudos to the interviewer, and you are really lucky if you get such a helping interviewer.

  • @DashieDasher
    @DashieDasher 5 лет назад +15

    from collections import OrderedDict
    QUARTER = "Quarter"
    DIME = "Dime"
    NICKEL = "Nickel"
    PENNY = "Penny"
    COIN_VALUE = {QUARTER:25, DIME:10, NICKEL:5, PENNY:1}
    def make_change(cents, drawer):
    change = OrderedDict()
    change[QUARTER] = 0
    change[DIME] = 0
    change[NICKEL] = 0
    change[PENNY] = 0
    while cents > 0:
    for coin in change:
    if drawer[coin] > 0 and cents >= COIN_VALUE[coin]:
    change[coin] += 1
    cents -= COIN_VALUE[coin]
    drawer[coin] -= 1
    break
    return change
    if __name__ == '__main__':
    drawer = {QUARTER:100,DIME:100,NICKEL:0,PENNY:100}
    change = make_change(83, drawer)
    for coin in change:
    print("{}: {}".format(coin, change[coin]))

    • @felkandoesthings
      @felkandoesthings 5 лет назад

      Nice solution! It doesn't work for 55 however, 25 + 10 + 10 + 10 should be the answer yours gives 25 + 25 +1+1+1+1+1. Always using the biggest coins is not optimal in some solutions, maybe try with a table like the guy in the interview did.

    • @Eva-lz5ig
      @Eva-lz5ig 5 лет назад

      You don't need imports, and that's way more complicated than it needs to be
      denoms = [10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1]
      def makeup(change, denoms = denoms):
      for denom in denoms:
      yield f"{change // denom} bills of {denom} cents"
      change -= (change // denom) * denom
      print("
      ".join(list(makeup(83))))

  • @megatroneata9911
    @megatroneata9911 5 лет назад +29

    def find_num_coins(total):
    num_coins = 0
    denominations = [1,5,10,25]
    while total > 0:
    last = len(denominations)-1
    if total < denominations[last]:
    denominations.pop()
    else:
    total -= denominations[last]
    num_coins +=1
    return num_coins

    • @zen_wheels
      @zen_wheels 5 лет назад +10

      google wants to know ur location !!!

    • @neerajraut6473
      @neerajraut6473 5 лет назад +3

      i really liked your solution. But the solution in the video is unclear to me the part where
      for coin in coins:
      num_coins+=cents/coin
      cents= cents%coin
      how did this work exactly? if u could help me out , i am a beginner and just started learning python

    • @megatroneata9911
      @megatroneata9911 5 лет назад +6

      @@neerajraut6473 say cents = 33
      for coin in coins:
      (iterate through coins starting at 25)
      num_coins += 33/25 (which = 1)
      (dividing checks the max number of times i can use this denomination so if cents = 76, 76/25 = 3, I can use the quarter 3 times
      cents = 33%25 (which = 8)
      (this checks how much I am left with after I use the denomination how many ever times. In the case of 76, 76%25 = 1
      if cents == 0
      (we have nothing left to check)
      break
      (if it is not 0, then we can move on to the next denomination which is 10, cents = 8, 8/10 = 0 so we are adding 0 to num_coins, 8 mod 10 = 8, and then we move on to next denomination and so on)

    • @megatroneata9911
      @megatroneata9911 5 лет назад +5

      @@neerajraut6473 also in python 3 you have to use int(cents/coin) to get the correct answer

    • @megatroneata9911
      @megatroneata9911 5 лет назад

      @@neerajraut6473 One more thing. The videos solution is actually better than mine. Mine is faster if the answer is less than 4 and slower if it is more

  • @SumoCumLoudly
    @SumoCumLoudly 5 лет назад +18

    def num_coins(cents):
    coins = [25, 10, 5, 1]
    count = 0
    for coin in coins:
    while cents >= coin:
    cents = cents - coin
    count += 1
    return count

    • @demonkoryu
      @demonkoryu 5 лет назад +2

      Yeah, that's my solution too.

    • @dan-3268
      @dan-3268 5 лет назад +1

      that's so beautiful...

    • @orion6618
      @orion6618 5 лет назад

      Worst solution, imagine that you have 99999999 coins, You would have to plus the coins millions of times.

    • @jackfinan9060
      @jackfinan9060 5 лет назад

      def num_coins(cents):
      if cents >= 25:
      count = cents // 25
      cents %= 25
      if cents >= 10:
      count += cents // 10
      cents %= 10
      if cents >= 5:
      count += cents // 5
      cents %= 5
      count += cents
      return count

    • @Suplagen
      @Suplagen 5 лет назад

      @@jackfinan9060 Why would you post a worse solution under a good one?

  • @rishangprashnani4386
    @rishangprashnani4386 5 лет назад +23

    you can go with [25,10,1], then pop out the first element, go with [10,1], then go with [1]. then take the minimum

    • @BryceRoche
      @BryceRoche 5 лет назад +3

      exactly ... way simpler

    • @cod4Rlp
      @cod4Rlp 5 лет назад +1

      smart

    • @rishangprashnani4386
      @rishangprashnani4386 5 лет назад

      thankyouu

    • @andrewisaac1061
      @andrewisaac1061 5 лет назад +17

      That will not work ... try to input 55 with your algorithm it will give you 7 coins .. which is wrong the correct answer is 4 (1 of 25 and 3 of 10)

    • @rishangprashnani4386
      @rishangprashnani4386 5 лет назад

      @@andrewisaac1061 yea, it won't :(

  • @walidzein1
    @walidzein1 5 лет назад +173

    it's all about modulus

    • @Anequit
      @Anequit 5 лет назад +6

      @SatansFlipFlopgo get that bag

    • @mohamedaminebenbouali2941
      @mohamedaminebenbouali2941 5 лет назад +1

      @@Anequit plipplop

    • @homeskilybisket
      @homeskilybisket 5 лет назад +2

      ​@SatansFlipFlop def num_coins(cents):
      pcents = cents
      q = d = n = p = 0
      q = pcents // 25
      pcents -= (25*q)
      d = pcents // 10
      pcents -= (10*d)
      n = pcents // 5
      pcents -= (5*n)
      p = pcents // 1
      pcents -= (p)
      print(q, d, n, p)
      num_coins(33)
      wouldnt this make more sense less looping

    • @dhkatz_
      @dhkatz_ 5 лет назад

      @@homeskilybisket That is not scalable, what if you wanted to change which coin denominations you had? It's just as easy to use a loop.

    • @slowtyper95
      @slowtyper95 5 лет назад

      @SatansFlipFlop this one doesn't handle the second question right?

  • @TheDmviper
    @TheDmviper 5 лет назад +4

    line 41 should be
    temp = min(temp, coins_j + num_of_coins[i%j])
    the way you have it currently would break if solutions to num_of_coins were stored for future calls to the function

  • @RT-.
    @RT-. 5 лет назад +2

    If you would convert everything to the same unit, wouldn't you be able to do this using modulo?

  • @Pulits
    @Pulits 5 лет назад +27

    My interview at Google as a front-end developer was brutal. All they gave me was a Google Doc (no text editor or IDE). There was little interaction with the interviewer. The problem was in a very specific format and all he said was "that's not ok" or "that works".

    • @baptiste6436
      @baptiste6436 5 лет назад +1

      What was in the google doc?

    • @Pulits
      @Pulits 5 лет назад

      Bapt Iste A problem on how to traverse the DOM with a function that received a node and a callback

    • @baptiste6436
      @baptiste6436 5 лет назад

      @@Pulits Oh I see! Thank you

    • @andoniades
      @andoniades 5 лет назад +1

      Did u pass that interview and are you still in the hiring process? Best of luck to you

    • @dhkatz_
      @dhkatz_ 5 лет назад +1

      @@srt-fw8nh Google exists, use it.

  • @megatroneata9911
    @megatroneata9911 5 лет назад +5

    also that "ran out of nickels" wrench didnt make sense to me. Why not just delete 5 from the list of denominations? is the function supposed to handle any set of denominations?

    • @mohithm.p6091
      @mohithm.p6091 5 лет назад +6

      If you just remove 5 from the list and use the same code it will return more coins in some cases, for example in case of 31 cents it will return 7 which consist of one 25 and six 1’s, but we can also get three 10’s and one 1 totals 4 is less no of coins. They are trying get minimum no of coins.

    • @megatroneata9911
      @megatroneata9911 5 лет назад +1

      @@mohithm.p6091 Ahhh got it

  • @Oli420X
    @Oli420X 5 лет назад +25

    This is much easier than what he made it out to be

    • @victorsamsonov4942
      @victorsamsonov4942 4 года назад +3

      So far all the ppl in the comments that posted the solution thinking they got it rights were wrong

  • @appophiss3890
    @appophiss3890 5 лет назад +16

    woudln't it work if he just calls min_coins with the whole coins array , then with coins[1:] then coins [2:]... and compare those ?

    • @whoami......
      @whoami...... 5 лет назад

      exactly what I just wondered

    • @mattbillenstein
      @mattbillenstein 5 лет назад

      Nah, like 55 cents is 25*2 + 5*1 (7 coins) or 25*1 + 10*3 (4 coins) -- I made that mistake first attempt.

    • @krnrrr
      @krnrrr 4 года назад

      @@mattbillenstein but 25*2 + 5*1 makes 3 coins
      you definitely meant 25*2 + 1*5

  • @jcrawlox109
    @jcrawlox109 5 лет назад +1

    First few days learning python, this was a fun challenge:
    money = 123 #variable to calculate coins
    quarter = 0
    dime = 0
    nickel = 0
    penny = 0
    x = money
    while x > 0:
    if x >= 25:
    x = x - 25
    quarter = quarter + 1
    if x < 25 and x >= 10:
    x = x - 10
    dime = dime + 1
    if x < 10 and x >= 5:
    x = x - 5
    nickel = nickel + 1
    if x < 5 and x >= 1:
    x = x - 1
    penny = penny + 1
    print("penny: ")
    print(penny)
    print("nickel: ")
    print(nickel)
    print("dime: ")
    print(dime)
    print("quarter: ")
    print(quarter)

    • @countablyinfinite4904
      @countablyinfinite4904 5 лет назад +1

      Could make better by print(“penny”, penny, sep = “:”) ...
      And also put try block before while loop and except ValueError

    • @jcrawlox109
      @jcrawlox109 5 лет назад

      @@countablyinfinite4904 Once I figure out what those are/do I'll give it a shot, thanks.

  • @chuckr6534
    @chuckr6534 4 года назад +2

    His algorithm doesn't work for values higher than 34 (e.g. it returns 2 for any value between 35 and 44). Does anyone know why?

    • @faaizqadri5316
      @faaizqadri5316 4 года назад

      true, the second function is not correct.

  • @MrRyanroberson1
    @MrRyanroberson1 5 лет назад +1

    34:50 you are incorrect. 55 cents can be best represented as one quarter and three dimes, as opposed to the otherwise used two quarters and five pennies. The minimum modularity of that system is 100, and cannot be reduced. all odd numbers of nickels (greater than 4 mod 10) above 25 cents *must* be represented with an odd number of quarters

    • @johnjohnson1514
      @johnjohnson1514 5 лет назад

      nerd

    • @FIRElover343
      @FIRElover343 5 лет назад

      Or 2 quarters and 1 nickel, if a nickel were available as opposed to [1, 10, 25]. found my own solution attempt doesn't match this and now I need to figure it out... It returns a coin count of 7, which would be 2x25c and 5x1c :/

    • @MrRyanroberson1
      @MrRyanroberson1 5 лет назад

      @@FIRElover343 the point is actually that at this point nickels are forbidden, otherwise the greedy (take biggest coins first) algorithm works best in all cases. yeah, it's an interesting problem, especially with the interviewer's assumption (that because the least common multiple is 50 that you only need to consider cases below 50) being wrong

  • @ryansadventuresontheintern7967
    @ryansadventuresontheintern7967 4 года назад +1

    The correct relation is
    # D[i] minimum number of coins needed to sum to amount i

    # D[0] = 0
    # for c in change
    # D[i] = min(D[i], D[i-c] + 1)

  • @hazeljoy1
    @hazeljoy1 5 лет назад

    A lot of people in the comments (as well as the original interviewee) are seeming to have trouble getting all of the edge cases for all possible coin sets. Here is one (python 3) solution that will give you the correct number of coins for any value and coin set
    from itertools import combinations_with_replacement as cwr
    def minCoins(value, coins):
    if value < 1:
    return 0
    i=1
    while True:
    options = [x for x in list(cwr(coins, i)) if sum(x)==value]
    if len(options):
    return len(options[0])
    else:
    i += 1
    value = 55
    coins = [1,10,25]
    print(minCoins(value, coins))

  • @altaccount648
    @altaccount648 5 лет назад +8

    I just think to do the challenge first, then go on thinking about how to improve it.
    I feel like I might not get a job with this thinking...

    • @anthonybrigante9087
      @anthonybrigante9087 5 лет назад +2

      Purfle No - this is the right way to solve a problem. Trying to write the best solution first will more often then not leave you with no solution.

    • @altaccount648
      @altaccount648 5 лет назад +1

      @@anthonybrigante9087 But won't I get called inefficient?

  • @UnbenutzerKanalname
    @UnbenutzerKanalname 5 лет назад +3

    Why use loops or dynamic programming at all for this issue?
    def num_coins(change):
    quarters = change // 25
    dimes = change % 25 // 10
    nickels = change % 25 % 10 // 5
    return quarters + dimes + nickels + change - 25 * quarters - 10 * dimes - 5 * nickels
    Then it can be simplified even more:
    def num_coins(change):
    return change - 24 * (change // 25) - 9 * (change % 25 // 10) - 4 * (change % 25 % 10 // 5)

    • @nicolasgalindo2199
      @nicolasgalindo2199 5 лет назад +2

      If the coins are of different values then you need a knapsack to calculate the optimal solution (The least amount of coins you need to return).

  • @swim3936
    @swim3936 5 лет назад +5

    Love these videos for the coding challenge! I've done my version in Haskell, since I'm not really proficient at Python, yet.
    To get the number of coins without nickels for x cents, you would run "coinnumber $ nonickels $ change x".
    data Change = Change {quarters :: Int, dimes :: Int , nickels :: Int , cents :: Int} deriving (Show)
    coinnumber xs@(Change a b c d) = a + b + c + d
    change x = change' x (Change 0 0 0 0)
    where change' x xs@(Change a b c d)
    | (x >= 25) = change' (mod x 25) (Change (a + (quot x 25)) b c d)
    | (x >= 10) = change' (mod x 10) (Change a (b + (quot x 10)) c d)
    | (x >= 5) = change' (mod x 5) (Change a b (c + (quot x 5)) d)
    | (x >= 1) = change' (mod x 1) (Change a b c (d + (quot x 1)))
    | otherwise = xs
    nonickels xs@(Change a b c d)
    | nickels xs == 0 = xs
    | quarters xs >= 1 = Change (a-1) (b+3) (c-1) d
    | otherwise = Change a b (c-1) (d+5)

  • @XmachiekX
    @XmachiekX 5 лет назад

    so i am kinda new to programming and before he started the 2nd "test" i stopped the video and did this:
    def num_coins (x):
    o=x
    l=[]
    coins = [25,10,5,1]
    for i in coins:
    h=0
    for coin in coins:
    h += x / coin
    h = int(h)
    x = x % coin
    if x == 0:
    break
    coins += [coins.pop(0)]
    l.append(h)
    x=o
    print("result is:",min(l))
    co = input("how many cents do you need?")
    num_coins(int(co))
    and i wanted to know if its fine and if i could improve it somehow?

  • @thesunilvarma
    @thesunilvarma 5 лет назад +30

    2017 ? Uploaded in 2019 !!!

  • @robbieskonieczny9464
    @robbieskonieczny9464 5 лет назад

    Quick question, is this a good solution to the first question?
    def num_coins(cents):
    coin_count = 0
    coins = [25, 10 , 5, 1]
    for coin in coins:
    if int(cents / coin) > 0:
    coin_count += int(cents / coin)
    cents -= coin * (int(cents / coin))
    return coin_count
    print(num_coins(4))

    • @jamshidyerzakov4942
      @jamshidyerzakov4942 5 лет назад

      it's not obligately to put int() everywhere, generally your code is almost the same as interviewee

  • @BenMartinStudios
    @BenMartinStudios 5 лет назад

    The lcm of (25, 10, 5, 1) is 50, but the initial greedy implementation shows that the shortcut value could lowered to 25. Why does adding the 5 back lower the shortcut if it doesn't affect the lcm?

  • @beeris
    @beeris 5 лет назад +1

    I'm at 16:11 - isn't the solution is to modulo from the smaller coin to the largest. It's not an optimization problem since it has algorithmic solution.

  • @WisdomofHal
    @WisdomofHal 5 лет назад +6

    Is this coin problem a typical interview question for python devs? When I began learning about python I remember this was one of the beginning problems and 1 of 5 of the first algorithms I learned. This video is awesome.

    • @WisdomofHal
      @WisdomofHal 5 лет назад

      John Brocksman That’s true. I’m still learning a lot and have a very long way to go

  • @deeplearningbro
    @deeplearningbro 5 лет назад +16

    Thank you for sharing the interview.

  • @Skullbash258
    @Skullbash258 5 лет назад +3

    For the second part, I don't know what type of solution this is but this is what I came up with. Not sure if this is the best solution so lemme know if I screwed up.
    If the cent total is over 50, then there is at least one quarter in the optimal solution. Subtract 25 and then look at the total again. If it's still over 50 subtract 25 until it isn't.
    Then, if the cent total is less than 50 but greater than 29, there is at least one dime in the optimal solution. Keep subtracting 10 and adding a dime to the coin count until you're under 29.
    Then finally once you're under or equal to 29 the greedy algorithm should take care of the rest.

  • @betterthanyou1558
    @betterthanyou1558 4 года назад +1

    i am a beginner and was trying this... is this correct?
    def num_coins(x):
    answers = []
    coins = [25, 10, 1] #or any coins acc. to the situation
    for i in range(0, len(coins)):
    cents = x
    answer = 0
    for coin in coins[i : ]:
    answer += cents // coin
    cents = cents % coin
    answers.append(answer)
    return min(answers)

  • @coletivating
    @coletivating 5 лет назад

    Simple Example including print out.
    def numCoins(chnageAmount):
    coins = [25, 10, 5, 1]
    numCoins = 0
    for i in range(len(coins)):
    numCoins = (int)(chnageAmount / coins[i])
    chnageAmount -= numCoins * coins[i]
    if (numCoins > 0):
    print("Give a", coins[i], "-->", numCoins, "times")

  • @uladzimiryankouski6464
    @uladzimiryankouski6464 5 лет назад +3

    actually, min_coins_dp does not work

  • @user-cj3yu9nv1u
    @user-cj3yu9nv1u 5 лет назад +1

    A solid question. I solved it in another way, and it was a really fun process.

  • @palrob1714
    @palrob1714 5 лет назад +34

    Thanks for sharing those interviews.

  • @__mango
    @__mango 5 лет назад +2

    Where are the tests at?

  • @iGladyator
    @iGladyator 4 года назад

    def num_coins(cents):
    coins = [25, 10, 5, 1]
    count = 0
    for coin in coins:
    while cents >= coin:
    cents = cents - coin
    count = count + 1
    return count
    print(num_coins(26))
    will this solution work as well?

  • @BeSomeoneCool
    @BeSomeoneCool 5 лет назад +4

    Tried to keep it simple for the 2d case (I am not a dev, have no knowledge in Python, was just curious)
    def my_test_coin(coins):
    myset = [25, 10, 5, 1]
    number_of_coins = 0
    left = coins
    for i in range(len(myset)):
    if left - myset[i] < 0:
    i+=1
    while left - myset[i] >= 0:
    left = left - myset[i]
    number_of_coins += 1
    print "Give " + str(number_of_coins) + " coin of " + str(myset[i])
    number_of_coins = 0
    if left == 0:
    break

    • @moonkake2838
      @moonkake2838 5 лет назад +1

      im also a beginner at python, but i think the for loop part could be shortened
      maybe u could do it like this:
      for i in myset:
      because from what i see in your code, the index of your list isnt really used individually apart from indexing myset
      so if you use for i in myset:
      if left - myset[i] < 0:
      could be
      if left - i < 0:
      hopefully i helped
      and also in python 3 the print function can be used as follows:
      print('Give', number_of_coins,'coin of', myset[i])

    • @nintendu64
      @nintendu64 5 лет назад

      def make_change(denominations, change):
      result = []
      for coin in denominations:
      result.append([coin, math.floor(change / coin)])
      change = change % coin
      return result
      change = make_change([25, 5, 1], 67)
      [print(x) for x in change]

  • @syedabdulrahmans3357
    @syedabdulrahmans3357 4 года назад +1

    def coins_count(amount):
    mylist = {}
    if amount > 25:
    mylist.setdefault("quater",(amount//25))
    amount = amount - (mylist["quater"] * 25)
    if amount > 5:
    mylist.setdefault("nickel",(amount//5))
    amount = amount - (mylist["nickel"] * 5)
    mylist.setdefault("pennies",amount)
    return(mylist)

  • @leoli4960
    @leoli4960 5 лет назад

    def num_coin(cents):
    num_quarter = cents//25
    remain_after_quarter = cents % 25
    num_dime = remain_after_quarter//10
    remain_for_nickel = remain_after_quarter % 10
    num_nickel = remain_for_nickel // 5
    num_cent = remain_for_nickel % 5
    print("The number of quarter is {}, the number of dime is {}, the number of nickel is {}, the number of penny is {}.".format(num_quarter, num_dime, num_nickel, num_cent) )

  • @bytefoundry8702
    @bytefoundry8702 5 лет назад

    If your given the total cents why not just mod each denomination from 25-> 1 to get the count. After each mod subtract that number of coins * denomination from cents.

  • @DanielUranga
    @DanielUranga 5 лет назад +33

    This is a classic "Knapsack problem".

    • @ItsAllEnzynes
      @ItsAllEnzynes 5 лет назад +2

      This is not the knapsack problem. Items in the knapsack problem have a weight and a value. In this problem the items only have a value.
      It’s a similar problem, but with regard to computational complexity, the actual napsack problem is non-polynomial while the complexity of this problem is polynomial.
      That said you could still solve it using any algorithm that solves the unbound knapsack problem by making the values equal the weights for the items, but I don’t know what the solve time would be with that methodology.

    • @ryansadventuresontheintern7967
      @ryansadventuresontheintern7967 4 года назад +1

      @@ItsAllEnzynes pseudo polynomial*

  • @grainfrizz
    @grainfrizz 5 лет назад +29

    I'm freaking out

  • @yesil1026
    @yesil1026 5 лет назад

    The reason for 50 is that it is the least common multiple of 10 and 25. So min_coins_dp(x + 50) = min_coins_dp(x) + 2

  • @ScytherDOTA
    @ScytherDOTA 5 лет назад

    My solution to the 2nd question via holding a register inventory in an array.
    def min_coins_dp(cash):
    if cash < 1: return 0;
    checkCoinIfEnough = 0
    num_of_coins = 0
    coins = [25,10,5,1]
    coin_inventory = [1,1,2,4]
    sum = 0
    for x,y in zip(coins,coin_inventory):
    sum += x*y

    if sum < cash:
    print 'Sorry, dont have enough changes. I only got :', sum ,'in total.'
    exit(0)
    for i in range(len(coins)):
    print('cash:',cash)
    print(coin_inventory)
    checkCoinIfEnough = 0
    if( coin_inventory[i] > 0 ) :
    checkCoinIfEnough += cash / coins[i]
    if (checkCoinIfEnough

  • @MrRyanroberson1
    @MrRyanroberson1 5 лет назад

    my approach was more like "let's first look at what these non-greedy cases look like" and find a pattern between two scenarios: an odd number of nickels, and an even number. for even, first split it into dimes. for odd, subtract a quarter and then split it into dimes. Five dimes makes two quarters, and then resolve some rounding issues for values below 25 (where subtracting a quarter is a problem)

    • @MrRyanroberson1
      @MrRyanroberson1 5 лет назад

      32:40 when you mentioned that, i wrote: (dollars,nickels) = divmod(nickels,20) into the program, with the later option of adding dollars as fours of quarters.

  • @siddhantjain7374
    @siddhantjain7374 5 лет назад

    The LCM of [25, 10, 5, 1] is 50, but it's always optimal to use quarters over 25. So how does LCM make sense in this case? Or does the LCM just give you a guaranteed bound, but perhaps not the lowest bound?

    • @evader110
      @evader110 5 лет назад

      With that set of currency, the greedy algo will always work. When the currency changes to [25,10,1], or no nickels, after 25 doesn't always work. See the example of 31 cents.

    • @kezar52
      @kezar52 3 года назад

      Actually for [25, 10, 1], 50 is not the magic number tho... We can easily try 55. 55 = 25*2 + 1*5 -> we need 7 coins. However, the optimal is 4, where 55 = 25*1 + 10*3. Am I missing something?

  • @TheRijintube
    @TheRijintube 5 лет назад +1

    I feel like he was overcomplicating, but I feel like this is all what he was asking for:
    def nc(c):
    q, rem = c // 25, c % 25
    n, rem = rem // 5, rem % 5
    p = rem
    return sum([q, n, p])

    • @diamartin6865
      @diamartin6865 4 года назад

      yeah exactly, but you also should include dimes so
      def num_coins(cents):
      quarters, rem = cents // 25, cents % 25
      dimes, rem = rem //10, rem % 10
      nickels, rem = rem // 5, rem % 5
      pennies = rem
      return sum([quarters, dimes, nickels, pennies])
      print(num_coins(10))
      would work out just fine

  • @masteryehudi7031
    @masteryehudi7031 5 лет назад +1

    Why doesn't the first problem require floor division (double slash) rather than normal division? Wouldn't he end up with decimal points?

    • @DD-pz8sp
      @DD-pz8sp 5 лет назад

      I'd like to know that as well

    • @GrzesiuG44
      @GrzesiuG44 5 лет назад

      @@DD-pz8sp In Python 2 division behaved in a same way as in all most popular, compilable languages: when arguments both were integers it was whole division by default.

  • @connorwilson8450
    @connorwilson8450 5 лет назад +4

    Yikes. This interview turned into a lesson real quick.

  • @GG-pv9cn
    @GG-pv9cn 5 лет назад +4

    Below is my solution. It's a bit verbose because I implement some extra features and make comments.
    In addition to returning the minimum number of coins used, it returns how many of each type are used, and it also considers that the coins in the register to make the change are limited. For example, if the change is 50 cents and I only have 1 quarter, the change will be 1 quarter, 2 dimes, 1 nickel, 4 coins total.
    The trick I used to determine the minimum number was this:
    1. Start greedy algorithm to get num_coins starting by taking the biggest possible chunk out (largest coin value)
    2. Start greedy n algorithm to get num_coins starting by taking the 2nd largest possible chunk (2nd largest coin value)
    3. Repeat for each item in the coin value list
    4. Take the minimum returned coin count from steps 1-3.
    In the example of calculating 31 cents with just quarters, dimes, and pennies (no nickels):
    First loop will use coin values: 25 1 1 1 1 1 1, 7 coins
    Second loop will skip 25 and use coin values: 10 10 10 1, 4 coins
    Last is just pennies so 31 pennies. 31 coins
    Minimum value is 4, so that is what's returned along with which coins are used.
    It does several things: 1) calculates minimum number of coins used to make a value of change, 2) returns a dictionary of counts of each coin used to make that value of change, and 2) returns a dictionary of how coin counts for each type remaining in the register.
    # given a starting index for the top-down algorithm and register coin counts.
    # returns: number of coins used, counts of each coin type used, counts of each coin type remaining in register
    def coins(change, coin_vals=[25, 10, 5, 1], i=0, r={25:100, 10:100, 5:100, 1:100}):
    if change 0:
    # find maximum coin value that is less than remaining change
    while change < coin_vals[i]:
    i+=1
    # if we don't have that coin, go to the next one
    while register[coin_vals[i]] == 0:
    # if we're checking pennies at this point and have none, change cannot be made.
    if coin_vals[i] == 1:
    print('Error: out of change, change cannot be made')
    return -1
    i+=1
    # reduce change by that value
    change -= coin_vals[i]
    # reduce count of this coin in register
    register[coin_vals[i]] -= 1
    num_coins += 1
    change_coins[coin_vals[i]] += 1
    return num_coins, change_coins, register
    # returns lowest possible number of coins used to give a certain value of change, given coin denomination (sorted high-low), and a count of each coin type in a register
    def min_coins(change):
    # coins we're using
    coin_vals = [25, 10, 5, 1]
    # coins we have
    register = {25:100, 10:100, 5:100, 1:100}
    assert [i in register for i in coin_vals] == [True]*len(coin_vals), 'Each item in coin_vals must appear in register'
    # a list of results (1 value for each starting index of coin_vals)
    results = [coins(change, coin_vals, i, register) for i in range(len(coin_vals))]
    num_coin_combos = [i[0] for i in results if i[0] > 0] # i[0] will be -1 if coins method encountered an error
    return results[num_coin_combos.index(min(num_coin_combos))]

    • @krnrrr
      @krnrrr 4 года назад

      that doesn't work for 55 when register is {25:100, 10:100, 5:0, 1:100}. the correct answer is {25: 1, 10: 3, 5: 0, 1: 0}

  • @Alva1326
    @Alva1326 5 лет назад

    I left it at min 23:15, but i have an question. In this kind of scenario is it acceptable to give a solution that is not maybe the faster one but it's simple and give the right result? for me looked like the person being interviewed is always trying to aim for the optimal solution first. and i was thinking "dude just iterate the coins array once, save num_of_coins into another array, and then iterate again the coins array but starting at the second position, and then iterate again but starting at the third and so on. By the end you return the minimum of your results array".
    Can someone give me some guidance?

    • @petertyldesley6542
      @petertyldesley6542 5 лет назад +1

      Personally, I think it's always better to get something that works first and then optimise after.

  • @skylarkenneth3784
    @skylarkenneth3784 5 лет назад

    The best i could think of with removing the nickels is to check if there is at least one occurrence of 1 quarter and at least 5 pennies. If that is the case, then return the answer - 3.

  • @yann5489
    @yann5489 5 лет назад +2

    Why this in python 2

  • @petro-大丈夫
    @petro-大丈夫 5 лет назад +2

    How is the first algorithm correct? That is not a greedy approach

  • @sharkkid100
    @sharkkid100 5 лет назад

    I dont know much about coding, but would dividing the total by the the largest coin and saving that value as an integer give you the amount of the largest coin reuiqred. Then you save the number as a double and then minus the double from the integer then times the value and repeat this process for each coin? So for example with 55 cents it would be 55/25 = 2 for the integer and 2.2 for the double. So you would need 2, 25 cent coins and then get 2.2 for the double then you repeat for each smaller coin?

    • @Erik-R
      @Erik-R 5 лет назад

      This is pretty close to what he did but I'm not sure what the double is for in your solution.

  • @matheuskuster2930
    @matheuskuster2930 5 лет назад +1

    My resolution for the second task:
    def minNumberOfCoins(target, coins=[1,10,25]):
    coins.sort(reverse = True)
    minFound = target
    for coin in coins:
    coinsArray = []
    if coin < target:
    coinsArray.append(coin)
    for coin in coins:
    while sum(coinsArray) < target and (sum(coinsArray) + coin) = minFound:
    return minFound
    minFound = len(coinsArray)
    return minFound
    print(minNumberOfCoins(31))
    print(minNumberOfCoins(70))

  • @f1uzz
    @f1uzz 5 лет назад

    Why not do it recursively?
    from enum import Enum
    class Coins(Enum):
    QUARTER = 25
    DIME = 10
    NICKEL = 5
    PENNY = 1
    def min_coins(cents):
    if cents == 0:
    return 0
    else:
    for coin in Coins:
    if coin.value

  • @rauljerlach4564
    @rauljerlach4564 5 лет назад +4

    (DISCLOSURE: I JUST PICKED CODING ABOUT 2 MONTHS AGO SO IT MIGHT NOT WORK WITH ALL CASES)
    So I'm pretty sure this code works for any set of given coins, and any given value for those coins, so it is supposed to work with lets say coins of 1, 2, 12, 16. The code is at the bottom, and before I will give a brief explanation of what I did. To get the smallest number you need to start by taking the smallest possible coin out supposing there is always a one, and continue doing that so for example in order to take 16 in change, before thinking of whether give them x amounts of dimes and x amount of nickels you must subtract the penny, this must be done while comparing one coin bigger than the one you are subtracting, lets say you must give out 10 cents, you will not start by subtracting a 5 and then another and give them 2 coins, because you can just give them one dime, so basically you are taking the smallest coin as long as you can not take the next in line. The code has some comments in there for you to read when pasting it at the app. sorry for my explanation, and I don't know the terms of dynamic programming, recursion and all that stuff so maybe my way of explaining comes a little strange this because my past is in math and physics (I'm a physics major), but the program should help making sense.
    P.S. I know maybe some steps might be unnecessary, if you see which please let me know.
    def min_coins(cents):
    # i started by making a blank list for the coins that will be used,
    # then asking the user to input the coins and append them to the list.
    coins = []
    ans = 1
    num_of_coins = 0
    while ans != 0:
    ans = int(input())
    if ans != 0:
    coins.append(ans)
    # first i checked if the amount of money is bigger than twice the biggest coin, if it
    # is bigger, then i added one coin of the biggest size, this helps with for example simplyfing a
    # 89 cents change to a 39 cent change,
    while cents >= (coins[-1] * 2):
    num_of_coins += 1
    cents -= coins[-1]
    # i quickly checked if the amount left is not a multiple of the biggest coin
    if cents % coins[-1] == 0:
    return cents / coins[-1]
    # i set up my counter and check if the amount to be given is divisible by the second smallest coin
    # and not divisible by the biggest coin. then do this with the following coins and rest the amount
    # needed from the cents and adding to the coin counter
    i = 1
    while i < len(coins):
    while cents % coins[i] !=0 and (cents % coins[-1] != 0):
    cents -= coins[i-1]
    num_of_coins += 1
    i += 1
    # finally i check if there is any residue that must be taken care of
    num_of_coins += int(cents / coins[-1])
    # return the answer
    return num_of_coins
    # testing the function
    print(min_coins(12))

    • @JkaBG
      @JkaBG 4 года назад

      When i tested your code with "31" it gave 4 (1+10+10+10 /4 coins), with a coin list [1,5,10,25]. Expected to give 3 (25+5+1 /3 coins)

  • @LimeWitness
    @LimeWitness 3 года назад

    I tried this myself and came up with this solution:
    def num_coins(cents):
    coins = [25, 10, 5, 1]
    num_of_coins = 0
    for x in coins:
    while cents >= x:
    cents -= x
    num_of_coins += 1
    return num_of_coins
    print(num_coins(31))
    Output: 3

  • @FIRElover343
    @FIRElover343 5 лет назад

    Before finishing the video I tried to take on the challenge as well...
    def min_c(target_change, c_inv=[1, 5, 10, 25]):
    num_c = 0
    c_inv.sort(reverse=True)
    for c in c_inv:
    if (target_change % c) == (target_change - c) and target_change - c > 0:
    if target_change - c < c_inv[c_inv.index(c) + (1 if c_inv.index(c) < len(c_inv) - 1 else 0)]:
    continue
    num_c += int(target_change / c)
    target_change %= c
    return num_c
    # Tests
    def main():
    print(min_c(50)) # 2
    print(min_c(50, [1, 5, 10])) # 5
    print(min_c(0)) # 0
    print(min_c(31, [1, 10, 25])) # 4
    print(min_c(49, [1, 10, 25])) # 7
    print(min_c(70, [1, 10, 25])) # 4
    print(min_c(55)) # 3
    print(min_c(100)) # 4
    if __name__ == "__main__":
    main()

    • @krnrrr
      @krnrrr 4 года назад

      try it with
      assert min_c(55, [1,10,25]) == 4

  • @ItsAllEnzynes
    @ItsAllEnzynes 5 лет назад +2

    Watching now... first algorithm was the way I would’ve done it.
    In the 2nd one with no dimes I know that mathematically the reason my other algorithm would no longer work is because 10 and 25 are both factors of 5, so when a number that is divisible by 5 I might be able to use dimes more effectively than quarters, so my revised algorithm is
    Count += change %5
    change -= count
    count += change/25
    change = change %25
    if count == 15: count += 3
    elif count == 10: count += 1
    elif count == 5: count += 2
    Return count
    There is probably an algorithm that I could use instead of hard coding, but why bother

    • @nr9131
      @nr9131 5 лет назад

      I thought he said had no nickles but I did similar to you. If ever get current_value ==5 then add +=1 to coins break out.
      For all values from 35, 45, etc. Only 55 can be solved with quarters and dimes so no worries there.
      Then only 1s between 6 and 9 will need to be considered for additional nickles so 6 will have same meaning as 56 etc.

    • @nr9131
      @nr9131 5 лет назад

      *Only 55 can't be solved

    • @nr9131
      @nr9131 5 лет назад

      Oh I fucked up. He wants min coins without nickle so like 30 would be (5) but with dimes (3).

  • @Marva123
    @Marva123 5 лет назад +2

    Both solutions require 'math.floor', you must first 'import math', then in first question put math.floor(cents/coin) on line 20, so floating point number isn't generated and causes an error. In second question you must use math.floor(i / j) on line 39, so floating point number isn't generated and error occur with index only being able to accept ints or splices

  • @typicalhog
    @typicalhog 5 лет назад +2

    I did it like this.
    def min_coins(cents, coins):
    coins_count = 0
    for coin in sorted(coins, reverse=True):
    coins_count += cents // coin
    cents -= coin * (cents // coin)
    if not cents:
    break
    return coins_count
    for i in range(1, 101):
    print(f'{i} cents : {min_coins(i, [1, 5, 10, 25])} coins')

    • @typicalhog
      @typicalhog 5 лет назад +7

      @@darkopz No, my line is in fact correct, that's how you print a "F"ormatted string in Python 3.

    • @SayandipDutta
      @SayandipDutta 5 лет назад +2

      These are called f-strings, introduced in Python 3. One of the best features imo

    • @GG-pv9cn
      @GG-pv9cn 5 лет назад +1

      Your method works to get the number of coins using a top-down approach, but does not actually return the minimum number of coins possible.
      If coins=[25, 10, 1], your method returns 7 (1 quarter + 6 pennies)
      But it should return 4 (3 dimes + 1 penny)

    • @typicalhog
      @typicalhog 5 лет назад

      @@GG-pv9cn True, good catch!

  • @sunnychandigarh2819
    @sunnychandigarh2819 4 года назад +1

    bedrag = int(input("Geef een bedrag dat je wil wisselen = "))
    biljetten = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    i = 0
    while bedrag >= 0.99:
    aantaal = 0
    while bedrag >= biljetten[i]:
    bedrag = bedrag - biljetten[i]
    aantaal += 1
    if aantaal >= 1:
    print(aantaal, "*", biljetten[i])
    else:
    pass
    i += 1
    this is the simplest solution

  • @makhus8337
    @makhus8337 3 года назад

    Is that okay for minimum number of ways to find, just sort the coins list and do the first operation mentioned in the video
    def num_coins(cents):
    if cents < 1:
    return 0
    coins = [25,2,4,10,5,1]
    coins.sort(reverse=True)
    num_of_coins = 0
    for coin in coins:
    num_of_coins += int(cents / coin)
    cents = cents % coin
    if cents == 0:
    break
    return num_of_coins
    print(num_coins(70))

  • @BlitzDjingga
    @BlitzDjingga 5 лет назад +7

    Is this for real ?
    Had to pause in the middle and really think how the minimal coins requirement different from the base /first question,
    And then it just make sense, but am not using dynamic programming mere loop of of coin array and function for the greedy algo

  • @garciajero
    @garciajero 5 лет назад

    this is my solution , python 3:
    def give_change(num):
    coins = [25, 10, 5, 1]
    cnt = []
    while num != 0:
    for c in coins:
    if int(num /c) > 0:
    for rr in range(0,int(num/c)):
    cnt.append(c)
    num = num % c
    else:
    pass
    return cnt

  • @borispsalman
    @borispsalman 5 лет назад +1

    The interviewer pointed out a few things but he was fine when the guy used len() function on integer number ? it works only with string, dict, list, tuple and set.

  • @AjayKumar-pg4jy
    @AjayKumar-pg4jy 4 года назад +1

    cents = 31
    denominations = [25,10,5,1]
    #Calc combination of denomination for every denomination
    def cash_calc(cents,denominations):
    num_coins = 0;
    coin_change = {};
    for each_coin in denominations:
    num_coins += cents // each_coin; # 31 / 25 = 1#
    #add a dict element for denom vs count of it.
    if (cents // each_coin):
    coin_change[each_coin] = cents // each_coin
    cents = cents % each_coin; # 31 % 25 = 6
    if (cents == 0):
    break;
    #Return final dict with all combination
    return coin_change;
    # Do this for every combination of denomination
    for each_denom in range(len(denominations)):
    print(cash_calc(cents,denominations[each_denom:]));

  • @yonghuawu2596
    @yonghuawu2596 5 лет назад

    The dynamic planning part is wrong, right? If you pass 56 to the min_coins_dp, it’s retuning 8 instead of 5

    • @samuelelliott4508
      @samuelelliott4508 5 лет назад

      Yes, it is wrong. You can hear that the interviewer had that intuition but didn't stumble upon an example like you have here. The correct way would be to imagine only using one coin of the given denomination, not using as many as possible.
      To fix it:
      [line 33]
      num_of_coins = [cents+1] * (cents+1)
      [line 38]
      for j in coins:
      temp = min(num_of_coins[i], 1 + num_of_coins[i - j])
      Note that this would require additional checks to avoid out of bounds errors when i < j, and I didn't include these here.

  • @jwwan5092
    @jwwan5092 5 лет назад

    Here is my solution for the 2nd part. I used dynamic programming because it is more optimal compared to the greedy approach.
    For example, 55 cents. The minimum number of coins is 4. (1 quarter + 3 dimes + 0 pennies = 4 coins)
    While, if we use the greedy approach (larger coin first), we will get 7 coins. (2 quarters + 0 dime + 5 pennies = 7 coins)
    So dp in this situation is more correct.
    Code:
    def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
    a, b = b, a % b
    return a

    def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
    def min_coins_dp(cents):
    coins = [25,10,1]
    coins_lcm= 1
    for i in coins:
    coins_lcm = lcm(coins_lcm ,i)
    temp=0
    while(cents>=coins_lcm):
    temp += 1
    cents -= max(coins)
    dp = [100000] * (cents + 1)
    dp[0] = 0
    for i in range(1, cents + 1):
    for j in coins:
    if(cents - j >= 0):
    dp[i] = min(dp[i], dp[i - j] + 1)
    return temp + dp[cents]
    print(min_coins_dp(55))

    • @DanishAnton
      @DanishAnton 5 лет назад +1

      So, I have minimal knowledge in python (I'm a C# / javascript programmer and can't even understand how your gcd function works) but I believe the following may have better performance
      def min_coins_dp(cents):
      if cents < 1:
      return 0
      coins = [25, 10, 1]
      min = cents
      for i in range(0, len(coins)):
      num_of_coins = 0
      for(k in range(i, len(coins)):
      num_of_coins += cents / coins
      cents = cents % coin_count_array
      if cents == 0
      break
      if min > num_of_coins:
      min = num_of_coins
      return min
      Didn't test it but it should have constant speed by the coin array length * (coin array length -1)

  • @joorkoor
    @joorkoor 5 лет назад

    Is it just me or was that min_coins_dp function incorrect. If you pass 66 into the function it'll return 3...

  • @SuperSoyajin
    @SuperSoyajin 5 лет назад

    The algorithm he has doesn't work for 80, where you want 2 quarters and 3 dimes to get a minimum of 5. His algorithm will consider 3 possibilities: [3 quarters and 5 pennies], [8 dimes], [80 pennies], resulting in an output of 8. The problem is fitting as many of each coin into the solution at once. Even though 3 quarters is less than 80 cents, and 8 dimes is exactly 80 cents, the optimal solution does not have either of these maximums. I'm surprised the interviewer did not catch this corner case.
    This problem persists even with the least common multiple optimization for cases like coins = [1, 5, 7, 11] and cents = 23. As long as the least common multiple is larger than 2x the largest coin, this problem can occur.

  • @ross951
    @ross951 Год назад

    def num_coins(cents):
    totals = []
    denominations = [25, 10, 5, 1]
    for i in range(len(denominations)):
    cents_orig = cents
    total = 0
    for denomination in denominations[i:]:
    coins = math.floor(cents_orig/denomination)
    cents_orig = cents_orig - (denomination * coins)
    total += coins
    totals.append(total)
    return sorted(totals)[0]

  • @Spinlayer
    @Spinlayer 5 лет назад +5

    Oh c'mon... I don't know why so much trouble. Sometimes the best option is to kick the vending machine to get your cashback!

  • @olicairns8971
    @olicairns8971 5 лет назад +4

    Cool question. My solution is below.
    def min_coins(change, coins):
    '''
    Args:
    change (int): Changed required (positive integer)
    coins (list): Value of coins available (all values are positive integer)
    Returns:
    min_val: Minimum possible coin number
    '''
    if change < min(coins) or change % 1 != 0 or min(coins) < 1:
    raise ValueError("Invalid input")
    # base case. Will always be optimal to return single coin
    elif change in coins:
    return 1
    # recursive. Calculate 1 + value for remainder for all possible coins, and return lowest val
    else:
    # temporary min_val, replaced by loop below
    min_val = change
    for coin in coins:
    if coin < change:
    cand_val = 1 + min_coins(change-coin, coins)
    min_val = min(min_val, cand_val)
    return min_val

    • @DAJakaRedAries
      @DAJakaRedAries 5 лет назад

      that's my try. Sorry if I misunderstood the task.
      def num_coins(amount, array):
      if amount < 0: return 0
      num = 0
      for i in sorted(array, reverse=True):
      num += amount // i
      amount = amount % i
      return num

    • @olicairns8971
      @olicairns8971 5 лет назад

      @@DAJakaRedAries That looks like an efficient greedy approach. I"m not sure it will give you the minimum value for every coin distribution. For example, I think it would return 49 for the coins [50,49,1], and target 98 (1 50 and 48 1s), while 2 49s is the minimum.

  • @Ronnie9P
    @Ronnie9P 4 года назад

    the solution to the first problem is briliant, i didn't think of that, but solution 2 is awfull, it can be easily done by this: you put a while loop in which after each complete for iteration, you remove the first element of counts, then you add into a list every num_of_coins, in the end, you just print the minimum of the list, which is 4 in that case, extremely easy.