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&
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.
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 :)
@@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.
@@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 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 :)
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 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
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.
@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.
@@pounet2 yeah theres simple algorithms which state that simplly going through decreasing quantities and checking which values fit is not the optimal solution.
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 ;)
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.
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.
@@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.
@@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.
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.
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.
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.
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
@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 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 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.
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
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.
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
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
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.
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.
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.
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.
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.
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))))
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
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
@@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)
@@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
@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
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
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".
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?
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.
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)
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
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 :/
@@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
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))
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)
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?
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))
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?
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.
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.
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.
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)
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
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])
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]
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) )
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.
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.
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
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)
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.
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?
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.
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?
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])
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
@@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.
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))]
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?
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.
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?
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))
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
(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))
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
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()
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
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.
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
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')
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)
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))
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
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
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.
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:]));
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.
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))
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)
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.
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
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
@@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.
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.
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&
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.
You should watch video where someone quit Google to become his own man.
This video is nothing.
@@norpriest521 Could you give an example? I would really like to see that!
@@michal304
Just search RUclips "Why I left Google"
You'll see so many videos about that 😂
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 :)
Python engineers are always cool.
Maybe it's because we are always being bullied for being pseudo code. :(
No.1 rule of coding in a team is;
Don't be smart. Keep it simple.
One of my professors said "never hire a programmer that uses recursion for !5" or something like that.
@@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.
@@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).
@@osquigene depends on the stack. If I was implementing this coin algorithm in elixir I would use recursion and it would be extremely efficient
@@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 :)
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
So everyone gets the job?
@@googleuser7771 you can still get to know skills of the interviewee anyways
@@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
True, he's patient and helping him out. Also getting him to talk so he can understand the interviewee's thought process.
@@googleuser7771 if you've ever interviewed you should be aware that interviewers aren't out to eat you. They're very professional and helpful.
"i don't think this is gonna give me the optimal solution"
"it will, in fact"
10/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.
@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.
@@pounet2 yeah theres simple algorithms which state that simplly going through decreasing quantities and checking which values fit is not the optimal solution.
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 ;)
I read this msg while the video played it lmao
These interviews are helping me focus on my own solutions while others talk about the same problem, thank you!
He was making it more complicated than it really was
Zeppelin waaaaaay more complicated
I think just divide it and find remainder should be an easier approach. But maybe his approach can be adapted to other currencies? idk.
Dude, took me like 10 line of codes and 3 min, if this is was real I'd hire myself haha
Antoine Parra same here, this was excruciating to watch
DIE HAPPY is it java?
That interviewer sounds like such a lovely person. I'm glad the interviewee eventually twigged he wanted to hear "Least Common Multiple".
Interviewer: hello, thank y-
Me: ok so "Hello world"
LOL
@@fraydizs7302 print("not hello to covid lol,)
WHo ever created this webpage/channel, its a genius! thanks for sharing, will checkout the website later!
It was 68 but I added my like. You're welcome.
@@evelynrthomas9982 Nice! :D
I don't like odd numbers, so made it 90 likes
@@BsiennKhan i helped you out there because it was stingy 93
Interviewee: "I don't know why this is happening"
Interviewer: "I don't know why this is happening"
I would say rather than thinking about optimal solution straight off the bat go for actually solving the problem and then optimize your solution.
Agreed
@@thecodingfoundation
Nah
@@norpriest521 ok
in many cases optimizing requires a completely different approach to the problem, for example when you want to achieve better
computational complexity
@@michak1456 yeah but first priority should be creating something that works, then optimize after.
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.
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.
That's a great point
Writing a novel has absolutely nothing to do with programming. Extremely bad analogy I'm sorry.
@@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.
@@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.
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.
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)
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.
The difficulty of the problem went from 0-100 real quick.
The solution for 55 is 4 not 5.
The correct answer for 55 is 3: 2x25 and 1x5 (2 quarters and 1 nickel)
Matis Matis incorrect. There are no nickles.
@@benbishop7512 yeah you're right, it's a typo in my answer, 3 dimes and 1 quarter so 4 coins.
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.
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
@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.
@@DestinyIsDecided Try 55
@@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
@@DestinyIsDecided That's where you're wrong. 55 can be made with 1x25 + 3x10, meaning only 4 coins.
@@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.
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
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.
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
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)
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
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.
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.
Sounds like the same guy from Google again
I have no clue how to approach any of these problems... but im still watching lol
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.
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.
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]))
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.
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))))
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
google wants to know ur location !!!
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
@@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)
@@neerajraut6473 also in python 3 you have to use int(cents/coin) to get the correct answer
@@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
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
Yeah, that's my solution too.
that's so beautiful...
Worst solution, imagine that you have 99999999 coins, You would have to plus the coins millions of times.
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
@@jackfinan9060 Why would you post a worse solution under a good one?
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
exactly ... way simpler
smart
thankyouu
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)
@@andrewisaac1061 yea, it won't :(
it's all about modulus
@SatansFlipFlopgo get that bag
@@Anequit plipplop
@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
@@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.
@SatansFlipFlop this one doesn't handle the second question right?
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
If you would convert everything to the same unit, wouldn't you be able to do this using modulo?
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".
What was in the google doc?
Bapt Iste A problem on how to traverse the DOM with a function that received a node and a callback
@@Pulits Oh I see! Thank you
Did u pass that interview and are you still in the hiring process? Best of luck to you
@@srt-fw8nh Google exists, use it.
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?
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.
@@mohithm.p6091 Ahhh got it
This is much easier than what he made it out to be
So far all the ppl in the comments that posted the solution thinking they got it rights were wrong
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 ?
exactly what I just wondered
Nah, like 55 cents is 25*2 + 5*1 (7 coins) or 25*1 + 10*3 (4 coins) -- I made that mistake first attempt.
@@mattbillenstein but 25*2 + 5*1 makes 3 coins
you definitely meant 25*2 + 1*5
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)
Could make better by print(“penny”, penny, sep = “:”) ...
And also put try block before while loop and except ValueError
@@countablyinfinite4904 Once I figure out what those are/do I'll give it a shot, thanks.
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?
true, the second function is not correct.
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
nerd
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 :/
@@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
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)
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))
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...
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.
@@anthonybrigante9087 But won't I get called inefficient?
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)
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).
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)
wtf is Haskell
@Caesar xd
@@xxoan.1613 Google exists.
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?
2017 ? Uploaded in 2019 !!!
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))
it's not obligately to put int() everywhere, generally your code is almost the same as interviewee
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?
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.
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.
John Brocksman That’s true. I’m still learning a lot and have a very long way to go
Thank you for sharing the interview.
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.
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)
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")
actually, min_coins_dp does not work
A solid question. I solved it in another way, and it was a really fun process.
Thanks for sharing those interviews.
Where are the tests at?
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?
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
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])
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]
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)
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) )
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.
This is a classic "Knapsack problem".
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.
@@ItsAllEnzynes pseudo polynomial*
I'm freaking out
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
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
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)
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.
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?
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.
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?
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])
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
Why doesn't the first problem require floor division (double slash) rather than normal division? Wouldn't he end up with decimal points?
I'd like to know that as well
@@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.
Yikes. This interview turned into a lesson real quick.
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))]
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}
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?
Personally, I think it's always better to get something that works first and then optimise after.
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.
Why this in python 2
How is the first algorithm correct? That is not a greedy approach
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?
This is pretty close to what he did but I'm not sure what the double is for in your solution.
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))
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
(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))
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)
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
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()
try it with
assert min_c(55, [1,10,25]) == 4
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
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.
*Only 55 can't be solved
Oh I fucked up. He wants min coins without nickle so like 30 would be (5) but with dimes (3).
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
We can use also round(cents/coin), can't we?
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')
@@darkopz No, my line is in fact correct, that's how you print a "F"ormatted string in Python 3.
These are called f-strings, introduced in Python 3. One of the best features imo
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)
@@GG-pv9cn True, good catch!
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
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))
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
That makes cents
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
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.
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:]));
The dynamic planning part is wrong, right? If you pass 56 to the min_coins_dp, it’s retuning 8 instead of 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.
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))
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)
Is it just me or was that min_coins_dp function incorrect. If you pass 66 into the function it'll return 3...
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.
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]
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!
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
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
@@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.
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.