Python Interview with a Facebook engineer

Watch someone solve the fruit into baskets problem in an interview with a Facebook engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

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?

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?

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: Yeah, because I want this to be useful to you. This is not for you to impress. This is for you. Yeah.

Sensible Bassoon: Yeah. Yeah. 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 B 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, oh, I think I'm saying. Okay, as you were saying, so, I get it now. So So basically, if I had this, if I had this given array, and I just had like orange, apple, then this, this would be the solution. It'd be four.

Digital Raven: Yep.

Sensible Bassoon: Got it. Okay, so right. So I want to return max fruit trees from that restriction. 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 you know, 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 realized 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: Yeah, 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'd 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 here? Because this? Yeah, when l is? That's the point it becomes Right, right. Let's say another apple here. Right? You don't know that, like, l should have been right next to where l? R is, right? Yeah. You basically got to figure out like how to keep track of like, Oh, I'm removed this, but there's still like another orange in there. So like, Can you keep track of that?

Sensible Bassoon: Okay, so if I removed the orange here, and right was at banana, then. And if we had these two apples added in? The idea is then. Oh, right. So. So the idea is, then we want to increment up 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: Yeah, check it in. Right as we light up, right?

Digital Raven: Well, no, because like, when, if you remove it, once you're removing it from the whole set? Um, oh...

Sensible Bassoon: We want to right? Maybe you'd want to hashmap but then leave a counter on the hashmap. So cool. So that way, we would actually know how many oranges are left. And so we can keep incrementing until the until the count equals to zero of that particular item. Cool. upgrade. So yeah, so. Right. So okay, so I'm trying to think, do I want to decrease the counter of this left pointer until zero or? So okay, so I'm just thinking about when we're in this condition here when it's an invalid. Set. So when it's invalid in there, do I want to decrease just this value until it's so he keeps shifting l until and every time we encounter the item that was at l? We can decrease the counter or...

Digital Raven: Oh, so that your input could have easily been like this? Right? Right. So like, l could have been here, right? But... You want like, like, you still want to remove all the oranges because like up to here apples still nice banana, but you're still like, basically, I think you want to remove until you only have two fruits again. Oh, okay. Okay, because that's the definition. Yeah, right.

Sensible Bassoon: Right, right. So we want to remove until only two fruits are left again. So if... Okay, so this is one fruit at count one we have... Okay, so... I think what we also need to account for is that with this new hashmap that as we expand, we need to increase the counters as the right value moves. And then as the left value starts here, we want to move the left. Oh, okay.

Digital Raven: You see?

Sensible Bassoon: Right? So you want to keep moving left until until one of the items that were adds becomes zero, and then the length of the keys becomes two. And then I think then we're okay. Right?

Digital Raven: Exactly. You just decrease, you just decrement you move L and new decrement counters until one of them whatever one hits zero. Once it hit zero, you delete that key from the hashmap. And then now that hash map is your set.

Sensible Bassoon: Right. That makes sense. Okay, so if I switch this into a hashmap? I'd say this. So I'd say then become equals to one. I would also assign this one equal to one. I can probably clean this up later. And that's fine. Don't be worried about it. So then I'd say, I'd say...

Digital Raven: Sorry, for your input there, right? Yeah. Um, let's, what if my input was like...

Sensible Bassoon: Oh, if there were the same items, right? That's quite possible, right? So okay, so in this case, we'd say... Okay, I'm just trying to think of a slightly more elegant way to initialize then. So you see that if it's less than two, right, so I don't maybe I just don't you don't need to do this. I can just start off with the pointers. And then I'd say that, yeah, if it's equals to this, we'd say plus, so. But if array are not in B, then we'll initialize it to one else we'd say. I'd say lF. Yeah, to just say else, array. B array r plus equals to one. Then we obviously need to also check here. So if length of V dot keys is less than equal to two. So then, actually, no, you can just do length on B on a dictionary, then yeah. In this case, we want to say okay, so we can just remove these so it's a while left is. So we first take a look, we need to hold the value. So I'll just say init val. Or, I'll say l Val equals to a array l so I'd say while sorry. It's a while... Is that still...

Digital Raven: You're not sure? What you you're not sure that's what you want to become zero, right?

Sensible Bassoon: Oh, right. Yeah. So you want to move up the left pointer and just decrease the counters on any item and if it becomes zero, right, so then, so while L is less than r... If you just do something like a B array, oh, you know that exists, we need to decrement it by one. And say if b array Oh equals to zero and we'd say oh, maybe not less than r we're actually wanting to check to make sure that the length of keys of b is less than a while it's still greater than two cool bytes then we're gonna say B of array as we just say, delete B of array. Cool. Then right? I think just deleting that, then it becomes two again, it becomes valid. Let's see. Would you like me to walk through an example again, or come running?

Digital Raven: I think i think i think there will be some cases where your code doesn't work here. Okay. Yeah, I'm actually not sure yet because I haven't like walked through it in my head yet. But like I think there's a case where your solution doesn't work right? Yeah, can you can you...

Sensible Bassoon: Sure. So do you want me to just go through this example?

Digital Raven: Or no, I don't think we were exposed that it's mainly it's mainly checking this right that is get your problem. Because like because like if you're at the last if I'm thinking because like r so like, what? For example, if this was like, This is whatever the input was, right? I'm just gonna... Yeah, these aren't pretend these are actual like letters. Yeah, we'll see like your final solution is actually here is actually at the at the last thing like includes the last array element I'm not sure your code will correctly do that. Because like when you're here you you in your while loop when you're when you add this and then you're shrinking... I think you might be good I think you might be good you're good you're good. Okay, yeah. Yeah, it's just for some reason this code will still work even without this if else like this. Oh, okay. Like even if you even if you hadn't done like this your code still would have worked even if it was like this... Well, this max fruits would have had been had to been check later. Oh, yeah. I think there are some because I don't think you're checking max fruits at the right place. Are you? It's because like, what if what if max fruits? Yeah, okay. Cool. So what I was was I was saying before make sense. Like if your thing is at the last, let's say your final thing is like let's say it was... Oh, you be a be okay. You check, you calculate max fruits at this point when our before our team it was added was became like you want to are so your maximums would have been two and then you added are to one and then you added the thing to the array. But then you never calculate max fruits again. So you would have missed you would have missed max fruits.

Sensible Bassoon: But what I then what happens is that B was already inside the inside there, and I simply increment the counter. B would not increase in size to something greater than two because the key already pre existed, right? And then when they just come back to the top and then check this again, because it's still less than equal to two.

Digital Raven: Well, not if it's not, not if it exits the loop, right? Because like if this was at that level.

Sensible Bassoon: That makes sense.

Digital Raven: Yeah.

Sensible Bassoon: I see what you mean, okay. Okay. So...

Digital Raven: You, usually the structure of like a sliding window thing is like, a loop structure, and then within the loop, expand right once, and then another loop shrink left until valid. And then right, then like, if you're, if you're checking at, so for example, let's say you're looping, right, and then you're expanding, right here, you're expanding. Or you're Okay, first of all, you're checking, then expanding, or you're shrinking, right? And then it will loop through and keep the same structure. Right? Um, right, but always want to check last in case like, these two operations gave you something.

Sensible Bassoon: That makes sense. Yeah. Yeah. Okay, so, okay, and so in this case... right. Because like, because I think the else protects this from checking an invalid window, right?

Digital Raven: Yeah. This actually, this if else actually exposes it, to being able to check an invalid thing. Right? Cuz like, if B was already to be was already two, then

Sensible Bassoon: Oh, right. Oh, okay. Okay, yeah.

Digital Raven: Then this, this B would have like three elements. So which is why you... Okay, there we go. You don't actually want to fly. Because you want to like, make sure by the end, by the end, you're checking like, every, like, your window is valid. So yeah, I guess get just get rid of it. Okay, we got there. But cool.

Sensible Bassoon: But that makes sense. Because then this would then shrink it accordingly. Yeah, but, but then. Right. So it moves forward by one. It's greater than two. Right? Yeah. I think that makes sense.

Digital Raven: Yeah. Okay. Oh, and I think there is like a slight bug in your... Do you see? Okay, cool.

Sensible Bassoon: Yeah, so I think maybe if I just started there.

Digital Raven: Well, I think negative one. Oh, okay. Okay. Because you're adding one at the beginning. What for our cause, like you're adding What are getting your own? Yeah, yeah.

Sensible Bassoon: So then check for edge cases, or? Yeah. Would you prefer that? Oh, yeah.

Digital Raven: I think yeah, we, you already discussed the space time complexity of this. I can, like ask you another question. You don't have to code it. You can just talk about how you would, because you can practice. But like, practicing solving a problem, like in front of, like, someone you don't know is like, that's, that's this right.

Sensible Bassoon: Right, right.

Digital Raven: Right. And so I'll give you again, tell me if have you seen this, okay. And I don't think we'll, we'll definitely don't have time to like, solve this one. But like, Okay, well, we definitely don't have time to code this one, but I think you'll have time to solve it. So basically, given a grid where ones represent land, zeros represent water and Island is a grouping of like, ones that are four directionally adjacent. So like, up, down, left, right? No diagonal. So in here, this will be, this will be two islands of size one. I want you to write a function, given the grid. It returns the size of the largest island if you were allowed to change at most, one, zero to a one.

Sensible Bassoon: Oh, okay. So yeah, I think I've looked at this problem. I didn't solve it, because I think this is kind of difficult. But the point, at least what I, so I definitely didn't code this in or anything like that. But right, so as far as when I was thinking about this, my general idea was just that. I think what I could do is like, Oh, right. So I could use an algorithm, I think, known as union find, or something similar to that to solve this problem. Because the idea is just that I would need to DFS for anytime I find a value of one and try and represent that entire, that sort of the entire island as some sort of quantity. So like, to me, easy if I could draw. But my idea is, I mean, maybe, yeah, it's just a space. Yeah.

Digital Raven: I mean, I guess you don't have to do with a form, right? You can just like type it as like this.

Sensible Bassoon: Oh, right. Right. Right. So if, let's say, let's just say that, like, any space that I include between the ones is just zeros. So if I did something like, right, so if I did something like this, and then what I would just say is that, like, I would build a count, for this particular Island, in this case, it would be like eight, okay, then this would be accounts like something like four, okay, then this would also be four, then I'd have to figure out a way where at any position that I'm at here, this is where I get a little bit lost is basically, at any one of these positions, I would have to be able to check in one of those directions. To see if there's an opportunity to jump to another island, if I were to flip to zero, so that I would need to sort of see that the distance between this point and so it would need to look something like to two spots beyond this single spot here or two spots beyond here. So what I mean by two spots is like, if there's a zero and then there's potentially a one here, you know, let's see if this actually became like a 10. At if I was at this point inside the island, that if I look to positions beyond that there's some sort of connection that could be made. And then furthermore, that if I was you know, basically this would have to account for all of the areas that you know, all of the sort of positions that I could be in on the only need to check the parts of the islands that are within the array and obviously, I couldn't check something that's out of bounds but but yeah, okay, so then what would happen is that let's see, I did figure out the logic to basically you know, basically, maybe I could do something like replace all the values within the island with that count that I found. And then should I find that sort of jump you know, let's say I might need to do multiple passes. I don't know this that's not I'm not sure if that's optimal. But basically if I did multiple passes, and I had something like this is 10, this is 10. And just assume that whole thing is 10 and then this is four and then this is four and then this is also four here. Essentially once I make some sort of connection that I simply re update all the values in that particular island with the sum value of the previous islands number so it'd be something like now 14 and then I no longer need to and then I'd also maybe update this islands number with 14 too.

Digital Raven: Would the resulting Island be 14 though?

Sensible Bassoon: Oh, yeah, you'd have to count the the distance gap so I'd say 14 plus the plus this distance. So at most one yeah. All right, so I'll have to add in. Don't need to add, or Yeah...

Digital Raven: There's just one is fine, because like the resulting size is 15. Right? But let's say, okay, so you wouldn't go and update it, but why are you updating it?

Sensible Bassoon: I'm updating it so that if I were to make a, I guess this is where it becomes pretty common, you know, in terms of time complexity would get really horrendous. And so I'd have to sort of think of a smarter way to do it. But right now, we're the reason why I'm saying I'm updating everything is that in another path, I basically do the same operation where I seek for jumps to potential other islands. And

Digital Raven: Right, but you're only allowed. You're only allowed to change at most one. Zero to a one. So like, you already a 02. Okay, okay. Like, there wouldn't be another pass. After right? That makes sense. Yeah, so like, in any path, you should consider any path like independent of each other. Um, okay. Yeah. And you only have growth.

Sensible Bassoon: I only need to consider rows. zeros. Oh, sorry. zeros. Okay. Yeah, yeah.

Digital Raven: Once you have like, this island, being like, oh, oh, somehow, you you did DFS on everything. And, and then union find. And somehow you were able to like, say, like, Oh, this island? Oh, from this cell, I can tell that it's this island. And like, this is the size of the island. So you can just like go to zero. And then like, add all the islands like that are adjacent to it. And then like,

Sensible Bassoon: Right, okay. Yeah.

Digital Raven: Yeah. Do you think of any edge cases?

Sensible Bassoon: Edge cases? So in edge cases, I would say, See, I had? Let's see. So if I did, see? All right. This is actually potential. Yeah, this is potential edge case, right? Where, in this particular array, if I flipped this one to a one? It would be the exact same values if I flipped this to a one. So...

Digital Raven: Well, yeah, but it's still very, right. Right?

Sensible Bassoon: Still, it's still three. So it's not? T. If it was all ones, I wouldn't need to flip anything. Not too difficult of an edge case to handle, I think maybe? Yeah. Let's see. Yeah, cuz we can just, we would know, the approximates we could we would know the size of the array. I can just have like an if statement that basically says that. If we have ones that ever counted up to the same size as the entire 2d matrix, then that would mean that everything's populated. There's nothing we could do. In another case, yeah...

Digital Raven: Sure. And you're in. I'm trying to think of like maybe whether this case will actually be applicable to you. But like, how do you plan on like, when you're union finding? How do you plan on keeping track of like saying, like, Oh, this is an island of like, grabbing the cell will give me an island of, Oh, this is an island of size one? Yeah, this is another one, like, how do you how do you can you think of like a way to...

Sensible Bassoon: Right so that's, that's another part of complexity that I'm trying to understand. So basically, the idea is that we want to make sure that a collection of coordinates belong to a particular Island, and that we can sort of check in constant time that any one of those coordinates is a part of one associated Island and not that we don't need to sort of like sift through an array or something like that. So naturally, that sort of lends me to thinking that this would be like a hashmap somewhere. Okay. Where the key. Let's see. So this is interesting. So we could do something like, even we could even map a coordinates like as the key so the XY value would equal to the key somehow and then. The key gets mapped to the pre designated value that represents that island. So Island one, or let's say, you know, this is zero, this is one, then this is not like, yeah.

Digital Raven: In your hashmap, right? When you're doing DFS, right, you're gonna have to somehow mark, when you're doing DFS, you're gonna have to somehow mark certain cells as visited or not, right? Yeah.

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.