Coin Change Problem (Python)

Watch someone try to solve the coin change problem in a mock interview with a Google engineer. Explore this problem and others in the world's largest library of interview recordings.

Interview Summary

Problem type

Coin change

Interview question

1) Given a value, return the optimal number of coins [1,5,10,25] to make the value. 2) Given a value and a set of coins, return the optimal count of coins to achieve the value

Interview Feedback

Feedback about Festive Samurai (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

You did really well, especially since you said this was your first time. It was great that you came up with a running solution to the simple first iteration right away, and then were able to get the more advanced iteration running as well. The only suggestion I would have would be to have a solid understanding of the approach you're going to use before starting to code -- for the second one, you needed to backtrack a little after the coding started. But overall, well done.

Feedback about Intergalactic Avenger (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

He was a great interviewer. Helped me out well when I got stuck and paced the interview well as well.

Interview Transcript

Intergalactic Avenger: Hello

Festive Samurai: Hey

Intergalactic Avenger: Hi, how's it going?

Festive Samurai: Good, how are you?

Intergalactic Avenger: Doing good. Are you familiar with the platform and how it works?

Festive Samurai: This is my first time but I know this particular console.

Intergalactic Avenger: CoderPad? Yeah, okay. Excellent, so then shouldn't be too hard to just get started. I'm just going to ask a couple technical coding challenges and then at the end if you have any questions for me, you can ask me then. I'll give some feedback about how it went on the platform and so forth. Yeah, we can just get started if you're ready.

Festive Samurai: Sure.

Intergalactic Avenger: Alright, so today we're going to be kicking it old school and we're going to be making change. Like in a cash register.

Festive Samurai: Okay.

Intergalactic Avenger: So. we'll start with the basic idea and we'll sort of build up on it. Let's just say that you're a cash register software and you need to find how many coins you're going to give back as change. And for example, if you know you need to give 33 cents back in change, you know that you'll give one quarter, one nickel, and three pennies. So that make sense in terms of what the overall structure is?

Festive Samurai: Oh yeah, so nickel is 5 cents? I forgot actually.

Intergalactic Avenger: Oh yeah, no problem, yeah.

Festive Samurai: And a quarter is a?

Intergalactic Avenger: So this is like 25 cents.

Festive Samurai: Oh a dime, I was thinking of dime. Dime is 10 okay.

Intergalactic Avenger: So then this is also... Pennies are 1 and then there's also dimes and stuff. So let's start by just... We're just gonna start by figuring out what the actual number is. So, there'll be some kind of number of cents. And then, you will return the number of coins it would take. So, in the example above, the answer would be... So like, num_coins 33 is going to be 5.

Festive Samurai: Yeah, okay. I mean the first thing that came to my mind was basically since it's 33, so like take the highest value coin, that's 25, and then see how many times that goes. And then go to the next biggest number, and then go according to the rest. I'm not sure if that will actually give me the optimal solution is what I'm trying to think.

Intergalactic Avenger: Okay.

Festive Samurai: But, I'm trying to think if it'll give me the optimal solution.

Intergalactic Avenger: It will in fact.

Festive Samurai: Okay.

Intergalactic Avenger: I'm just going to change the number for one second. And then, this is just going to be.

Festive Samurai: Okay, so yeah, that's what I was thinking. Okay, that makes it easier. I could just write mod then. Oh, so the mod will give me the remainder of cents. And when the remainder becomes 0, that means we have gotten to it. And by division, we can get the number of coins for that particular amount. So basically, I have my coins equal to... I'm going to make a list here. Basically like, 25, 10, 5, and 1. And then go while True and I might have to change the loop, but I'm just trying with while True. And since... number_of_coins = 0. And now, I can do number_of_coins += cents. Mod that cents by coin in coins I guess. And cents = cents / coin . Then return. Oh sorry, just for sanity check and housekeeping, if cents < 1: return 0. And then return number of coins, I guess. Let me double check. I could also do, if cents == 0: break. Sorry, I think I'm mistaking. Because if it's 25, cents / 25 is 1, which is not right. I'm just using one coin, so that should just go away. I'm missing something here. Something simple. number_of_coins = 25 / 25. Oh wait, I have... Yeah, that makes sense.

Intergalactic Avenger: Mhm. Okay, looks good. Let's just write a little test case here. Let's see how it goes. Alright, so we're going to see what happens.

Festive Samurai: I'm gonna comment this out.

Intergalactic Avenger: Oh yeah, yeah, yeah. That's a good idea.

Festive Samurai: Oh, of course.

Intergalactic Avenger: Okay, perfect. Alright, and what's the runtime of this algorithm?

Festive Samurai: Runtime is the number of coins, so 4, which is constant.

Intergalactic Avenger: Constant. Okay, excellent. Alright, so you're basically taking advantage of the fact that the greedy algorithm is correct for this set of coins. So you go and you greedily decide how many quarters you need. And then dimes. And then nickles. And then pennies. And that gives you the correct answer. Now, what if I mix it up a little bit and I say you don't get any nickels. Your cash register has run out of nickels. So you only have coins worth 1, 10, and 25. So, the algorithm that you wrote, in this case is going to give you 7 because it's going to be one quarter and 6 pennies.

Festive Samurai: Right.

Intergalactic Avenger: Whereas, the real answer, which is 4.

Festive Samurai: Minimizing the coins.

Intergalactic Avenger: 3 dimes, and 1 penny.

Festive Samurai: Okay.

Intergalactic Avenger: So, can you rewrite this so that it will work when you're machine has run out of nickels?

Festive Samurai: Okay, wait so do we just need to make it work when it runs out of nickels, or do we have to minimize the number of coins?

Intergalactic Avenger: Oh, you want to minimize the number of coins. I guess I should really be calling this min_coins(cents). I was kind of figuring, as a cash register, you're not trying to give people hundreds of pennies. You're trying to give people a reasonable amount of change.

Festive Samurai: Right, right. That makes me think that we have to do some sort of min. Okay so, basically I have to do something like: If I'm using 25, what's the number of coins I get. And what's the number of coins I get if I don't use 25. So, it's kind of like a dynamic programming solution, I feel.

Intergalactic Avenger: Yeah, makes sense.

Festive Samurai: So, basically I have to include or not include and work with that. There could be a recursive way. Or I could have a table or array of the input basically. So for like 31, I build up to 31 starting from 0,1,2,3,4.

Intergalactic Avenger: Ah okay yeah, so it would be sort of like the definite proof of induction.

Festive Samurai: Induction, yeah.

Intergalactic Avenger: That's one way to do it for sure. Yeah you can just reuse the, or... Either way.

Festive Samurai: So basically, I'm going to initial number of coins basically. [0] * len(cents). Okay, I think I see what I have to do here. So basically, having 0 initialized for the fields, the indexes define the number of cents. So for the 0th index, I need 0 because 0 cents because there is nothing in there. Okay, so now I can go 1 cent in. Okay, so for i in range len plus one because the last one is not included in the range. So now I have each cent value. Now I have to go through each coin. For j in basically coins, so basically I have to do minimum of hmm. So I'm building from the first one. coins_j like I'm seeing how many coins I can take from this. So that would be i / j. That's the number of coins that I can use from j.

Intergalactic Avenger: So is the idea that you build up this table with cents. And at each cents interval, you're going to see.

Festive Samurai: The minimum number of coins that I need to build up to that cent number.

Intergalactic Avenger: Right. So then what's happening with the coins of j. What are you doing here? So, if coins is 25, then i divided by j is the number of coins that one denomination, that could get you to where you're going. But then, there's going to be a lot of rounding issues. So like, that's going to be 0 for the first 25. So yeah, I guess then...

Festive Samurai: Oh, right.

Intergalactic Avenger: I'm just curious as to what that number is going to represent.

Festive Samurai: So what I was thinking was basically: I'll calculate how many coins I can use from this denomination. And then what the remaining value that's left. And how many coins did we need to build up to that. So that's one value for. No, that doesn't make sense. Because getting from A to B, I might need to use multiple coins. So I'm building one by one. Coin from each coins. I have to build for that particular cell, and how do I do that with using all the coins?

Intergalactic Avenger: So you've definitely identified one correct solution, and you've identified that it's this dynamic programming idea with memoization. So let's just keep saying you do with this memoization. You're building up this table. In this case it's not two dimensional, it's just one dimensional. And how are you going to use that table as you are sort of building up the empty rows that you haven't calculated yet?

Festive Samurai: So basically for the entity value I'm looking at right now, I'm going to take... If I use 25 cents, how many quarters do I have to use. And then how many cents remain after using the quarters. And then, what was the minimum number of coins in that value.

Intergalactic Avenger: But does that look back into any of the previous values that you have filled in? It almost sounds like with that algorithm, you don't even need this outer loop. You just need to run something on that one number itself. Or do you go and look back on some of the cells that you've filled in before as kind of a hint for what the current cell is going to be.

Festive Samurai: Yeah, I mean I definitely look at the previous cells, right? So if I'm say at like 35. So I'm at 35 and I see that I can use 25 once, so I use 25 and check what the remaining value is, which is 10. And now, 10 needs only one dime. So I check it directly for the cell that I've filled for 10, which will say 1. And then, I use 1 + 1 that I've gotten now, so that's 2 - that's minimum.

Intergalactic Avenger: I think I understand what's going on. So, you've got some values that are filled in. So I'll just fill in a couple. So this the number, and then this is going to be the minimum number of coins. Right, so 5 is just 1 because it's a nickel. Oh wait, we don't have nickels. I'm starting to get the idea. Okay so, here you are at 35. And then how are you filling in 35?

Festive Samurai: So that would be 2. And then how I come to that will be somehow I will do a minimum of something. I'm trying to think how I would do that. And, basically when I'm at 35, I'm going to check for the first coin that is 25, and I can see I can use that once. Now the remaining value is 10. And then 10 would have been over here with 1. So I'll just use 1 from the 25 and then I'll check what the remaining value form 35 is. That's 10. And 10 required only 1 coin, so that's 2. So I would save 2 and then I will go for the next coin - 10. And 10 will fit 3 times, so I check 3 plus the number of coins used in 5, which would be 5. So 3 + 5 is 8. And then I would check if I used just one.

Intergalactic Avenger: Okay, yeah, I see. That makes sense.

Festive Samurai: Yeah, but I'm not sure that's the right way to do it... Maybe that is the right way.

Intergalactic Avenger: I definitely think it's the right approach. It's definitely the right way of thinking about it. But I think if you code it up, it will become a little clearer. Or if you can maybe... That's sort of a weird thing to say. It's hard to code something up if you don't have the idea of exactly what you want it to do. But like, 35 was an interesting one because it started off sort of the right way. But let's look at 30. Let's look at how 30 is going to work.

Festive Samurai: So for 30, I'll use 25 first. So 25 gets me one coin. And then I'll check for how many coins were used in 5. Now, 25 is a 1 and then 5, so like 6 coins. So I'll keep six in my hand. And now I use 10, and 10 gives me 3 coins, so that becomes my current minimum.

Intergalactic Avenger: So walk me through how you get 3 for 10.

Festive Samurai: So I'm using 10 now. So 10 goes 3 times into 30, so I use 3 coins. And 30 % 10 is 0. So there's number after.

Intergalactic Avenger: Ahhh, I see. Okay. Yeah, I think that'll work.

Festive Samurai: Yeah, but I'm not sure that's the ideal way. But I'll try this line and see what happens. So like, coins_j is equal to this. So actually, I think I'm doing the same thing again. coins_j is equal to this... I'm going to delete that, I'm just writing stuff that I think I might need.

Intergalactic Avenger: Actually, I just thought of an example that counters yours. Let's say we do 70.

Festive Samurai: So 70, I use 25. So I see I can use 2 coins. And then we have 20, which will be 2, because 10 gets you 2 coins. So that will get me 4.

Intergalactic Avenger: I see yea. Yeah, no okay, you're right.Yeah, I was thinking if you started with the 10, then you're going to get 7. But no, you've taken the 25 out first.

Festive Samurai: I mean, even if I use 10 first, I'm using the minimum basically.

Intergalactic Avenger: Yeah, and you definitely want to use the minimum. Okay, yeah, let's keep going with that then.

Festive Samurai: Okay, so coins_j is equal to i. This is the number of coins I can use for this. if coins_j != 0. Basically, min(temp, coins_j)... Sorry, can you give me one second. I'm confusing myself. temp = min(temp, coins_j + num_of_coins[i % j]). Oh wait, no sorry temp = min(temp, coins_j + num_of_coins[cents - coins_j * j]). Okay okay, yeah. cents minus this.

Intergalactic Avenger: And how do you break out of this while loop.

Festive Samurai: Actually, I don't think I need a while loop, sorry. So for 10 coins in this...

Intergalactic Avenger: Yeah, I think the temp needs to go outside of that.

Festive Samurai: So this is the number of coins I need from j, and it's not equal to 0. And then temp is the number of coins. And then I'll say the loop, I can do num_of_coins[i] = temp.

Intergalactic Avenger: Alright, let's fire it up and see how it goes. I'm going to comment that out so it doesn't run. Alright, let's see what we get. We should get 7. Oh, we should get 4 I think.

Festive Samurai: Oh, sorry yeah. That doesn't need to be len(). Okay. 31... Ok, so that should be 3 times 10 cents, that's 30. And then there's one cent. Yeah, okay that's four. Yeah.

Intergalactic Avenger: 4, alright, excellent.

Festive Samurai: You can do 70.

Intergalactic Avenger: That should be 4 too. Alright, excellent. Very good. So, what is the runtime of this version?

Festive Samurai: This is order of... coins is constant. So it's basically an order of n, which is the order of the number of values basically.

Intergalactic Avenger: Okay, makes sense. Now, if you think about this. So, it's order of n time, which totally makes sense, correct. If you were going to really do. And you wanted to have cents be potentially very large. Well, if you think about it, let's say you're making change for $1000.25 or $1000.10 or something. There is a shortcut you can make at the upper end of the number range. So you know for example that if you have some multiple of dollars, you just use dollar for those, because you know to a certain extent that you just use the biggest coin. So can you think of an optimization for this where above some certain number, you just use quarters and below that certain number, you use this more exact algorithm to find the perfect combination.

Festive Samurai: Yeah so, I'm trying to think of a reason, but my first idea was if it's over 99 cents, then I have to use quarters for dollars. So it has to be over a dollar, including a dollar.

Intergalactic Avenger: So any amount over a dollar, you know that you use quarters. And then for the remainder you use this algorithm. What's the motivation for a dollar. Like, of course we deal with dollars and hundreds of things and we like out trailing zeros and stuff, but is there a lower number that you could optimize past. Like, so 100 is certainly a good one. And anything over a hundred cents, you can simplify and say pay all in quarters above that, But, can we lower that number somehow? Like, where did that 100 come from? What properties does it have? Are there any lower numbers that have the same property?

Festive Samurai: Okay, yeah it does, I see the point. So, the highest value after 25 is 10, right? So for coins with minimum, so we have to do either coins of minimum of 25s or 10s. And that breakpoint comes when we go over 40. Because 30 we can use 3 tens and that works. 40, we use 4 tens, and that works. And when it's 50, we can use 2 quarters, and that works. So it has to be over 49, I think, when we can just use quarters until it comes to less than 50.

Intergalactic Avenger: Okay! And that is correct. But why? I mean, I think you're sort of hover around the answer. And I think you have a gut sense for it. But what is that special property that the number 50 has with respect to the other 3 coin denominations?

Festive Samurai: Because we know if the input is more than 50, quarters basically cover that. Quarter needs 2 coins to get to 50. And every other denomination need many more coins to get to 50. I'm not sure if I'm using the actual words you're looking for. But basically, quarters will get you to 50 much faster than any other coins.

Intergalactic Avenger: But why not 45? Why can't you go any lower than 50? And I guess where I'm really going with this is... So let's say, you're not going to have to write it, but let's just say that we have another function here with number of cents, and then I give you the coins. You created this coins array here, but what if it's an arbitrary list of denominations. Like this could be the number [26, 42, 89]. So this could be some kind of arbitrary set of denominations of any old weird numbers. And, you're right that you can totally follow this algorithm if I pass into you the coins. So you've defined them here because I gave them to you. But this algorithm will totally work if I just supply that list of coins to you. The only issue is that that is only optimal in terms of time down towards the lower numbers. And there's this optimization that you can make that above a certain number, you don't actually have to do any tough calculations. You can just say, above this number I can use the highest denomination and pay for them that way. And below this number, I have to do the certain number, I have to do this. So like, for example like if I pass you coins as [89, 26, 1]. Above some certain number, you're just using those 89 cent coins, because that's going to get you the fastest into the range where you have to pay more attention. And so just like you said, in the case for [25,10,1], 50 is that magic number, where above 50 you just pay with quarters. And with 50 and below, you gotta start doing all of the backtracing and memoization to find the perfect number. So what is that relationship between 50 and these three numbers. And how would you find that for any random set of numbers.

Festive Samurai: I see. So, we have to get the highest number in the coins, and the second highest number, and see how many times does the second highest number go into the highest number. So 10 is 2.5 times away from 25. So we can use 2 times of 25. Basically, in this case, we'll have to use 3 times 89 beyond which we can use 89 all the time, I think.

Intergalactic Avenger: So what is that number for [89, 26, 1].

Festive Samurai: 3 times 89, so that's 267.

Intergalactic Avenger: Hmm, 267. So where did you get that?

Festive Samurai: So basically what I'm thinking is how far is 89 % 26. Wait, not mod - by (divide). So that's 3 basically. So 3 * 89 is 267, which is how I got that.

Intergalactic Avenger: Hmm. But... I should have picked smaller numbers. But, I think that number is actually higher than that. I've picked some bad numbers because they're too high for me to reason about. So let's try something a little bit... Just try these to make it easier to reason about.

Festive Samurai: So the highest number is 33, beyond which we can use 11 all the time.

Intergalactic Avenger: Okay, so that's certainly true. But that's a little bit different than the equation you just gave me.

Festive Samurai: No, so 11/3 is 3. Now 3*11.

Intergalactic Avenger: Ah, I see, okay, alright. But what about 15?.

Festive Samurai: 15? So again, 45 would be it. So 15 / 3 is 5. 5 * 15 is 75. 75 is the breaking point basically.

Intergalactic Avenger: But actually in this case, the breaking point is actually 15. Because like if you have say 18 cents, it doesn't hurt you to start using your 15 cent coins already. Also, let's go back to the original one.

Festive Samurai: I got the reason now, I'm not sure how to reason that. Like I know how to do it now, how to get the value, how to get the breaking point. But I'm trying to see how I can reason that now. So from the examples that are given, I now know I have to take the LCM.

Intergalactic Avenger: Yes, exactly! That is exactly what you do.

Festive Samurai: Yeah but I'm trying to see how that helps.

Intergalactic Avenger: So yeah, I mean it's a little bit unintuitive, but it's just this idea that the multiples in a sense, you can think of as... In the same way you can break down a product into its prime components, in the same way you're breaking down this number. This larger number into these sums. And the sums are all going to be some number times... Or they're going to be some multiple of these coin denominations. So like, it's sort of like, it's a little bit of 3 * 25 + 1 * 10 + 1 * 5 or whatever. When you start to think about it, that's actually 3 * 5 * 5 + 1 * 5 * 2 + 1 * 5 and then you can say to yourself, well wait - I know that everything I'm doing with 1 * 5 or like, this piece here is already subsumed. It's almost like 25 is multiplying the effectiveness of my 5 cent coin. And so, you're automatically safe above... You know that 3 quarters will never be the worst thing to do, than using nickels. Because you already have that 5 piece in there that's being... The other way to look at 3 quarters is 3 * 5 * 5, which is 15 of the 5 cent coins. And so, as long as you can find the least common multiple, then that means your sort of re-aligning your parenthesis so that above that certain point, there's no need to worry, because you're already being covered in that sense.

Festive Samurai: Yeah, that makes sense.

Intergalactic Avenger: Alright, that was my question. I'll have some more feedback, but in general I thought it was really well done. And yeah, if you have any questions for, otherwise I'll just leave some feedback in the platform.

Festive Samurai: So, I was serious, this is my first time trying this, and I don't know what I can ask or what am I supposed to ask, like I was curious: being an interviewer, how does it help you, why are you doing it. I don't know if that's the right question to ask, but I'm curious.

Intergalactic Avenger: So a couple things, I do get paid for it. So that's an incentive. But also, I've done a lot of interviewing in the course of my career. I've been on both sides of the interviewing table, both interviewing and being interviewed. And, I think it's kind of an interesting process but also I think it's one of those things that can be very intimidating, and it can be frustrating and you can get really nervous and built up about it. And I have certainly failed many an interview and never gotten past phone rounds and all this other kinds of stuff. And I just found for myself that practicing and doing it over and over helps me solidify it and makes me sort of be better at going in interviews. And so, I want to be of some help to people who want to be better at it. So there's that kind of motivation as well.

Festive Samurai: I completely agree with that, that practicing solidifies it, but again like, these things you don't really use at work and if you don't practice it for six months or even a year, you kind of lose touch, and then you have to practice again a lot of times. I mean, I don't know if you agree with that. I mean like, how does it help in assessing someone if someone who hasn't practiced, is not able to solve them. And someone who has been practicing for months and then is able to do it.

Intergalactic Avenger: That is an excellent question and that is the million dollar question actually. At a lot of companies, especially the bigger companies, like Apple and Google and such, are famous for this, that they keep trying these different things, and they try to do interviews in different ways and there's definitely this acknowledgement that doing coding challenges like this is not perfect. But the thing is that no one has come up with anything necessarily any better. That's really what it comes down to. Everyone looks at this kind of stuff and they say to themselves "There's got to be a better way" and yet, when it comes down to trying different things - so I used to work at Google, and they're constantly tweaking their interviewing style, and as an interviewer at Google, you're constantly being told, "Well, you should try doing this differently, or doing this a new way" and all this stuff. And for a while, they really liked asking these brain teaser questions, much more like logic stuff. And then that went out of fashion. And then they said you should ask things that are really specific to your work. Like take an example of something that you were working on that day and ask them about it. And then that turned out that some people were better at those, but not as good as others. The problem is that there's no one right answer, there's no one right thing. And at the end of the day, if you are going to be a Software Developer, sure you might not have to play these little math games, but a lot of it is being able to see "Do you remember how to code?". And you know, not all positions involve a lot of coding, but a lot of times companies don't want you being afraid of it. So just being able to see you are able to close your curly brackets in the right way, is something that people want to see. And just sort of the mathematical mind. I mean, in a real interview, there would certainly be another element to it, which would be asking about your background and your thoughts on the company and the product and all this other kind of stuff. That's a lot harder to sort of have a platform for practicing in a uniform way. So this is also kind of focusing on one element of the technical interview. But like, it's an important one. As little as people want it to be true, like I've have very qualified and competent Engineer friends of mine who I've worked with and I knew were really really good at their stuff. And one example, the guy went in for a Google interview, they said no we're not going to give you an offer because you coded too slow. Wow right? Didn't get an offer because he coded too slow on the whiteboard. And like, you don't want it to be that way, you really don't. You want to be able to say "Hey, but this guy's got 20 years of experience doing this and he knows his stuff. And he's a super expert in all this, and he's super smart, and he'd be a great addition to the team. Why are you not letting him on because he's coding too slow." But the problem is, you know, that from the company's perspective, they only have so much time, they only have this small window into what your background is and what you can do, and they only have so many signals. This idea of solving problems with code is kind of what a lot of software developers do in one sense in part of their day, and just making sure that that piece is rock solid is important to a lot of companies.

Festive Samurai: Yeah, yeah, I understand.

Intergalactic Avenger: Yeah I mean, it would be great if there was another answer, but for the time being, in this day and age for what we know about interviews, this is kind of how they're done, so it helps to practice, it helps to get that stuff down and yeah. So I hope that's some kind of answer.

Festive Samurai: Yeah definitely, yeah. I mean, thanks a lot. I had a great experience doing this. It was my first time and I definitely liked it.

Intergalactic Avenger: Cool, alright. Well glad you enjoyed it, and I thought you did really well. So yeah, otherwise, good luck on your future practices and real interviews, and have a good rest of your night.

Festive Samurai: Thanks, you too.

Intergalactic Avenger: Goodnight, take care.

Festive Samurai: You too, bye.