Python Interview with a LinkedIn engineer

Watch someone solve the matching pairs problem in an interview with a LinkedIn engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Matching pairs

Interview question

Find pairs of values that sum up to a given value.

Interview Feedback

Feedback about Dystopian Pizza (the interviewee)

Advance this person to the next round?

Yes

Feedback about Admiral Velociraptor (the interviewer)

Would you want to work with this person?

Yes

Interview Transcript

Admiral Velociraptor: Hello? Hello...? Hello? Can you hear me?

Dystopian Pizza: Hey can you hear me?

Admiral Velociraptor: Hey, how's it going? Yeah, I can hear you fine now, yeah.

Dystopian Pizza: Good. Cool.

Admiral Velociraptor: Sweet, so have you used this site before to do mock interviews?

Dystopian Pizza: I've been an interviewer before, but I haven't done an interview yet.

Admiral Velociraptor: Oh awesome, so I guess you're on the flip side now. That's cool. Let me just jump right into the technical question then, since you're familiar with the site. Given a list of whole, positive numbers, how would you go about finding two numbers in that list that sum up to a given target number. And you can assume that there are no duplicates in the list, so I'll drop some of the details in the comments.

Dystopian Pizza: Okay cool, is Python cool with you?

Admiral Velociraptor: Sorry, what?

Dystopian Pizza: Is Python okay with you?

Admiral Velociraptor: Yeah, Python is fine. Whatever you're most comfortable with.

Dystopian Pizza: So we have a list of whole numbers. And given that list, we need to find two numbers that sum up to a given value.

Admiral Velociraptor: Exactly. And it would be convenient if you could print it out.

Dystopian Pizza: Okay, can I assume that the list will always have a valid answer?

Admiral Velociraptor: No, you cannot assume that. That's a good question to ask.

Dystopian Pizza: Okay, so I think I've got an obviously naive answer, which is you go through the list once, and for every value you check the list again. That's O(n^2). I've got a solution that's down to O(n), which is that you essentially iterate through the list, and you put them all into some sort of hash table. And then you iterate through the list a second time, and then for each value in the list, you subtract it from the target value and then you find the complement number that you need to find. And then you check the hash table to see if the complement is inside that.

Admiral Velociraptor: Perfect. So, you described two solutions here. Can you describe to me space-time wise what the second one would be.

Dystopian Pizza: I think it would be O(3n) because you iterate the list once to put the values in. And then you iterate the list again to check for compliments. But the checking process would be constant because it's in a hash table.

Admiral Velociraptor: Cool. In this problem, do you know if your... Generally, what I like to tell the candidates is you definitely want to clarify what you're optimizing for. So like, space or time.

Dystopian Pizza: In this one I'm optimizing for time, because I'm producing an extra data structure to keep track of it. Maybe there's a way to modify the original data structure to make it use less space. But I guess in this scenario, is the goal to save space or time?

Admiral Velociraptor: Cool. Yes, so that's kind of the question I was hoping you'd ask. The way I generally do the interviews as an interviewer is that I like to give feedback iteratively, over the course. So yeah, in this problem, definitely optimize for time, and yes - it's generally good to ask so you have a better sense of the code.

Dystopian Pizza: That makes sense.

Admiral Velociraptor: But yeah, your solution is definitely optimized for time. You definitely have to do at least one iteration of the list to get the answer. So why don't you just go ahead and start coding it out if you don't have any more questions about other things, then go for it.

Dystopian Pizza: Cool, I'm going to run this one time just to make sure everything is going smoothly. Cool, let's code it up. Quick question, which wasn't brought up before. So there could be more than one valid answer obviously. Here we have (1, 2) but we could also have (0, 3). Do you want multiple valid answers?

Admiral Velociraptor: Yeah, so that's a good question to ask. One single valid answer is fine. And also you won't have 0 in the list, so it will be just positive numbers.

Dystopian Pizza: Okay, so only positive numbers and one valid answer is okay. Do you want me to return null or return false or just return an empty string or something?

Admiral Velociraptor: Yeah, if there's no valid pairs, then you could just print out No valid pairs, that's fine. So that's a good question.

Dystopian Pizza: Okay, cool. So, yeah I think I'm good to go for now.

Admiral Velociraptor: Sounds good.

Dystopian Pizza: So, I'm just going to test some key test cases.

Admiral Velociraptor: Sounds good.

Dystopian Pizza: Actually, I'm just going to stick with the first one and then we'll do the key test cases afterwards.

Admiral Velociraptor: Yeah, that's generally what I like to ask as a problem, the candidate writes out a few test cases and then we can look at the outputs together.

Dystopian Pizza: You said you like to do that first or afterwards?

Admiral Velociraptor: After is fine. If you're used to TDB and if it helps you code up the solution, either way is fine with me honestly. As long as we can have a discussion about why you chose those test cases, and how you generally like to do your code coverage.

Dystopian Pizza: Sure, I'll go forward and then we'll discuss it afterwards.

Admiral Velociraptor: Sounds good.

Dystopian Pizza: Yeah, is there some sort of set value I could use? I don't know what Python's set value is. So I'm just going to do it like this.

Admiral Velociraptor: Okay.

Dystopian Pizza: Okay, so let me just run through line by line to make sure I'm not missing anything. So, we start with putting the values in a dictionary from the list. And then for every value in values, we iterate through it and we add the value to the dictionary. And then we go through the list again, and we get the complement value. Or the target, not a great name, but whatever. Equals value_dict[value], we don't need to check for null, because obviously it has to be there from the previous line, minus the target value. You can do extra checks for a valid target compliment, but I don't think it's really necessary for what we're doing because if it's an invalid number, it just won't be in the value dictionary. And then we get the target_compliment in the dictionary, which is Python's way of "if it contains", then we return the compliment and the value in the format that we presented. I guess technically we want to do it the other way around because in our scenario we would do the value first, and then we would find its complement, which would be the target value, and that would produce 1 and 2, at which point you return that as a string. And then if that doesn't work, we return no valid pairs. So let me run this and see how that goes.

Admiral Velociraptor: Looks like just a few small things to tweak, right?

Dystopian Pizza: Oh, sorry, yeah. It's not working with Python for the value, so it's false. So I guess let's figure out why that's false.

Admiral Velociraptor: What do you generally code in?

Dystopian Pizza: Right now at work I'm generally doing JavaScript and Java. Python generally I use for projects and stuff.

Admiral Velociraptor: Okay, cool. And generally it's good for interviews too because it's easier to write. It's faster.

Dystopian Pizza: Yeah, it's written like pseudocode. Okay, so let's take a quick look. I'm going to take a quick look at end of my... I'm going to throw in some prints. Can you debug in this console, I'm not sure? Do you know?

Admiral Velociraptor: I don't think you can debug, generally what I've seen people do is like add in print statements, that kind of thing.

Dystopian Pizza: Okay. So, I guess there are a few states that I want to check. First, did the value in the dictionary end up being what I thought it was. And then also did my target_compliment end up being what I thought it was.

Admiral Velociraptor: Yeah, makes sense. And you can also get rid of this Hello, World! that's going on over here. Yeah, there you go.

Dystopian Pizza: Yeah, that should be sufficient to let me know that we are running through the stack where we think it is. So, our compliment is always -2, which... The values in the dictionary are the values that they should be. target_compliment is -2, why is that? Is our target correct?

Admiral Velociraptor: Oh, is it because you are doing True - 2. So True is just 0.

Dystopian Pizza: Ahh, yes. Actually, I didn't even know that... Good call, good catch.

Admiral Velociraptor: There we go. Now I think you just have to pull it out somewhere.

Dystopian Pizza: Okay, let me...

Admiral Velociraptor: Why would it even print False? Oh because you have == there.

Dystopian Pizza: Yeah, I said == there because it gets away with testing it. Oh, that's why. Because 13 and 10 is the first valid pair in the list. So 1 and 2 is not the right answer.

Admiral Velociraptor: Oh, so are you subtracting them?

Dystopian Pizza: The goal was to find the target of the two, which means if I find the value - target, that's not getting me the two that work together.

Admiral Velociraptor: So, for this you would want 1 and 2, so you want to find the sum of two numbers, that equal the target.

Dystopian Pizza: Yeah, sorry, just give me like 30 seconds to figure this out.

Admiral Velociraptor: Yeah, take your time. No rush.

Dystopian Pizza: So, in this case we want 3 minus the value. The value would be 3 minus what it is. So in this case, yeah, 1 and 2 becomes that. Which equals 1 and 2 and then we can run a few other tests. So like one test that I'm going to run is if there's no valid pairs.

Admiral Velociraptor: Sounds good.

Dystopian Pizza: So in this case we're going to get rid of the 2. And there should be no valid pair now. I'm also going to run it when there are multiple valid pairs in there. So here there are multiple valid pairs. And the right answer here should be 1 and 4.

Admiral Velociraptor: Mhm.

Dystopian Pizza: I guess a way in which this would fail... I think this would still work... You know where this would fail? This solution?

Admiral Velociraptor: You're telling me, yeah.

Dystopian Pizza: If a value is 4 and we have this... [2, 2]. Now the problem with this one is that [2, 2] would only be one entry.

Admiral Velociraptor: Yeah.

Dystopian Pizza: Now, I'm trying to think about the consequences of that, because in this case we do the target - 2and then we check inside and that's correct. So this would be correct. But this one would be wrong. And that could probably be solved perhaps by keeping the counter and then checking to see... Instead of putting True there, doing a counter. And then if there are two of the same thing, we... I'm forgetting the word, we don't iterate it, but you know what I'm talking about, we add one to the value, so we assign the value in there.

Admiral Velociraptor: Fetch the value, add one, put the new value in for the key. Yeah.

Dystopian Pizza: And we don't allow for the same thing to check for itself because it's over here, it should say no valid pairs, but will probably still return true.

Admiral Velociraptor: Uh, well... If you're going through that second one in the new way, you would only do one iteration in the for value so it would just be one, and then it wouldn't work. So like if 2 checked for itself, and it's only one, you would know that 4/2 is 2, so it needs at least 2. So you'd be able to do a little math there and figure it out.

Dystopian Pizza: Yeah, so you would just need to modify the code so that it could handle this case over here.

Admiral Velociraptor: That would would be good.

Dystopian Pizza: Okay, let me take care of that.

Admiral Velociraptor: Okay.

Dystopian Pizza: Sorry, sorry, sorry. I've made this overly complicated. So first we just check if it's in the value_dict. Then we check if it equals its complement. If it equals its complement, then we need to check if that value is more than one. Okay, I think this might be what we're looking for. Okay, so first we check if it's in the value_dict, then we check if it equals its complement. If it the complement is not greater than 1, then you continue and you keep iterating. Otherwise you return the value string.

Admiral Velociraptor: Okay.

Dystopian Pizza: With the two value bug, I want to run through this again just to double check in my head.

Admiral Velociraptor: Good call, yeah. Definitely want to catch it on your own first before the test finds something. So good call. I think I like your solution. You still got the wrong value.

Dystopian Pizza: So I got the right value for the last one, but I got the wrong value for this over here.

Admiral Velociraptor: That's a valid solution. So we'll probably want to put it in the debugger and see what's going on here. I'm sure it's related to the counter stuff because this is a case where you have two duplicates.

Dystopian Pizza: I think it needs to be greater than 0, not greater than 1, is what the problem is.

Admiral Velociraptor: Oh yeah, that makes sense, yeah.

Dystopian Pizza: There we go.

Admiral Velociraptor: Nice, very nice, yeah. So, I'm just looking over your code now just to make sure there aren't any breaks. And a question for you is, do you feel like you've covered everything with the test cases?

Dystopian Pizza: Let me try to think again. We are assuming that the numbers are a valid input, correct.

Admiral Velociraptor: That's what I was going to say, I was hoping you'd ask because I did mention that the input list is valid, but I never mentioned that the target number would be valid. So you definitely want to try with a negative number for example or 0, or like those kinds of things.

Dystopian Pizza: That's the thing, I think 0 and also the number 1 would also not work, because 1 would require two positive compliments.

Admiral Velociraptor: Oh, that's a good catch, yeah. So, yeah. You definitely want to test those things out.

Dystopian Pizza: Okay, so let me just run through it again. We've got the valid case. We've got no pairs. We've got two of the same numbers. We've got two of the same numbers with no complements. We've got invalid target, because it's too low. The target, I'm going to assume we're not going to get something that'll overflow the target numbers, so it's not going to be too high. I don't think there are any other extreme values that would throw it off. Okay, I think I like my tests of target values. Let me do one with an empty list as well.

Admiral Velociraptor: Good call, yeah. In this scenario you can assume the input list is valid with whole, positive. But I like where your mind is at.

Dystopian Pizza: Okay, yeah. Let's run the code. Cool, that looks good.

Admiral Velociraptor: Great.

Dystopian Pizza: I think I'm happy with the solution in terms of speed. Obviously it's not the most space efficient as we've mentioned initially. I think I've come up with a decent amount of tests. Yeah, I think I'm happy with this.

Admiral Velociraptor: Great, yeah. So that was my question. Some reasons why I basically like asking this question is, 1) it gives you a sense of the candidates is ready to ask questions before coding. 2) is it lets me on a deeper more syntactical level see how well they can code this out and structure their thinking. And 3) is seeing that they cover all kinds of edge cases in their tests and ask the right questions and basically they have their head in the right place. Basically you could have done just 1 and 2 and also no valid pairs, and it would have been pretty poor performance if that was the case, but you definitely found thing through testing is the scenario of duplicates, so that's very good. The only feedback that I could give on this interview that would make it better is if you actually thought of the duplicates thing or whether both inputs were going to be valid, those kinds of tiny things that you ask to them before you start coding. That would have been like super impressive. But otherwise I definitely thought this interview was fine. I would definitely give it a pass to the next round. Yeah, that's my feedback.

Dystopian Pizza: Okay, great. Thank you! I guess feedback for you, because I think we're supposed to do it both ways is that I thought you were really clear, I thought that you gave a question that was really easy to get started on right away. You were also very good at not giving me the answer, but also working me through it, so I appreciate your feedback, thank you.

Admiral Velociraptor: Cool, cool. Good to hear it. And it's kind of cool, you do interviews on this site too. How's the experience been with you? Because I haven't given an interview yet on this site to someone who's an interviewer.

Dystopian Pizza: So, I started as an interviewer because I ran into the founder at some sort of meetup, and I decided to try it as a courtesy. And I kind of wanted to try both sides. I'm not strongly looking for any type of position right now, so it's kind of interesting to see both sides of the experience. This seems kind of like a no brainer. This right now felt exactly what it felt like when I was screening for interviews, so it's pretty good. Pretty valuable for whenever you look for a job next, whenever that is.

Admiral Velociraptor: Cool, yeah. Good to hear. It was great talking with you. I guess since you're not looking right now, I don't want to wish you best of luck or anything. But when you do look down the future, I do hope it goes well for you.

Dystopian Pizza: Okay, yeah thank you!

Admiral Velociraptor: Cool, alright. Bye.