Python Interview with a Capital One engineer

Watch someone solve the paint house price problem in an interview with a Capital One engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Paint house price

Interview question

Find the minimum price to paint all houses given a price list for each house and colors.

Interview Feedback

Feedback about Paisley Hex (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Communication was great and you immediately intuited that the problem could be solved with either backtracking or dynamic programming. Your implementation was clean and I could follow what you were thinking the whole time (which is shockingly rare, in my experience). I'd just keep practicing, maybe do more dynamic programming problems if you know you might encounter some. Knowing what parameters to build your table around can be tough.

Feedback about Occam's Pizza (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

1/4

Interview Transcript

Paisley Hex: Hello.

Occam's Pizza: Hey, how's it going? Can you hear me?

Paisley Hex: Yep, I can hear you.

Occam's Pizza: Hey, me one second. Right. All right, I'm going to copy paste this problem. And hopefully you haven't seen it before. If you have, let me know. If you want to do it anyway, it's okay too. Sorry about this. I wish they'd open the editor before this starts so I can put these in. Okay, all right, you got me?

Paisley Hex: Yeah, so no two adjacent houses can have the same color. And the cost of painting each house a certain color is represented by n times three cost matrix.

Occam's Pizza: And if that doesn't make sense to you, I can I can help explain it here.

Paisley Hex: Let me finish reading the problem again. For example, 00 is the cost painting the house zero with the house with the color red and the cost of one two is the cost of painting house one with the color green and so on find the minimum cost to paint all the houses. Okay. The costs are inputs?

Occam's Pizza: Yes, yeah. So the so these, this can be thought of as, so this would be that first element in the array. So the first array in this array, the first row is the cost of painting that index. So house zero either red, green, or blue. And then you go on to the next one, and it's the same thing.

Paisley Hex: And but like, these aren't the same for every house, like painting house zero green is different than painting house one green.

Occam's Pizza: Exactly, yep. You just want to minimize the total cost. So for this inputs two plus five plus three.

Paisley Hex: Then there are just a couple of edge cases.

Occam's Pizza: I see, so I'm thinking this might be a either dynamic programming or a backtracking problem.

Paisley Hex: Those are good inferences.

Occam's Pizza: As to exactly how to go about this, I am still kind of brainstorm how to do it. So I guess it's trickier in the sense that the adjacent houses can't be the same. Okay, so I guess the tricky part is like, what's optimal in the beginning might not be the optimal at the end. So you can't really save... We can't really save the answer. Like, traditionally, I guess, for dynamic programming would be like, you know, you save the two and the five as the optimal answer if the list was if as if there's only two houses. But there could be a combination later on where or maybe that's not true. I'm just trying to figure out if it's like, maybe there's a combination that dictates that okay, you have to take this the 17 or the 16 first or else, you know, the, the effects downstream might not might have to be suboptimal. So I think if there's a way to solve this by saving, or maybe I can think of like brute force first, where you just add every single combination. I guess that's basically what backtracking would do actually.

Paisley Hex: Yeah. So this first example, which is the only non trivial example here, you're right, it's not necessarily a good example, because you could just really take the cheapest house at each or add the cheapest color at each house. Right. Right. So and your intuition is correct, that that would not always work. But it might be worth coming up with an example here, for which that's not the case, so that you could test your algorithm against that.

Occam's Pizza: So for this one, you know, take the two, the size, just swap these around. Counterexample. Yeah, so you can't take two and two anymore. We would take take the 16 hours, or you take the two and you take the five, and then take a 17, I guess. And then you can go back to five again. So how did how did you detect that? So I think if there's like, there's an algorithm that can be used to get this because order does matter. And so is there a way to get this without trying every single possibility? Because otherwise, if you try every single possibility, that's, I think...

Paisley Hex: Yeah what would the time complexity basically tried to if we enumerated every single possibility?

Occam's Pizza: So there will... by changing just one value? I think it would be a quadratic as in n times n.

Paisley Hex: I think it'd be worse.

Occam's Pizza: Yeah, so maybe it's n times n times three.

Paisley Hex: So if we choose, if we choose, we can freely choose from the first one, right. And then depending on we chose in the first one, we can pick one of the other two trees in the second one, right? Yes, then so on. So you get something like the time complexity would be o of three times two to the n minus one.

Occam's Pizza: Right. So it's exponential.

Paisley Hex: Exactly. Your intuition is right, doing backtracking and numerating every possibility is, is suboptimal. Like if if if you want to write that out, it'd be good practice. But there is a better way to do it.

Occam's Pizza: Actually, at this point, I'm thinking it has to be I don't know if I'm digging a hole, but I'm thinking it has to be a dynamic programming problem. And I think that's, so I think there might be a way to get around the like, so I'll save... I'll see, I'll do like three options, basically come up with three answers, and then choose the best answer. And where the first answer I start with the start with red. Second, like I'll do like three arrays basically want the first array, I'll start with red, like an array and third start with blue? And their third answer, I start with green is a red green. And, yeah, and I'll, with these three options. I can choose, like, I can run the I think maybe I can do this in one pass. Okay. And that would be an O(n) solution, which I think is the best possible way to do it. How to do that. And still, like, it's still kind of fuzzy in my mind right now. Should I just write some pseudocode?

Paisley Hex: Yeah, you can just think out loud. I'm not going to judge your thinking or anything.

Occam's Pizza: So I think, you know, as you mentioned, the first option I can take, you know, let's say this is the blue column, or this is the red column. I take that no matter what, it doesn't have to be the most optimal. Like, I guess, like, in the middle, kind of thinking in the middle would it would like just because I start with one doesn't mean that, like, I can break away from that and, like do something sub optimal, and then go back to optimal again. I don't actually I don't think that's going to work even if I need I take a greedy approach for each one. Each color... Yeah, that's, that's not going to work either. So I don't... Yeah, so I can't take the greedy approach. So there has to be another way. So I guess now I'm thinking like, do I... Is there a way to do some sort of like, divide and conquer approach?

Paisley Hex: That might be but I think you're on you're on the right track. Okay, just think about it some more.

Occam's Pizza: Okay. Alright. So I, I worked down I work down the the array. I always take what's best at that current index. Maybe... We maybe I can add dimensions to two dimensions to this problem.

Paisley Hex: That's a good idea.

Occam's Pizza: Okay. All right. So let me just imagine, like what this might look like, just for the red, just for the read. So like, so I guess we're, or I'll take, I'll take 17 for some. And then and then. So I can only I can take the second 16, or maybe make this 15. So it's less confusing. Like I either take 15 or, or five. I'm thinking so... So not sure if this is right, I'm just gonna figure out by and I have to keep the state otherwise... And after I add them, I take the lesser one. Not sure. Because I keep on going down. Going down, things might change. So taking five and taking 15 will give me different options later on. So I won't know until the very end. But then, like, it kind of goes back to that. I'm trying to figure out which, which states I can actually cache. Because, you know, if I try everything, then I'm not really caching anything because I'm trying everything. Okay. So start with 17. So I can only, I can only take 15 or five right now. But... Oh, actually, I actually I can I think, or two of them can't be next together. Okay. Yeah. So I can only take 15 and 5. So maybe. Yeah, so me. So I'm thinking, I think it was thinking kind of just creates this tree basically. So if I take 15, for example, it kind of branches out to 17 and two or the changes for 19. But if I take it takes the 15. I can only take 19 and two. So maybe I can just build a tree. And well, if I build a tree, and then I calculate all the leads. That's basically... Yeah, that's now it's all right, leaves with that.

Paisley Hex: Do you know how many leaves in that tree.

Occam's Pizza: So that would be that would be the exponential. Probably two to the n minus one times three. Yeah. So back to thinking about the states I need to cache again.

Paisley Hex: Yeah, that's the right way to think about it. You're on the right track. Okay, so how do I cache the state but leaving flexibility? How do I determine which? Okay, so, so?

Occam's Pizza: So I can give you a hint here, if you're if you're looking at house one, so the second house index one, what is the best value you could get if he chose red for house one? What's the best value you could get if you chose green for house one and what's the best value to get if you chose blue?

Paisley Hex: So, for red, it would be two. For green, there would be green, or red or green. And for green will be blue again. I guess.

Occam's Pizza: So then. Yeah. So then if you went to the next house, what? And repeated the same process... How would that look?

Paisley Hex: So for red... it would be green. For blue. It would be green. For green, it would be blue.

Occam's Pizza: But can we append those results to the results append maybe isn't the right word. Can we can we extend those results iteratively?

Paisley Hex: Yeah, I think that could be a table. And then there has to be another additional. One more. I think one after we get that table, that table can be used for one more pass? I'm not sure if that is correct. But that kind of feels correct. I generate a table where the first the current house references the last house... Like what is the optimal last, you know, the previous house for the current house to take? And then maybe I can like do a search of some kind. On? On on... Maybe I can this time. Greedy we look for the lowest, the lowest amount. So let me just write it out a little bit. So like for... Yes, or for the first one, I'll just have zeros. And for house one. It would be ninth or the 16. In this case. It would be two I'll just write the values for 15 it would be 17. For five, it would be two again. I'm just testing this out to see if that makes any sense. For the second house to the middle house would be also five I think... Yeah. And the final house would be 15 in the middle. So I do see a pattern here where two of the houses will always show the same, like the two houses will show the best value in one, one house would show the second best value. Maybe that's something I can take into consideration. Okay. So this is a short example, so I'll go through the rest of it. This is so that I'm on house three now. So for 16 is two, for 15 is two again. Five is 17.

Occam's Pizza: I gotta say, you're exploring the best option in the previous house was for each house. Yes. Gotcha.

Paisley Hex: 14 is 5. Or, I mean, these could be indexes, indices. For better readability, I'm just writing them out. Or, yeah, five, nine, in this. Okay, so now there's a way to find the best way. So I would basically take some of these basically. Without I mean, I guess just reword the same problems.

Occam's Pizza: Yeah, I think finding the path here would still be exponential. But, but this is an interesting way to think about it. Yeah. But you are you, you do have the right shape for this table. So yeah, I don't know if I would do it exactly this way. But this is a good way to go have an n by three or a three by n table.

Paisley Hex: Okay. All right. So these are indices. I mean, as these change indices. Okay, so maybe I can maybe I can add them. Because if I don't take as I don't take. Okay, maybe like I'm just trying to figure out if I, if I take the most optimal, whether looking, you know, moving forward or looking backwards, it doesn't really matter because, oh, okay. Okay. Actually, I think it does matter. I mean, because I'm looking backwards. I'm just, all I'm considering is all I'm considering is from the final like as if like so if I'm looking backwards from numbers, house number two, which is this, all I'm considering is adding like which which branch is the smallest up to that point, I think. So I think that could kind of be more flexible than just thinking of it like more greedily. Okay, so. So now I'm at number... Let me just read the copy and paste this again. So, okay, I'm going to think about it like this, where... The best I can do at 3 is 17. To 17. And, and a house one. Which, which one should I add? You know, I should? I should? I should take that value for each, for each for each option and save it. Man, feel like I'm just going in circles a little bit.

Occam's Pizza: I think you're you're getting you're getting there.

Paisley Hex: Okay, so all right, so I'm at house one now. And that position, allowing the green position and, and and I want to I'm at the green position, so I want to add the two. So 16 plus two is 18. And oh, man, I think this is actually the solution. So 15 plus 17 is 32. Hopefully my math and I and the best solution is five plus two is seven. So I think I can actually just keep on doing this. And I just take, I just take the smallest at the end. And that should work. Okay. Wow. All right. Should I spend the last 10 minutes to code this?

Occam's Pizza: Alright, yeah, yeah. I have a follow up and some optimizations I could ask you about but those codes is first.

Paisley Hex: Okay. Yeah. Hopefully I have time to finish. All right. So min and just call it cost and key goals three... Give me the table. And then I'll just I guess I'll just reassign pzero. Let's actually give you the table and then the algorithm is basically to choose the one that you're not... So for. For house in branch... select the minimum. So we're seeing how I can do this. So I can do like the what is house is our array? Maybe that's why I do need a house sorry house is an index. So I need to like do another for loop to populate each column. Actually this is actually one more. Okay. All right. So dp house or color equals itself... cost equals position adding the minimum of the two positions that it's not so... Okay, so I need to figure out a way. Okay, so maybe I'll create another table here I'll have what is called positions and create an array of positions where one or zero equals a tuple. And... okay, yeah. Oops, I was just, I did Ctrl S to play, I mean to save, it doesn't matter. Alright, so. So I just call it next index one, index two. And I'll just finish on one... positions dictionary. Color. So I'll get the minimum of the previous, the previous dp. So I'll just copy and paste here and index one and index two and I'll just do a house minus one. So after this, I think this is the algorithm I think this should just work if I just return minimum of dp. They're just the last night I went to the DP array. So, do I just run this or do want to talk about it.

Occam's Pizza: You want to try running it on the first input, the first example input. Just pick either we get 10 to that.

Paisley Hex: Okay, so an object is not iterable. So I don't think I can list a dozen.

Occam's Pizza: No, you could. I think I think you just need to make that range length crossed. Oh, yeah, there is a typo to make. There. Yeah.

Paisley Hex: I have to print it.

Occam's Pizza: Yeah, I think I don't I'm not super familiar with this editor, this platform. But yeah, I think you got to print it. And there we go. Pretty good. Yeah. So this looks good. This is I think the optimal way to do it. So I have a whole nother follow up. But I'm not going to do that. But I'm I asked you, how could we optimize space on this?

Paisley Hex: I think we can definitely just make it two columns. Because we only need the last... We only need the last row. So it could be the case where after we're done with the last row, we just overwrite the last row, we just swapped the we just swapped the two columns back and forth.

Occam's Pizza: Yeah, exactly. Because it's because we only the it's sort of like a Markov property, right? We only care about the previous step. We don't care about any of the steps prior to that. So yeah, well, that's great. That's it. You got it.

Paisley Hex: Well, you gave me a your gave me a good hand. So I wish I thought of it.

Occam's Pizza: Like, this is a tricky problem. And I know some companies don't even ask DP anymore. I think like Facebook doesn't ask DP anymore. But I you know, it's good to prepare, I think. Yeah. Yeah.

Paisley Hex: I know, it's good that you asked a pretty difficult one, because I do want to move to a company that I mean, the company I'm looking at does have a pretty high bar. And I do think like, given the you know, the COVID situation hiring bars has like so yeah. Now this is a good one. I I'm just going to remember it now. I feel like yeah, it...

Occam's Pizza: This one's hard. For the same reason, a lot of dp is hard, because it's not clear what you want to memorize, like, like what the so like, if we were using a memo, like what the arguments you'd want to memorize are, but in this case, like what we want the cells in our table to correspond to, you know, it can be tricky.

Paisley Hex: You have any general or that I can improve upon.

Occam's Pizza: No, I mean, you did a pretty good job, you were very explicit about what you're doing. I can't think of anything off the top of my head other than practice more dp if you're going to be interviewing somewhere with DP questions as well.

Paisley Hex: Oh, thank you. Thank you. This was great. Stay safe and thank you for the interview.

Occam's Pizza: For sure, absolutely. Enjoy the rest of your night.