Python Interview with a Google engineer

Watch someone solve the split array largest sum problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Split Array Largest Sum

Interview question

Split the given array into K sub-arrays such that maximum sum of all sub arrays is minimum. Given an Array[] of N elements and a number K. ( 1 <= K <= N ) . Split the given array K subarrays (they must cover all the elements). The maximum subarray sum achievable out of K subarrays formed, must be the minimum possible. Find that possible subarray sum. Input : Array[] = {1, 2, 3, 4}, K = 3 Output: 4 Optimal Split is { 1, 2}, { 3}, { 4}.Maximum sum of all subarrays is 4, which is minimum possible for 3 splits. Input : Array[] = { 1, 1, 2} K = 2 Output: 2

Interview Feedback

Feedback about Immutable Catamaran (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

Strengths: TC was able to reach a brute force solution to the problem at hand, with minor hints from the interviewer. TC performed well at the new grad level where they incorporated hints well into their solution. TC used the vertical bars approach pretty well and their code was pretty readable/easy to follow along. TC was able to answer the correct time and space complexity, and their efficacy was also pretty good. TC communicated very well their approach and key issues with the question Areas of Improvement: TC can improve their approach by targetting the optimal solution rather than brute force, by practicing more problems like this one I would recommend a Leaning Hire decision for new grad level

Feedback about Ferocious Sandwich (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 couldn't find anything to point out. I think you're a great interviewer, who understood my messy thoughts and tried to steer me on the right path. Easy to understand, engaged, etc. I also don't know if you came up with the question yourself or it was given by the website, but it showed me where I need to study more, so that's good too.

Interview Transcript

Ferocious Sandwich: Hello.

Immutable Catamaran: Hello.

Ferocious Sandwich: Hi. Hi. Can you hear me?

Immutable Catamaran: Yeah, I can hear you, thanks for coming. This is my first time on the platform so.

Ferocious Sandwich: Oh, okay, that sounds decent. That sounds decent but yeah. Thanks for trying this platform out. So this is going to be like a practice interview. So without like disclosing too much about ourselves, can you like quickly introduce yourself?

Immutable Catamaran: Yeah, I'm, I'm a new grad. I'm, I'm looking for work. I, oh, sorry. Emma has a dog as an AI. introduce myself to you, because I wouldn't say I'm looking for work. But yeah, I'm a new grad. I'm looking for positions with regards to new grads, front end or back end or postdoc positions. I've, I'm gonna be graduating in about four months. But I am interviewing. Just preemptively. So I'd like to have a have a position, you know, after I finished school. And yeah.

Ferocious Sandwich: Yeah, that sounds like a decent introduction. So just a quick intro about me. I'm like a mid level engineer at Google right.

Immutable Catamaran: Oh that's really great.

Ferocious Sandwich: Yeah. So yeah, I'm, I'm like, This is my third or fourth interview on this platform of some kind of new as well. So my main programming languages have been Java and Python. So if you're familiar with them, or you can probably start the question, but if not, if you wanted to C++ or some JavaScript, like that, that's also fine with me.

Immutable Catamaran: Yep. I've been practising the most in Python. So I think I'll go Python three.

Ferocious Sandwich: Okay, sure. Let's switch to that. Okay. Here we go. So let's get started with a question. Usually, the question starts for, like, the question is asked for 45 minutes, but let's just give like, let's give the same amount of time here. And then at the end, we can probably debrief saying that what went well, and what didn't go well, and things like that. Right.

Immutable Catamaran: Okay, thank you.

Ferocious Sandwich: Let me paste the question, okay. So give me one second. Right, so basically, your task is an array is given to you, okay, your task is to split the array into K sub arrays, right? Such that the maximum sum of all sub arrays is minimum.

Immutable Catamaran: Alright, minimum okay.

Ferocious Sandwich: So lets say for example.. yeah go for it.

Immutable Catamaran: Oh, sorry. Sorry. No, I just, yep. Wow, so let me just clarify what minimum is. And, um, I guess I'll look at this test case. 1234. And also, they give you k, and you have to split them in a way so that you don't have like, you have a minimum combination of them. I see. I see. So in this example, up 1234. Case three, and yeah, you want to, you want to put the one two together and the maximum sum of all sub arrays. Okay, it's four. Okay,

Ferocious Sandwich: yeah, this Yeah, this is a pretty challenging question. Right. So take your time. That's what I would say. So usually a Google interview question in onset are usually in this level. Right?

Immutable Catamaran: Okay, thats...

Ferocious Sandwich: yeah, go for it.

Immutable Catamaran: Gotta practice, gotta practice. Thank you, though. I. So let's let's just think of like maybe I'm going to think of an solution that might be super slow. But it would maybe work I would, how I would do it. If I had the three only had to divide into three sub arrays, what I would try every combination that could give me three sub arrays. Maybe I would try one and two. And then I actually, I would try. I would try maybe building the biggest sub array possible. And then, so I know if I have four elements in my array, and I can only build the array, then I just build my first sub array as big as possible one and two, and then I try three and then I try four. And then I will do 1314. And with my sub arrays being those individual elements that are left, I will keep going and I just keep track of my minimum possible values. And if I try every combination, I'd have something at the very end. Now to look at this time complexity, look how fast this runs. Let me just think about how, how fast or how slow this would run, how many sub arrays Am I actually building here? I would go through. So in my first example, I have one, my first summary will be one and two. And maybe I'm talking but I think it's also okay to just talk about how to type it out to just your queries. Yeah. So that, you know, that will be a first run, and then it'll be 1 and 3.

Ferocious Sandwich: Hold on, hold on, hold on, hold on. One second. Yeah, one, three is not a separate, right one, and is like picking like the submarines needs to be contiguous. Right? should either be 1234 or 1234. Okay. Contiguous.

Immutable Catamaran: My apologies, I should have clarified that as well. So I guess it would end up being my next, my next test would probably be doing once I realised my first ever race like to have a try first ever, like the one and I would have a second array be the maximum possible? And then so on and so forth just for this? Well, honestly, in this case, there are if I'm not mistaken, their only way, let me just write this out to my self. With their own, there might be only three subarrays, but let me just clarify. Yeah, there are only three sub arrays it would this one this particular. This particular case, it's, we only take take one pass to try all of them. If I might be mistaken, here, let me just doesn't look like there. If it's continuous then doesn't look like there's any other option. And I just want to make sure it's literally k is not like less or more than K just always K. Okay, it's always K. But that is okay, split the given K subarrays, so they must cover all the elements maximum or sub array. So achievement of minimum possible. Okay. Well, I'm going to while I keep this example, in my mind, I'm just going to think about the second case. I have I one, one and two. I would there's only two ways to break outside of contiguous arrays and 112. Well, okay, this is I guess I separate these. This is only two sub arrays mount. These examples are reasonably small. If I had bigger test cases, I don't think I'd only use one pass is what I'm kind of kind of convincing myself if k is bigger, sort of case. If the sample size is larger, and K is just tends to be, if I'm going to guess, like many more sample cases, yeah. So it will take not just one pass, but I'm trying to think of it would just take me more passes. I'm going to No, I think I just removed this and give myself maybe slightly longer. Slightly longer, sorry, sorry, it's a slightly longer array, and I'm going to give myself maybe a different key value, just maybe still make myself how many classes it would take. So let's take this and I take the count of three. And you know, like first, as I kind of said, I would start with the maximum possible so this will be four, and five, and they will leave me with six. So and that's the maximum possible but in this case, you can see that don't necessarily slide that first sub array downwards. I would have to try this next I would have to try four and five. And then I would have to try five and six before it have been exhausted. four and then five and six before you can start exhausting more cases. So yeah. How long would How long would this take me? In? If I, let's call this? It would be it would be. And to the, let me just describe this to myself it looks...five six for n times and two for every big every big sub saw sub array, I would have to break it down until it's down to one. It's is that without me it's, I don't want to say it's m to the n, but

Ferocious Sandwich: you can answer the time complexity in terms of k and then

Immutable Catamaran: in terms of k and n. Yeah, well, oh, with sense of n to the n, I'm just trying to talk to myself to think of it's N to N times K or

Ferocious Sandwich: so yeah, think about it this way. Okay. Say for example, you have n elements, right? We need to make K sub arrays out of them. Okay? How do we choose k minus one vertical legs, splitting lines, such that between two vertical lines there is one sub array? Like, imagine there is an array, you're exploiting the array by drawing a vertical line, right?

Immutable Catamaran: Okay. I have a piece of paper on me, but I do this a drawing window here. So I should do this.

Ferocious Sandwich: One second. Look at my example, right? So that just did this. Okay. So what for 123456? Okay, one such configuration is here, you draw a vertical line, okay, marking this array as the zeros array. And then the next vertical line to first vertical line, okay, is your secondary, and then the remaining is your current array. Right? So, k minus one vertical lines uniquely determine a sub bullet of the main array, right?

Immutable Catamaran: Yes, a split of the main array. Well, yeah, free drawing it like that. That's, that's interesting. For sure. I k minus ones play and what's a good way to do that? Okay, this is put together very sorry, one sec. So if I, I just want to see if I can just drop it one at a time and do a calculation but I'm not sure that would work we would like to both. Yeah, thank you. Just the talk out loud, I'm just thinking, give myself if I want to split them. I, I'm not sure if I would maybe add them all up and give me give myself a reference point to see what the maximum sum could be. Because I know subarray would have something smaller than a maximum sub maximum sum. I'm not sure if that could help. But if I added all these up in this, in this example, I would have six plus 410 plus 21. And I know that my sub arrays and not to say can't be it will be less than seven per se. Sometimes they're like They are it's because the arrays unbalanced. So you can have. So you might have some sub array like 2020 plus one plus zero or something. So I don't know if having some sound man dividing it accordingly would also work, I am going to discard that idea. I

Ferocious Sandwich: basically you are thinking about some sort of an optimal way to solve this question, right.

Immutable Catamaran: I'm thinking of a way.

Ferocious Sandwich: So, can you think of like a brute force way? Like, can you construct all the possible sub arrays, write all the positive case subarrays and then try to find the minimum.

Immutable Catamaran: Okay, okay. So going back to my original, some of my cases I left down there, I, yeah, I would. So I guess meet me speaking in the hint, you gave her vertical bars, I, I guess I would, I'd have two bars. Or in this in this example, I would have two bars and I leave them at the end. And I shuffle the left bar and I shuffle the right bar until it met the left bar. And then I shuffled my left bar, one to the left and an a shuffle my right bar, and so on, so forth. And that's it, those are like, in this case, two bars doesn't two pointers, but to two pointers to like shuffle a deck, I keep moving left until I get back to the very start. And then those, that's a way to generate sub arrays. And it feels like there's it's depend on how many bars there is. So if you just a one bar would move to the left. But yeah, if you had more bars, your second bar would move has to do a full house, it has to move through the list until it met the first bar again. So the number of loops is dependent on K, so that's

Ferocious Sandwich: okay, you're on the right track, you're on the right track. But instead of taking the value of K and iterating, like writing, like for loop K times K in our for loop, right? Instead of doing that, the can you think about where do we where can we place k minus one pass? Right? How many positions can k minus one bars take?

Immutable Catamaran: Oh it would be in this example? It would be k times k minus one over two probably wait actually. Okay, the first bar, the left bar it could be and 123454 different spots. And the right one could be an A once a once, one, one and then one only has one option for one case, and then two options and then three and then four. So that's total can. Can in this example.

Ferocious Sandwich: So basically what you were doing was out of n spots, okay? You're picking k minus one spots. So out of 01 so on up to n minus one, okay. You are taking k minus one numbers, right. So how many surgeries are that? Big K minus one number from the list of zero to n minus one.

Immutable Catamaran: If I had zero, zeros n minus one, picking k minus one numbers. Sorry, how are you saying? Sorry, your question was how many ways I can pick k plus one numbers.

Ferocious Sandwich: You have given us a number how many ways can you pick k minus one numbers from the array zero to n minus one?

Immutable Catamaran: It would be n minus. So the first the first bar would be n minus one ways. And the self so on and so forth would be n minus two, and minus, minus three. And until until one And so that and it's based on K so that's and

Ferocious Sandwich: sure sub n minus k plus one right.

Immutable Catamaran: Yeah. Wait n minus k plus one?

Ferocious Sandwich: Yeah. So, the last one would ideally be n minus k plus one right? That will be the total number of ways right? Basically n choose k minus one right?

Immutable Catamaran: Right. So, I say n choose k minus one,

Ferocious Sandwich: okay. So, that is the total number of ways programmatically how to figure out which are the k minus one slots or k minus one numbers, you can pick out of n minus one numbers, do you know a way to do that?

Immutable Catamaran: Know a way to pick to n sorry, so your question Can Can you repeat your question again?

Ferocious Sandwich: Sure. programmatically k minus one numbers from zero to n minus one list such that all possibilities are covered

Immutable Catamaran: I think I could do that. But how would I?

Ferocious Sandwich: Okay, I mean, like, one hint, I can give, you can go from index zero, right? at index zero, you can pick the first vertical path, or you can either pick the index zero as the first vertical bar or not pick index zero as the first vertical bar. Right. And every time you pick it, you can decrement the value of K. Okay, and then proceed to the next index. Right. So,

Immutable Catamaran: I so you're saying put a bar at the very beginning. And, and just

Ferocious Sandwich: No, I'm basically saying, start at the first index, okay, you can either put the bar in the first index, okay. Or you can choose not to put the first bar in the first index, right? There are two ways.

Immutable Catamaran: Okay, so I can make a beat between the first index and the second index.

Ferocious Sandwich: Yeah, yeah I mean you can consider it like that.

Immutable Catamaran: Okay, okay.

Ferocious Sandwich: So you can pick either to place the bar between the index zero and index one, okay, on Oregon, choose to place the first bar ahead of index one, right? At every i index, you can either pick to place the bar there or refuse to place the bar and then move ahead. Right?

Immutable Catamaran: Right.

Ferocious Sandwich: You have two choices, right?

Immutable Catamaran: Yeah, you can do it

Ferocious Sandwich: You can either do it there or you cannot do it. Right. So every choice you can make, can you like write an exponential function, which says like, if I placed it there, then I would decrease the number of bars to place and then recursively call the next index, right?

Immutable Catamaran: Increase the number of bars to play and then recursively call the next index. But okay. But you recursively call them sub array paths that index or Yes. Oh, that's what you're saying? Yeah. So you place a bar at an index and then you recursively call it sub array after that, and then you place another bar dive so that was what you were describing?

Ferocious Sandwich: Yep. Yep.

Immutable Catamaran: Yeah, until until you reach until you place all your bars. Yep. Basically. I could. Yeah. I could try that. Recursive replace your price. I just And then, so So yeah, you recursively call it on the, all the arrays to the right. And then what's like left is what you have on the left. And then you hopefully, yeah, I don't know what to do one once we once we come back from a recursive call, but at least I can place bars.

Ferocious Sandwich: Sure, at the very end of the recursive. Alright, once you have placed all the busts, you can you'll have an idea as to how much is the sum of each subarray? Right? From that you can pick the maximum sum and then compare it with the global minimum.

Immutable Catamaran: Yeah, I wasn't even thinking something recursively. I'd give myself a base case. If I had if I had, but say, Okay, if I had no bars, that means I'm at the end of my array. I I just, I don't mean to K is like equal to one I just clarify. just clarifying a K. One. Yeah, K is bigger than one a bakery one is less than n. Okay. So base cases, K is one, I would just return the error return the maximum, I would return the sum of that array. And I do I want to compare it to my global right away or compare it to? Or maybe I just returned? I just returned to some. Yeah, I just returned to some I think of it that was my base case. Let me let me continue to just in this in this case, it's just a super basic case, I'll return six. And that's my only case. If I had k, this case would be equal to two, I I guess I placed a place a bar so to speak in between one and two. Or I could not do that. So I was recursively. So I would have I would recurse. On the first recursive call would be two, and three.

Ferocious Sandwich: And K equal to one.

Immutable Catamaran: Yep. And k is equal to one. Returning five. Now what happens when I returned five to my original, maybe I'll put this in like a tab. What happens when I return my five? I probably have to check my one as well. And compare? Well, I have to at least at least compare one in five, maybe not for the list is not the best way to show up, but one in five. And then I returned the max of that. But then I have to check the other recursive call, which is which is the next option, which is three, and k is one and I return three here. And now I have now I guess.

Ferocious Sandwich: One plus two, even compared with three. Yeah.

Immutable Catamaran: Yeah, one plus two is three and three. And now I have well, I guess, I guess. No, I want to check. Do I want to put this in my do I want to add do I want to add five to my global now? I think that's really how global five and then you mean my apologies. Yeah. Go to min. And we just be max of this local local min are described describe it is local, this local man. So this I, this looks like and then and then I guess I have to at the end of all this. The answer would be, oh wait three. I apologize, my answer would be three. So this is the this is interesting, because this is admittedly the simplest test case I could give myself to just understand this. Now I just want to know I'm just like talking to myself. Like I just want to know what happens if I had k is more than two places one bar is not that difficult. But what happens if I have more bars? Maybe if I use this, this 1234, for example, and my k is equal to three, so I have to have multiple recursive calls. So I would have to my first recursive call, put the bar there, and then case equal to, and then I haven't reached the base case, because my case is not one yet. So I'm going to try doing this. And then I'm, I'm just going to talk about calls for the moment. I think my next, sorry, this will be k is equal to three, I put a bar k is equal to I put a bar k is equal to. K is equal to one and this is fine. I'm going to return array sum. So just use 234. That means my last one would be awesome. This will be four. This is something I would return. This will never return as well. And then I was

Ferocious Sandwich: Hold on, what is line 37. Why is it?

Immutable Catamaran: So sorry, I had two, three and four. So I put my first bar between two and three. And then I put my second bar between three and four.

Ferocious Sandwich: Hold on didn't you place your first four between one and two.

Immutable Catamaran: I put Yeah, I put this one here. And then for this one, I put it here. And then I have to try putting it here. Okay, I will have four. Yes. My apologies. I don't know that. This is just how many tabs there are. And then I think those and now how do I compare these ones? Oh, it's kind of like a It's not. It's like I actually maybe I should write this out to myself. Return seven, return four. And here, it will be sorry, to seven. And he would be five and four. And that would give me well, and then seven eyes and I wouldn't compare these ones. And then I send that back as my best option, given the bar at this place. Now how do I compare seven? Just it was my variable. I honestly just maybe have like a local, local min. Yeah, it was really just as like a local minimum. Yep. And then return five. And then what I discovered from this first bar, is that best option is five. Yes. How and then I keep an eye basically. Okay, this case, because it's three, and then I basically move my bar forward, and then repeat the whole process again. And then until my bars at the very end, I do my until my bars at the very end. And hopefully I'm keeping track of some stuff here. And then I am just going to I keep track and I return the minimum of these options given that the bar is index bars, and so insert an index and so forth. And then I return min of all that. And then I return the minimum of all that. So, and I think I guess the fundamentally that's what, what this approach would look like. How just, you know, just clarifying. Are there any other like cases that like edge cases? For example? If let's see, if we clarify k here and k is less than n and n, so n has to be at least one and k has to be at least one. Okay? So let's see what if f do I need to add at the very beginning that sometimes you don't have to but do an F and like is equal to One, maybe I just return this number, because you can't place a bar. So you would have to you wouldn't do a recursive call. So I do need the space somewhere earlier that just says that like, can I just return? Return nums?

Ferocious Sandwich: Sure something that says something like, Oh, yeah. So now that you know the approach, can you like, go ahead and start writing the code for this?

Immutable Catamaran: Yeah, I'm going to try doing that. Okay, here. Fine. We're just gonna case work for now until I found a bug. Okay, so let's, and then it's a ray of testing. So we're just going to call them Nums. Or array, and, oh, it just highlighted it. So I thought it was for some reason. Okay. Yeah, bases first. Yeah, just

Ferocious Sandwich: Ignore the compilation errors, like most Google interviewers won't care.

Immutable Catamaran: Okay, that sounds cool. Thank you. Oops, sorry, I clicked on something on my side, okay never mind. Length as length. If length is equal to one, I return a return the array. And now because I'm going to need some sort of second function. I am not running fully out yet. But until we find a better name. Now I just because my base case can't be my recursive function. So I want to do I place a bar? No, do I place a bar right away? And then call it? Do I do a for loop for my first bar and then call it every time? Or do I try to simplify it? And? Well, are they trying to simplify and put that all my function? If I have my k is equal to if I have my k is equal to one, okay, it's always at least equal to one. So you're always going to put a bar and so my n has to be two from here on in. So I that's maybe I, oh, if I had let's, let's say, if I had, say, Oh, actually, I need a K. They give us k. So I was the cur, I would Yeah, I would. I would do I want to put a for loop here or not? One second. Okay, no, I'd probably, I'm probably going to leave this here for now. And see if I really needed but I don't think I do. So this would sort of be what it would look like now. Now, in this case, what am I trying to do? Going back to my example, I first want to put a bar at the very first option possible and I want to loop and continue putting a bar down the line. I want to store all of my sums I get from moving the bar forward, I believe. So I for now, where do I want to start putting my bar technically like, or maybe just phrase it a different way that makes sense with arrays is that I want to chop off my first element and chop off the first to chop off the first 344 index in range. I'd start at one length, of length of array. Now is this. Okay? Yeah. And then I would have to and then we've talked in bars, but I basically do just have to recurse from here. some you know, I Yeah, so min, I call this recurse min maybe we'll leave that for now is equal to recurse array array arrays from index to the end, and then my it will be k minus one that is that now I didn't really put a base case here. I forgot, if k was equal to one, then I just want to sum everything up and send the incentive back. Now. I just I was thinking maybe there'll be a faster way to do it. But I can do this. Yeah, I think there might be some way but I'm going to do this for now. For index and range length of the array sum plus is equal to, yeah so this is the base case. And I'd have to reach return the sum one is only one option. So this is okay, for now. Just maybe could be changed, but I think it's okay. For now. For now, going back to my recursive min. I didn't have a sum. This gives me a cell. And now I need like some kind of like, local, Max. Local min. And what is their giant value? I should set it out? Well, I could I, maybe this was oh, I forgot about the tactically important markup here.

Ferocious Sandwich: Don't worry about it.

Immutable Catamaran: Yeah. So you know, I, maybe this isn't the best way. But this is my this is my this is my giant value compared to I know that. I know that says Oh, no, it's in my it's in my loop. That's on my list. But I know that I have to like at least go through the foil of at least one. So I'm not worried about returning infinite. So local min is now equal to min Kurzman now is this what I want to happen? See, I think this is what I want to happen. So I put my bar in the place I return the minimum they check it but the second place and I turned that minimum and so on and so forth. And I do want to return the local minimum now. This, I want to see if I be missing anything from here.

Ferocious Sandwich: Okay, think about like before recursing from index to the end, right? From the zero to index, there was a sub array. Okay, when you put a bar to the left of the bar, there was some sub array, right? Shouldn't that sum of that left time separate? Also be considered

Immutable Catamaran: Oh,yeah, there's no you're totally right. I forgot that when I was doing this I not only Yeah, my regular Kurzman just returns things from the left, but the actual comparison comes from the sub. So I need to have a sub array from the left. And, and and compare that to my sub arrays from the right. And it's only one sub array from the left. So I hope there's not like a super quick way. Is my for loop are in the right place. Or not. I guess I don't have no my I don't have to do like I can. Yeah, I don't have to do it that many times Correct. I could just do it once to have my left sub array up here. And my range would be up to actually no I do need in there because that's where I determine where my bar is. So my bar is here. So I have to base it off my bar which is over here. So, one signal for so far, I'll even know what the other way caught. I'm just going to call it day for now. It'll be zero. And so index and, and definitely need a sum here called, we're gonna call it less prime is equal to zero and less plus equals to array J. Okay. And then now I have a left sum, I have a rehearsed sum, and I have a local min so I, first I have to check first my max. Look. Nutrition we call it local man, but I do need

Ferocious Sandwich: It's fine, It's fine, I understand so.

Immutable Catamaran: Yeah, less sum, and recurse min. And then I have my variable, I want to compare my local min to my variable. That is how everything up. Now, now, am I missing any?

Ferocious Sandwich: Yep. So basically, everything looks good so far. Right? I just want you to think about whether we need to calculate left sum every time we are at an index, or we can calculate left sum?

Immutable Catamaran: Yeah, I would know, because you just have to add the end to it, you know that you're less than starts at the beginning. And you have to keep fighting it over, so to speak. So let me just, it will start at zero here. And really, I just have to, really, I think I just have to do one second. Left, some started zero. And if I if I call my recursive on my cutting out the one, then it's just as index says c of i. My index might be one off or one one left, one on one off or anything like that. But it's simply not I think I think this is okay.

Ferocious Sandwich: Maybe your index is a bit one off. So maybe add left sum

Immutable Catamaran: Oh, yeah. Yeah. Yeah, that's Yeah, that's true. That? Yeah, I was. Yeah. Oh, yeah, you're right. Yeah, I think.

Ferocious Sandwich: Yep. That's it.

Immutable Catamaran: It is a left sum. And that does make this slightly faster. Right. I don't have to go over. I want to kind of return to that. First. Sorry, at the start of the recursive function. I wasn't I do hear that. I didn't like oh, yeah, well, my base case I. But I don't think there's a faster way to do a base case really.

Ferocious Sandwich: I think you can.

Immutable Catamaran: Maybe if we pass more variables back. But let me think about that. K is equal to one. Right, right. Now what I do is I sum everything up and then I send it back. But can I Okay. Can I see maybe? I'm thinking like, I don't I'm not sure. I'm just thinking like, maybe I create something here. And then I pass that along. So that creates something here and I pass that along and to the, into the recursive function, a little bit nervous about passing more things. For example, if I start with my laptop, I started making films from the last but I don't think there's a way to do it where I put my comment. Let me just think about it from here. 120. So I, so I just am just thinking about this. This again, so when I pass in. Let's only say I have like I passed on this and this is my final answer. Here. I don't really see. You know, there's no other way of getting around it and looping it. So I was thinking maybe in the call beforehand, I I'd sum up everything from you here, I get one toasty 15. And then I know if I move my left bar, you know, I slide my left bar over that I know I'd be passing in repassing, like, pass in 10, and then it'd be passing in six, passing, etc. I keep like, Alright, moving. So it looks like you.

Ferocious Sandwich: Basically, I just wanted to point that out to you, can you keep a cumulative sum?

Immutable Catamaran: A cumulative? What I was thinking, and I'm not sure this is on the right direction, too, but like i, cumulative sum.

Ferocious Sandwich: So instead of splitting the array via indexes in Python, if you could, if you could never split the array and, and inform from which index do we need to calculate?

Immutable Catamaran: Could I pass them just left and right, indexes up the array of the window I kinda want to send in. I was acquired just a little bit of modification by I can try that as well. Okay, so you know, this I write in next here? Sorry.

Ferocious Sandwich: Yeah one second. So I think we are at the very end of the interview. So it's about 50 minutes. Right. So I think you will be able to solve this given enough time, right, like, with the cumulative sum and like left index and right index. So I think you're good with that part. So I guess we can start with a debrief if you don't mind. I know. Yeah, sure. So for a new grad, I would pass this as a lean hire. Right? So really? Yeah, this is a lean hire, like, so this is a brute force version of the solution, right? There's a certain version of the solution, which is of complexity, and log some, okay, if somebody had told me that, then I would give the mid level recommendation for them. Okay, but for a new grad...

Immutable Catamaran: n log sum?

Ferocious Sandwich: n times log of sum of all numbers in the array.

Immutable Catamaran: Thankyou.

Ferocious Sandwich: Okay good, you can look check this out later. I've just given you the link.

Immutable Catamaran: Thank you.

Ferocious Sandwich: Sure. So basically, what you did here is the brute force version of what they showed us in the first step. Okay. So for a brute force, kind of a solution, and you're able to, like, communicate very well. Okay, what is your thought process? Okay, you're able to take hints and suggestions very well, and incorporate that in your solution. Okay, all of these things are the stuff that you are looking for in a new grad, right? We don't really expect new grad to like, completely ace the interview with the very best, you know, algorithm or things like that, as long as we are hinting towards them to use something. And they're like, and they are like, responding to our hints well, and incorporating those interest into the solution. There's a very good signal. Okay. Okay. So, yeah, I think you did very well. Okay. So even though there could be some minor bugs in here, right, like maybe range one comma or something, it could be plus or minus one index. As I said, we are really not fighting with the compiler, right? It could be could have some bugs, right. But also, overall, it was a pretty good attempt, like, in my opinion, right? Doing this. And apply for Google. If you want, like, I can probably hit you up with a referral. Right? I'll probably share my email ID at the end. You can also do so and then I can probably give you a referral. This is a pretty decent return, in my opinion.

Immutable Catamaran: I that's really, I thank you very much. Like you could probably see I was I was pretty nervous. And I just want to see where I am and how much I need to practice more before i i started approaching interviews. But yeah, they just thank you. Thank you so much. I yeah, I I felt like I did not great. But you You gave me a lot of hints. And I need, I needed all of them. But thank you very much.

Ferocious Sandwich: Cool. Just a quick FYI, if you think that the Google interview was hella easy, trust me, you would have missed something. That's what I felt, right? Most of my interviewers, and like colleagues tell me this. If the interviewer thinks they did very well, then probably might have missed something. But if you think you have not done well, usually it indicates that you have reached far into the solution.

Immutable Catamaran: I'll keep that in mind yeah, thank you very much. Yeah, this is wow, I learned so much though. Like, I'm so thankful for your brother. This is really good.

Ferocious Sandwich: No worries dude like, I hope you like the fact that you've learned some new technique, right? A new way of thinking. That's what I want to convey in interviews like this. As long as you did that, I'm so happy.

Immutable Catamaran: Yeah, thank you. Is there one more question? Is there like a theme for this kind of problem? I if I searched recursion, I, I won't get this question. But is there a good theme, so I can practice more things along this line as well.

Ferocious Sandwich: Yeah. So the team for the optimal solution, optimal version of solving this problem is can you binary search the answer right.

Immutable Catamaran: Binary search? Okay, yeah.

Ferocious Sandwich: Say for example, the output for the first example is for right okay. That means that the maximum sub array Amin, the minimum supper is some achievable is four, okay? Can the minimum sub arrays some achievable be five, right?

Immutable Catamaran: Okay.

Ferocious Sandwich: Yeah, take the answers range, okay. From the minimum answer, like from zero till the sum of all the numbers, right, that will be the possible value for the answer, right? For each of those answers, right, the each of those answers cannot possibly be the minimum okay. So, it can be the minimum up till some point beyond which it cannot be the minimum. Right. So, your candidate answer from zero to the sum, right. Will be possible, possible, possible possible? And in some point, it will be impossible, impossible. Impossible. Impossible. Right. So the whole goal is to binary search on that answer on that answer.

Immutable Catamaran: Binary searching my sum is definitely, yeah, I have not seen that. Yeah, that's, that's super interesting. I was doing binary search the other day, but I only use binary search if I have sorted arrays, and that's my trigger to try to do them. But searching it by this is. Yeah, that's something I've seen before. I will have to say that as well. Thank you.

Ferocious Sandwich: Yeah. Check that link out there. They do the binary search Announcer And yeah, expect these kinds of questions on your Google on site.

Immutable Catamaran: Yeah, that's yeah, that's tough. But got better. Lets practice enough. And we can try it. Yeah.

Ferocious Sandwich: Yeah. You'll be able to get too, don't worry.

Immutable Catamaran: thank you very much. Thank you.

Ferocious Sandwich: No worries. Okay. Then I guess you can enter the interview. If you need any more help or info from me, feel free to ask. I'll probably share my email id see you. Good luck.

Immutable Catamaran: Thank you. Have a nice day. Have a nice night, wherever you are. And thank you.

Ferocious Sandwich: Thank you. Bye.

Immutable Catamaran: Okay. Bye