Python Interview with an Airbnb engineer

Watch someone solve the two sum problem in an interview with an Airbnb engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Two sum

Interview question

Given an integer array and number k, output all unique pairs that sum up to k. Example: for input [1, 3, 2, 5, 46, 6, 7, 4] and k = 4, output (1, 3).

Interview Feedback

Feedback about Adequate Penguin (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

Great interview!

Feedback about Recursive Beast (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

3/4

Hey there, Thank you for your time! I like the question. It can be made progressively harder if necessary. It also has some interesting corner and edge cases. Very good interviewer. Overall, I felt at ease and comfortable. Exactly one time, I wasn't sure if I was talking to myself or not, but that's due to the medium of communication (audio only). I enjoyed our discussion about time complexities. I misspoke about seeing an in-place iterative quicksort. The quicksort I saw here (https://www.youtube.com/watch?v=WaNLJf8xzC4) *is* in-place, *but* not iterative. It is recursive. Sorry for any confusion.

Interview Transcript

Recursive Beast: Hello?

Adequate Penguin: Hello, how are you?

Recursive Beast: Hey how's it going, I'm good how are you doing.

Adequate Penguin: I'm doing good as well, thank you?

Recursive Beast: Sorry for the wait, I had some problems with my connection for some reason.

Adequate Penguin: It's fine no worries.

Recursive Beast: Cool, is this your first time on the platform?

Adequate Penguin: Yeah, this would be my third time, and this is my first week. What about yourself?

Recursive Beast: I've been an interviewer for a few months now, I've done a bunch of interviews. Are you new to the industry, are you looking to switch jobs, is it your first time interviewing or just looking to brush up your skills?

Adequate Penguin: Right, so I am new to the industry, I just graduated but I studied electrical and computer engineering.

Recursive Beast: Okay, cool Awesome. What was the most challenging project you worked on at school?

Adequate Penguin: So it was actually a software project, we were developing a quad-core processor but in code and Verilog which is what they call a hardware development language. My team and I made, like, a logic core, a cache, and a ring network. We kind of traded off roles. I was, for example, verifier on the cache, implementer on the core, that sort of thing. We put it all together into this really nice quad cord.

Recursive Beast: Okay, cool. And was it the most exciting project you worked on?

Adequate Penguin: Yeah, I think it's the thing I'm most proud of up to now.

Recursive Beast: What was exactly the most challenging part for you about this project?

Adequate Penguin: Okay, so for example when I was verifier for the cache, I had to come up with how I was going to verify the entire cache. It was a finite state machine based cache, so there were a lot of things to check. There's a lot of paths through that finite state machine that you can go through and you have to check each one.

Recursive Beast: Right, Right.

Adequate Penguin: You have to make sure you don't miss any of them. I also wanted to add in some of that into all of my test cases. I wanted to add in some of my locality temporal and spatial that you might find in a real cache request. So I kind of took that idea around, like, how do I do this? And I eventually wrote a script in MATLAB because I didn't know Python at the time. But I did it in MATLAB which kind of used just random chance. Some probabilities I did adjust myself to determine if the next cache request would have the same address as the previous one but with certain degrees of granularity like if it would have the same, for example, four bits of the same address or the entire first eight bit, that sort of thing.

Recursive Beast: Okay, I see.

Adequate Penguin: Yeah, so I was really not glad when I got all of that working.

Recursive Beast: Okay, awesome. Well thanks for sharing. Do you see what I am typing on the platform?

Adequate Penguin: Yes, I do, I see. Hello! Hello as well.

Recursive Beast: Awesome, yeah. Let me tell you the question verbally first and then we'll proceed to implementing it and I'll type it out on this platform.

Adequate Penguin: Sounds good.

Adequate Penguin

Recursive Beast: So you're given an integer array and a number k and I would like you to output all pairs that sum up to this number k. (while typing) So, given an integer array and a number k, output all pairs that sum up to k. Let me give you a few examples: let's say you're given this [1, 3, 2, 5, 46, 6, 7, 4], and k = 5, I would like you to output (1,4), as well as (3,2). Let me know if you have additional questions about it, so yeah that's about it.

Adequate Penguin: So, I want to be totally upfront: I have seen this problem before. Is that okay with you?

Recursive Beast: Yeah if you can just tell me what you think the solution is?

Adequate Penguin: So there is one thing off the top of my head wrong with the solution I'm about to give. You can put it in a set and for each number in the list: go to it, get the complement. So in this case you go to 1, then you would get the complement: the 4 and check in constant time whether 4 is in that list. And if it is, then you have your first pair. You would do the same thing for 3, except now you'd be looking for 2, the complement. So you see it right in there, you would output it. For the 2 you would get a duplicate, (2,3), so one thing you can do is as you get pairs you can remove them from there. What if you have two 2s in there?

Recursive Beast: Yeah so I don't want you to have duplicates in the output.

Adequate Penguin: No duplicates in the output but you do allow them in the array.

Recursive Beast: Yes, in the array that I am passing in, yes.

Adequate Penguin: What is you have this: [1, 3, 2, 3, 2, 5, 46, 6, 7, 4]. You have two distinct pairs: (3,2), (3,2), but they're the same pair. Would you want two of those outputs?

Recursive Beast: Yeah, I would want the pairs to only show up once.

Adequate Penguin: Okay, so that should work for sets, because once you make it a set, at least in Python you remove any duplicates, right?

Recursive Beast: Okay, mhm.

Adequate Penguin: So after you make this list a set, even if it had started off with duplicates like this [1, 3, 2, 3, 2, 5, 46, 6, 7, 4] it would just turn it to a list without duplicates. This list: [1, 3, 2, 5, 46, 6, 7, 4]. Okay yeah so let's go through it. You look at this one. I think a good strategy is to remove it immediately because what if you had a 2, like what if your sum was a 2?

Recursive Beast: What if what?

Adequate Penguin: What if sum is a 2, so k = 2 instead of 5. If you look at the 1 and look for a 1, you'd be finding the same 1 and returning (1,1) incorrectly.

Recursive Beast: Right.

Adequate Penguin: Instead you could do like: okay my complement is a 1, I'm going to remove the 1 I'm looking at and look if there's a remaining 1. And there isn't so you don't return (1,1). So I think that should take care of that edge case, but now let's go back to the original example. You see there is a 1 and you ask yourself if there is a 4 but first you remove the 1 as we said. So there is a 4…

Recursive Beast: How about we go ahead and actually try implementing that solution?

Adequate Penguin: Okay, that makes sense.

Recursive Beast: So, you're satisfied with the set solution? The solution that uses a set?

Adequate Penguin: Yeah, let's try doing it. I just want to know absolutely that all the edge cases are taken care of. And do you want to use Python? I just changed it to Python.

Recursive Beast: Thank you, yes I do want to use Python.

Adequate Penguin

Adequate Penguin: Let's get rid of this. Okay. def find_all_pairs_that_add_up_to, then nums our list. Okay so first we're going to make a set out of nums so that should remove our duplicates as well. Now we're going to go for num in nums_set. I think you can iterate through a set just as well as you can iterate through a list. But actually since we're modifying the set maybe we should just iterate through the list.

Adequate Penguin: Okay so now we're going to get the complement which would be k - num. To avoid that edge case that I mentioned we should remove num from the nums_set. And here, remove() will sometimes throw an error if num is not in nums_set but here we're guaranteed for it to be in the set.

Adequate Penguin: Well, okay, that's incorrect, if nums originally had duplicates, we could be trying to remove a number that is not in the set, no longer, right? Like if we had two 1s in there. So that's why I made nums_set back into a list without the duplicates so now both num_set and nums have the same digits.

Adequate Penguin: Now we check if complement in nums_set. Do you want the output printed out or added to a list? Do you want the output accumulated into a list of tuples or do you want it just printed out?

Recursive Beast: It doesn't really matter. As long as they're pretty obvious that it's a pair, it's fine with me. Whatever format you prefer.

Adequate Penguin: Okay, so if there is the complement in nums_set the num and complement add up to k so we print them out. Otherwise we don't do anything and go on to the next number. And we can go ahead and test this out. We can either run through the example, or run through it like a hand by annotation.

Recursive Beast: Let's actually make a couple of test examples and run the code with the test examples.

Adequate Penguin: Okay, sounds good. Let's have a function that just tests our answer. Here is one version of nums that we can run through and k = 5. And we can have it run through on that set of numbers. And now we can have another version that would test when k = 2 and there's a 1 in the set of nums but there aren't two 1s. Maybe like a test case where there aren't any pairs that add up to k. [2, 5, 8, 2, 8] k = 20. And maybe another one where you have this situation [2, 3, 3] k = 5, and you don't want to print out the pair twice.

Recursive Beast: Yeah exactly, I would only want to print out (2,3).

Adequate Penguin: Okay I could just run this, but then we'd have to check out all the test cases visually, or I could put the respective results here. This one would have to print out (1,4), and (3,2). Only (3,2) once even though 2 is in there twice. This one would have to print out nothing, just and empty list. This one: another empty list. And this one: just the tuple with (2,3) just once.

Adequate Penguin

Adequate Penguin: So let's run it.

Adequate Penguin: Okay so that didn't work. So let's run through one example and see what should be going on. Let's see if we just print this out. It's printing None because I'm not returning res[]. So should I run it again?

Recursive Beast: Yep.

Adequate Penguin: Okay so we did fail one test case, the first one. (1,4) and (2,3). That's because it printed out the numbers in the other order, don't see why though. Maybe when we did the set it kind of reordered some things, that could be why? Should I test it some more or discuss the time complexity?

Recursive Beast: We didn't print out all the pairs, we only printed out one example. Why does it say true true true true?

Adequate Penguin: Because we're comparing against expected outputs. I could have it just print out the pairs if you like. It might not be very obvious.

Recursive Beast: Okay, sweet. If you could talk about the complexity that would be great.

Adequate Penguin: Yeah no problem. First of all we are using a set, that set will be on the order of O(n) or actually, the O(number of unique numbers in nums) and that's for space. For time complexity we are just running through a basic for loop which just runs through each unique number in nums and this remove operation and this membership test and this append. I think they are all constant, especially if amortized over so sometimes adding something to the end of an array can be O(n) but because this is probably a dynamic array it is amortized to O(1). What I'm trying to say is that inside this for loop is all constant time, it's also O(n) or more precisely O(unique).

Recursive Beast: Perfect, so what if I told you that you couldn't use a set?

Adequate Penguin: I couldn't use a set? If I couldn't use a set the next thing I could think of is to sort the numbers. That would incur nlogn penalty time. Once I sort these numbers I would get [1, 2, 2, 3, 3, 4, 5, 6, 7, 46]. And I would use a two pointer approach. If I point to the very first element and the very last element and that the sum of those is larger than the desired sum then I can decrease that by moving this pointer to the left. And now my sum is eight but that's still too large so I would decrease that pointer. My sum is 7 and that's still too large, now it's 6, still too large. Now, 1 and 4. 1 and 4 sum to the desired sum so I would output that. Once I get that 1 and 4 I have used them up so I can just increment that pointer and decrement this one.

Adequate Penguin: But what if there was also a 1 in there, I would have to account for that but I don't want to output (1,4) twice…. I think I have a way to account for that and it would be just by looking back at the last thing that I appended to my list of results and checking if that is equal to my proposed couple. Does that make sense or should I explain more clearly? Because I would not necessarily have to encounter those in order. If there were two pairs of (1,4) in the list I would encounter them back to back. I just had a (1,4), I wouldn't need to include this one. I don't think it would ever have the chance where you would have something else here and then a (1,4).

Recursive Beast: Right, right.

Adequate Penguin: It would be contiguous.

Recursive Beast: And what would be the time complexity of this solution?

Adequate Penguin: Right, so you can't get away from that O(nlogn), you have to sort it. And then after you do that sorting the time complexity is linear because you're basically either incrementing or decrementing the left or right pointer once per iteration, and you would eventually have to meet up and that will take at most n iterations.

Recursive Beast: And what would be the space complexity.

Adequate Penguin: If you do in-place sorting it wouldn't be any extra space complexity. It would just be constant.

Recursive Beast: What sorting algorithm would you use?

Adequate Penguin: Actually just today I saw an example of in-place sorting for quicksort, so you could do that one. I also know that you can do in-place sorting with heapsort and that would also be O(nlogn).

Recursive Beast: And was that quicksort an iterative or recursive implementation?

Adequate Penguin: Yeah it was iterative, so it wasn't going into the stack or anything. Yeah I actually saw it from a TEDx video.

Recursive Beast: And if it was a recursive algorithm, you mentioned something about the stack.

Adequate Penguin: Right if it was recursive then you'd use space on the call-stack.

Recursive Beast: If you couldn't use the two pointers, how would you make sure that you found the pairs?

Adequate Penguin: Without the two pointer approach you could do like a brute force approach where you check every unique pair. Like a hash approach would be pretty much like a set approach but a little more inefficient. So you're not going for that right, no hash? Once you sort them, you can do a binary search. Here, you know you're looking for a 4 so you can binary search on the remainder. That would itself be O(mlogm). O(nlogn) for sorting and again O(nlogn) for binary searching.

Recursive Beast: O(nlogn) for binary search?

Adequate Penguin: At this place it would be O(logn) but you'd also do another plug-in here and here. And of course the space you're looking through can get smaller and smaller but overall it will be around O(nlogn).

Recursive Beast: Okay, cool sounds good. Thank you so much for implementing the solution even though you saw the problem before. I just wanted to make sure we covered all the edge cases.

Adequate Penguin: Okay, no problem. So should I implement the other solutions?

Adequate Penguin

Recursive Beast: No it's fine actually. After we finish the interview there will be a feedback form that you should fill out if you can and I'll do the same for you but that's about it.

Adequate Penguin: Yeah I definitely will fill that out. If you have some time, could I ask you a few questions.

Recursive Beast: You can leave any questions or feedback on the form actually. What kind of questions did you have?

Adequate Penguin: Right, so I just wanted to ask what you did yourself. Like the naming here is very big but very descriptive, what are your thoughts on that? Like having this very large name find_all_pairs_that_add_up_to() is very descriptive but is very large and do you have an opinion on that?

Recursive Beast: I wouldn't stress out on naming too much, I would actually rather it be descriptive and have long name of functions and variables than have very generic names. I think it's actually better to be descriptive than not descriptive. I think your solution is pretty clean and easy to follow.

Adequate Penguin: What about like, naming nums underscore set. Is there a better way to do it?

Recursive Beast: Yeah, again I would say that I think your naming conventions are fine as long as you're following conventions that are also appropriate for the language that you are using. I personally do not use Python.

Adequate Penguin: Okay, thank you. If you have a few minutes can I ask you what you do? Like are you front-end back-end?

Recursive Beast: I'm a back-end engineer.

Adequate Penguin: Okay, and you work in what languages?

Recursive Beast: I work in Ruby and Java.

Adequate Penguin: Ruby and Java, okay. Can you say more about what you do, or would you rather now?

Recursive Beast: I work on a fraud team, so I deal with anything related to fraud. Basically keeping the platform of the company that I work for, safe.

Adequate Penguin: Okay cool, thank you very much for your time. I really appreciate it.

Recursive Beast: Yeah of course. Thank you so much for your time as well. If you could leave feedback for me and I will do the same for you that would be great.

Adequate Penguin: Yeah, definitely

Recursive Beast: Have a great day! Bye!

Adequate Penguin: Bye!