# Python Interview with a Meta engineer #### Watch someone solve the fruit into baskets problem in an interview with a Meta engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays. Python interview with a Facebook engineer: Count max fruit - YouTube ### Interview Summary **Problem type** Fruit into baskets **Interview question** Given 2 baskets that you can collect fruit into, find the subsequence of 2 fruits that maximizes the amount you collect. ### Interview Feedback #### Feedback about Sensible Bassoon (the interviewee) **Advance this person to the next round?** Yes **How were their technical skills?** 3/4 **How was their problem solving ability?** 4/4 **What about their communication ability?** 4/4 > Areas of Strength: > - You have a systematic and knowledgeable approach to problem-solving which basically guarantees that you'll be able to make progress on a question. > - Has a solid command of chosen language. > - You communicated your thoughts and actions enough for me to not be worried. > > Areas of Focus: > - You should practice looking at code and solving the problem from a fundamental level so that you can come up with more solutions. > - When walking through code manually, actually look at the lines of code line by line. #### Feedback about Digital Raven (the interviewer) **Would you want to work with this person?** Yes **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 > I think that was one of the best mock interviews/interviews I've done. It was super helpful, and the feedback was exceptional. I have no real suggestions on what could be done differently. I will definitely try and book again! ### Interview Transcript **Sensible Bassoon:** Hello. **Digital Raven:** Hello. **Sensible Bassoon:** Hi. How are you doing? **Digital Raven:** Not bad, not bad. How are you? **Sensible Bassoon:** Pretty good. **Digital Raven:** Um, all right. So I'll be giving you a mock interview today. So I'll be asking from one to three questions most likely two questions. So I can go ahead and just start giving you questions. Or you can go ahead and tell me like, oh, like, what kind of like positions or level you're looking for? Or you can just straight up tell me: Oh, or like, specifically, what companies if you if you know that I can, I can calibrate that way. Or you can just straight up tell me like, Oh, I want an easy and a hard, or I want two mediums or something like that. And then like I can accommodate that way as well. **Sensible Bassoon:** Sure. So currently, I'd say like the two next interviews that I'm kind of focusing on, that are coming up pretty soon, I'm going to so yes, first, the level. So I have about like one and a half to, you know, less than two years of experience. After graduating with my CS degree, I'm mostly interviewing for SWE positions, sort of SWE in ML positions, since I worked as a machine learning engineer. But the I have an interview with LinkedIn, and then an interview with Facebook, both for SWE and ML slash ML infrastructure positions. As for difficulty of questions, I guess, I'll leave that up to you to decide. I just kind of wanted to sort of be, you know, a standard interview that you might want to sort of expect and see if those those companies. **Digital Raven:** Yeah, for sure. Yeah, I think I think I think if you let me decide, like the questions based on like, company and level, that's what that would be way more helpful to you. So you said LinkedIn, Facebook, you have around like, 1.5 years of experience, it's cool. I think I have questions for you, for sure. Cool, are you familiar with streams, and how they work streams? Like, basically, there's an object that like, people can keep writing to. And then like, like, a subscriber can like, keep just like grabbing from it. **Sensible Bassoon:** Um, sort of what really, I don't have too much experience working directly with sort of stream based data. I kind of, yeah, I'd say I have minimal experience, but I understand. Certain, like, I guess, some basics, I guess, regarding that, but but not much else. **Digital Raven:** Okay, that's, that's fine. Um, could you go ahead and change the editor into the language of your choice? Python? Perfect. Cool. So I'll give you this one first. And like, feel free to tell me like if you've seen the question before, obviously, this would be way more helpful to you if you've never seen the question before. So and then, like an actual interview, you're trying to pass this is like a helpful session. **Sensible Bassoon:** Right. Cool. **Digital Raven:** All right. So I'll paste my question down here. So given an array of birth and death years, an array of tuples. Basically, each tuple represents like when a person was born and when they died. Given an array of such tuples, I want you to return to me a year that has that had the highest amount of people alive during that year. And you can assume that no one dies before they're one. So like, we're here is always better than that. I mean, that's your is always greater than birth year, and like it's ab, BC. And you can... Yeah, and for example, in here, in this example, there were three people who were alive during 2005. But there's no there's no other year that has more than three people or even three people in this in this example. So you should return 2005. **Sensible Bassoon:** Okay. Sure. So, I've seen a problem that's like sort of similar to this, but I think it was less complex. I think I actually encountered a problem that was very similar in description on an interview that I had recently. **Digital Raven:** Does it? I mean, if you've already seen this course the question or seen a similar question, we, we just talked about how you would solve this question, and then we can move on to another question. **Sensible Bassoon:** Sure, that would probably be better. Since I think I wasn't able to solve it completely optimally. I think I was a little bit close. But I got kind of caught up on implementation details. So if maybe I could even describe that problem, because it's extremely similar to this. But let me see. So basically, the problem was the same description similar in the sense that like, there's a set of tuples that reflect intervals, but it's mostly it's regarding meeting room times. And furthermore, that you're supposed to return the single hour in the meeting room time that contains the most amount of people in that are currently overlapped on that particular time, which I think is quite similar to this problem, in the sense that you're just returning the year with the highest number of overlap. Yep. Right, very, more or less identical problem description, the way I kind of went about solving this problem was using a heap. And the idea of using a min heap is that, essentially, so the idea is that I'm going to add in intervals of the end dates into the heap, first, I will sort the array, so I'm going to sort the array by the start. But the first key in the tuple, the idea so that we have some sort of, it's just so that basically all of the... it helps us so that when we're making an iterative pass through this array, then we'd sort of be able to make comparisons between the last are sort of the end interval of this current value, and then compare it to the beginning interval, this next one, and we can sort of make a comparison like for example, if this value is greater than or less than this or greater than or less than, like the heap, then we can sort of make decisions based off of that, once we sort by the first key, since it sort of kind of allows us to align these, these numbers up nicely. So... **Digital Raven:** So you, you, you sorted the array by the birth year for the median part time? And then and then you would push the death, year. Then he, and then whenever you press a new, like, a new birth year, you would like process all of all everything in the heap that like... **Sensible Bassoon:** Right, the idea is that if I find a birth year, that is, if I find a birth year that is greater than the value, the smallest value in the min heap, which I can just check in constant time, then I would want to replace the I would basically want to remove the item at the top of the min heap or the minimum value, and then put in that new end interval or so that that new start interval. Oh, sorry, I want to put in the, the end date of the of the one where the begin date was greater than the min min value on the min heap. Does that make sense? **Digital Raven:** Well, I feel like you, you can. I feel like there might be cases where that wouldn't work depending on how death years and like, play out. I think like as long as you process the like, if you had just like, sorted like the birth years from the beginning, and then add all the death years from the beginning, then you can just keep you can just keep processing death years instead of having to worry about adding it back into the heap, right? Or you can just add it back into really, once you're done processing that, that death years corresponding birth year. Because you'll need a condition to add into the heap. I feel like you'd have needed to add it into the heap no matter what. Right. But again, what problems are slightly different. So... **Sensible Bassoon:** The thing is, is that I would return the length of the heap at the end of the problem. But that doesn't exactly solve the year and quantity or like the year that has the max, it just would tell you. Oh, it just tells you the number of overlap. Or I guess... **Digital Raven:** Your question, it would have was meeting her up, sorry. Yeah, the number of meeting rooms that you needed in a year, it would have it would have like, returned like, oh, the highest population that a year has experienced? **Sensible Bassoon:** That's correct. So I'm not exactly sure yet on how I would modify that particular approach to accommodate for this condition where we need to find a particular year. And I think that's kind of where I would, because kind of stuck. Thanks. Okay. **Digital Raven:** Yeah, um, so you already basically have it. So basically, you would just keep like a population counter, whenever you encounter a birth year, you would just increment the population counter. But before you do that, you go through everything in the array that is, in that in the end, you remove everything in the heap that has was you remove everything in the heap, that was that was less than the current year, and then you would like, increment the counter. And then when you were like moving the death, also decrement the counter, so that way, you can keep track with the population. And then when you and then you keep track of like a max population variable, and then when that maximum population variable gets set, you can also set the max population year. Okay, cool. Um, **Sensible Bassoon:** Cool, right? Yeah. So I see where you're going, would you like to see me if I like, if I wrote out some code that, you know, I already have the sort of pseudocode in my mind, but... **Digital Raven:** I think more useful to you if you saw like, newer questions. **Sensible Bassoon:** Yeah, sure. Sure. Sure. That makes sense. **Digital Raven:** If we had time, I would love to see you code it I love it. I love watching. Oh, sure. You as useful to you as possible. So okay, well, this this this question is a little, like convoluted in terms of like, I don't know when that happened. And then here are the restrictions. Basically, you're given an array of strings representing a sequence of fruit trees. So it could be like Apple, Apple, banana, apple, apple, orange, watermelon, or whatever. Watermelon, those don't grow on trees. But and you have two baskets, you and you are to pick fruits. Basically, you want to find your to pick fruits from the tree and then put them into the baskets, your goal is to return the maximum number of fruit trees you can pick from, given the below restrictions, you can only have one type of fruit in each basket. Okay, so in the example above you like in Apple, banana, orange, you can only like either, like, pick from Apple, the apple tree than the banana tree or the banana tree than the orange tree. And once you start picking, you can't skip a tree and then keep picking it. So basically, if this was my thing, right? I would still return two because like by the time I picked this apple I wouldn't be able to pick this apple because I had to go through like two other types of trees. Basically, it has to be like a contiguous sub array. **Sensible Bassoon:** Okay, okay. **Digital Raven:** So basically, it's just like, find the maximal sub array, like find the find a contiguous sub array with maximal length that has that has like, two elements in it. **Sensible Bassoon:** Okay, okay, so my initial thought here, so I, okay, I would say that I have seen this problem before. I've never I don't think I ever solved it, though I just looked at it. And then I remember this description. I don't think I recall what the solution was or what the correct way of going about this is. So I'd say more or less is equivalent to a new problem. So cool. All right. So my initial potential thought about how to go around this problem would potentially involve using some sort of additional array. I'd say that's one thought. And I think I would, what I'm trying to say is that this would maybe go towards dynamic programming. Whereas an alternative would be I use something like a sliding window. Okay. So, right, so I think I can't. So normally, before I would approach something like dynamic programming, I'd have to solve some sort of idea regarding how I would want to recurse about the problem. But I don't have a direct idea about how to do that yet. So I would just at least first look at this idea regarding a sliding window, where my approach would just be that first, I'd want to constrain the time complexity to O(n), so that as I make an iterative pass, I maintain something like a hashmap, or maybe like two pointers that expand outwards, like an array. And if I exceed something like, yeah, I guess that kind of makes sense in the sense that the condition that we're trying to do to make sure that this particular window is valid, is that we make sure that there are only two types within that particular window. And at every time we expand the window a bit more, we would need to increment the maximum length that which is our return value. So right? So the idea is that we'd have a max length, okay, so right, so I'm just going to write some, I guess, like rough pseudocode. So I'd say like for i in the array. So I think we definitely need we will, obviously will need to have a max length. And we also need to have some sort of hash map that handles some things. So let me just think of how I want to do this. So I'll just call it H, to refer to that. And, okay, so if I'm at a, so I'm going to say that, I would maybe just start at the first index, and then look left and right. Since if I'm at here, there's nothing left. So if I was at this value, banana, if I look left, and it's Apple, then you'd have apple and banana. So that that already maxes that they're already maxes out everything that we can use. If I went right, then this would be a violation. So then, right, so the idea with that would imply that we would have left and right pointers that start at the ith value. And then so if I would, yeah... **Digital Raven:** I was gonna say, it seems like what you were explaining to me is that you were like, basically going through each prospective, like element and say, Okay, what happens if I say this must be included in the final result? And then you'd like expand that window out that way? And then you do that and check. But that's not really slides window, is it? Because like a sliding window you're saving throughout? You're just like moving a bounce. But right, this one, where each element, you're creating a dynamic window. So right. Yeah. So I would, I would, I would think more about how you want to structure your sliding window approach. **Sensible Bassoon:** I see what you mean, okay. So if we were to start at every single value, and then expand outwards until we have a maximal value, I think. Right. So I think due to the nature of the problem, meaning that we need to we need to have a contiguous sub array, it means that we would definitely have to look to adjacent values. And then we can do something like saying, since banana is adjacent to Apple, we have to add that as our second bucket. And then if the next value after that is not within apple or banana, then we simply just take a snapshot and say is that greater than max... If so, then we set That is the new max value. And then we just keep going, right? Because I think there'd be no reason to go backwards left if, if I was at this ith position, I've already taken a look at this banana Apple combination before. So I think I'm not sure if that's brute force, but I think that's O(n^2). Where, basically, if I was an i, then I would then look next to me, that's orange, I go to here, I noticed that that's not orange or banana. I just say that's max length equals two still, I then when I get to orange, you know, then I see Apple, and I see orange, and I see Apple, and then eventually, I know for sure that that's the max length. And then actually, we don't need to go... If we find that these two for let's say, we find that this is a max with this updates max length, we could just continue the ith pointer from the end of that particular window. Yeah. Now, let's say there was another value here, like banana. Think I would want to actually continue from this, this point, not this point. So I wouldn't do something like restart the i plus one, but maybe I'll just start off at the point where this particular window ends, so that I can at least count this. This one here. Yeah. Okay. Does that sound like an approach? I should try? Or would you prefer that I optimize something like that? **Digital Raven:** I mean, so basically, what from what I've, I've, from what I'm understanding of what you're saying, it seems like you're you're it seems like you're doing fine, it seems like you're gonna do O(n) time. **Sensible Bassoon:** Right? That's correct. Yeah. Yeah. So So yeah. I yeah. Because if I'm, if I'm moving, so I meant to mention that after mentioning the this, that I would move it and is that in each case, no matter what, I would always move the i after a look. So like, if I just see Apple banana realize that that's not greater than max length, I would just continue starting from banana, and then so on, and then check banana orange, realize that's not that, you know, maybe that's the you know, maybe there's some other window that's max length, and then I would just start off at this value, then at Orange, right? **Digital Raven:** Oh, well, then, well, then you would be it would be n squared then. Because like for one. For each one, you're you're restarting the window, you're resetting the window. Because like, if you go here, if you look forward, and you go here, and you go here, and then you just reset the window, and you're looking for. Yeah, then it would be n squared. So instead of like looking for, so what, what the normal structure of like a sliding window approach would be, would be, is to like, in the loop, you extend... you extend the right end of the window. **Sensible Bassoon:** Yeah, as max as I can, then, until it's invalid. **Digital Raven:** Yeah. Well, you extend it one at a time, right? And then, and then it's invalid, you shrink the left until it's valid again. Right? Really? How is usually how, like sliding window closes work. **Sensible Bassoon:** Oh, okay. Okay. So that in that case, what I could do something like is, if this was left, right at the initial point, I can move right. Up until this point, I checked that the window is valid, which it is, and then it can make a comparison to max length. And then when I get to this point, I realize that it's invalid. So then I just start moving left to this point. And it's valid again, check links, and then so on and so forth. Until I think that would then do that, right. **Digital Raven:** Exactly. **Sensible Bassoon:** Got it because they like so. **Digital Raven:** At most n times, and then l is never going to be greater than R. So it's going to be n. **Sensible Bassoon:** Got it. Okay. So I'm gonna go ahead and try and implement this. So if that's all right. **Digital Raven:** Yeah, go ahead. Okay, cool. **Sensible Bassoon:** In this case, I think let's see. I'm just trying to think of whether I want to do a while loop or a for loop. I think since I'm shifting pointers around. Maybe I'll just do a while loop for now. Okay, sure. So I'll say, while left I might not need to try... The last point of I'm just going to write this in case a while left, greater than equal to zero and are less than length of the array. So then what I'm going to do is say that. Okay, so I'm going to have some sort of... **Digital Raven:** Yep. When will the first condition ever be false? **Sensible Bassoon:** Yeah, that'll that. Sorry, that'll never be false. Right. So. Right, so that so in this case, I'm just checking if the right is less than the length. Yeah, I'll try and write it to that, it won't be a case where like, left will exceed right. So I don't need to do something like left less than right or something. **Digital Raven:** It less ever become. Even if it equals right, then like you already your thing, it would have been like, your window would have become valid before ever before L ever reaches R. **Sensible Bassoon:** Right, right? That makes sense. Yeah. Okay, cool. So let me go ahead and maintain a dictionary that would be looked like this. Let's see. So... actually, I could just maintain a small list of links to reflect my buckets. She'll just say, bucket looks like that. What I could do is something like initialize right to the first point and then populate the bucket like this. So that, I'd say array L, then array, right? **Digital Raven:** Sure. **Sensible Bassoon:** And I can obviously add as you know, a condition at the top saying that the the length of the array must at least be two before we can do any of this processing. That those are just the edge cases we can handle when we're done. So then, yeah. **Digital Raven:** Yeah, in like a function that it's easier to like, block. **Sensible Bassoon:** Yeah, yes. Count baskets. Just count fruits. Yeah. Then, okay, so then, well, right, is less than the array. Okay, so what I want to do is, I want to check. Okay, so the condition obviously, that we're checking is that we have unique values. So then. Okay, so actually, maybe it would make more sense if I maintained a set and I can just check the set length. Yeah. So so I can do something like this. P dot add this... so right, so then, if so, not exactly sure how I'm going to organize this yet. I just need some I just need some time to like just try writing some things then. Yeah, it helps me think a bit better that way. Yeah. Have e is less than two to say right plus equals to one else, right plus equals to one. And then so I certainly need to add in new values. So if I did that, then I would do something like b dot add the array right. Else we need to do l plus equals to one and we need to remove the dot remove the array that was at the previous l so we can't we got to this first. So it would be like the dot remove Oh, and then we move it forward. Then when it comes to the top, we don't need to make sure that it's valid. So then, right, so well, are both sorry, keep doing well. Yeah, I'll bring... Okay, so then you remove the left value increase left. Okay, so that First and to move this. So essentially the point of that is if I removed that one left would be there. Okay, okay. So we need to also check that the, so we need to check the distance. So if r minus L plus one is greater than or greater than the side say x fruits to zero is greater than zero. And this we say that max fruits equals to the R minus L, O plus one. So, okay. All right, so then, if the length is is that then, right, so I'm just gonna try and walk through my code really quickly, in my mind, and then see what I'm missing. Because I think I'm missing something. So or something's not working correctly. So then. **Digital Raven:** I mean, I see I see two bugs. Well, I mean, of course, other than like, the fact that you didn't return max root after the loop. **Sensible Bassoon:** Right? Yeah, yeah. **Digital Raven:** That doesn't, yeah, we get it. Other than that, I still I see I see two bugs. We're both logical. None of them syntax. Right? One of the one of the... **Sensible Bassoon:** Okay, right. So I think one of the bugs I might have in my mind is that it's possible that the, the left item that I'm pointing to is not the one that is the one that causes the violation. But let me just see, what's what am I? So okay, so if I just start off at the top, and I had my set here, but have Apple, banana... **Digital Raven:** Then we can say AB Oh, and whatever for now, because like, okay, typing, like to sample input is going to be like, right, time consuming for you. Yeah. **Sensible Bassoon:** So then, if the length of b is less than equal to two, which is correct, then we're going to move the right pointer. And we will need to add that new item. So it should just be Oh, then we get back to the top. Okay. This is a problem. So yeah, so definitely can't be there. If it's less than two, then we can take a look at least. Right? So then, if, okay, so in this case, it's not equal to not equal to two, we need then need to move the left pointer. So we're going to remove the left item. So it should just be B Oh. Left is here. Right? Is there. And we're going to go back to the top. Is it less than equal to two? Is it better than max root? It's not, then we're going to move right? **Digital Raven:** Sorry. Oh, yeah. Um, what did you just say. **Sensible Bassoon:** So yeah, basically, sorry, I forgot to mention this, but max fruits... **Digital Raven:** No, no, no, that's fine. But. Oh, yeah. If you, but are you actually comparing that? **Sensible Bassoon:** Sorry. I could just do something like so I can just do max fruits. **Digital Raven:** Cool, right? Cool. Cool. **Sensible Bassoon:** So at any point, we know that it's valid we can check so then right so then now we want to move right. So right next rule is to at this point, so right minus left right was at one left was at 01. minus zero is one plus one that should be to some extra it was two at Apple, banana, banana, orange, it was also two doesn't change max fruits. We then move our over here, we add in the new value. So when you add an apple eventually it'll reach this willing to remove the item at the left. So right and then it'll be... Oh a and then left pointer gets incremented, right pointers still at the same position. Do so then we reach this condition, Max fruits is then still the same, we made we moved the right pointer, we add in that new item, it was already inside there. So then B will remain at the same length, we then undertake a look at max fruits update, and then I think that would at least solve for this particular example. Because even when it reaches this point here when left is over here, okay? **Digital Raven:** It... Keep, keep going. Like even after you've like reached here, let's say like, right was here, and then left was like here, you've already had your max equal to four. **Sensible Bassoon:** Right? You would then reach this line. So this is the max, this is when max reads becomes four. And presumably when right as there, and then right gets incremented one more time, then the banana gets added. So then this gets added in. So it would be B. And then we would reach the top of the while loop again. In this case, the length of B is not less than two. So we need to remove the left items. So orange gets removed. **Digital Raven:** Right? Orange gets removed. **Sensible Bassoon:** Yeah. Oh, right. Right. So in this case, we need to put the left pointer all the way to the point where right is in that case, so... **Digital Raven:** Well, do you because, like, you only want to shrink this until you want to keep incrementing until... Okay, so maybe. **Digital Raven:** Yeah. When you're when you're keeping a set, right? You're, it's very easy to like, keep track of like, what is in there? **Sensible Bassoon:** Oh, I could either build a secondary 2d matrix that I can mark off as visited. I can potentially modify values that are already in the array. Yeah. Yeah. So I think my only concern about modifying values inside the array is that if I do multiple passes, that I don't do something like overwrite a value that I would need to check again, or something. Like if I flipped if I did something like if there was a zero here, and I flipped it into a one while modifying in place, then I would never... **Digital Raven:** Oh, yeah, yeah, this, your depth first search is not would not include like the flipping. Right? Okay. Yeah. What will happen later? Oh, okay. So I do have to go to a meeting in like, short minutes. But But I can tell you. Yeah, first of all, great, good, very good stuff, your understanding of your, your language of choice is great. You have a very systematic approach to problem solving, which is, which is like, something that like, not a lot of people can say, and I think that's going to be a huge strength for you. And you're here two approaches I've seen too, this is like when you're marking something as visited when you're like depth first search, and you can just like, have like a label, right? And then once you've visited, you label it, it's like, and then in a hashmap, you have you can be like, Island a is like size. 10 or nine, right, nine right now. What Yeah, and then Island B is like, blah, blah, blah. Or what I've seen someone do like in a recent interview, and I was like, I thought that was so clever, is that just update you every time you start exploring a new island, you create an object. Okay. And then you set each value to the same reference of that object. And then at the end, you that object will hold the size of the island. And then at the end, you can just **Sensible Bassoon:** Oh, that's really smart. That's pretty cool. Yeah, I've never thought of that's really cool. Yeah. **Digital Raven:** We did that. I was like, Yo, this is amazing. **Sensible Bassoon:** That's a really, that's a really smart idea why I never thought they could do something like that. **Digital Raven:** Yeah, it's like it opened up my mind. But oh, and the edge case I was I wanted you to think of was myth it was. If you're array with like, this, where if like here, if you look here, get size like seven and you look here and get size seven? A lot of people... Okay, yeah, a lot of people don't think about, like, over counting. Like, it could have been one island, at their boat that they're surrounded by. Right, you know, right. Yeah. **Sensible Bassoon:** Okay. Yeah, that makes sense. Yeah. **Digital Raven:** Well, it was good talking to you. I'll leave I'll leave my feedback and advice written so that like you can, like you met at your own pace. Sure, instead of like just talking at you. Well, good luck at LinkedIn, and Facebook. And if you get Facebook, hit me up because I'm a I'm a I'm a software engineer there right now. **Sensible Bassoon:** Oh, awesome. That's cool. Awesome. Thank you. Yeah, definitely. **Digital Raven:** Yeah, I made sure to ask you questions that would like help you towards Facebook. **Sensible Bassoon:** So Oh, great. That's that's Yeah, that's fantastic. Google. Sure. Yeah, have a good meeting. I don't want to hold you too long. Yeah. **Digital Raven:** No worries. Thank you have good luck. Have a good day. **Sensible Bassoon:** Thank you so much. Bye bye.