C# Interview with a Google engineer

Watch someone solve the maximum sum subarray 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

Maximum sum subarray

Interview question

Given an array, give the start and end indices for a subarray that contains the maximum sum.

Interview Feedback

Feedback about Awesome Llama (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

Mr Llama discivered Kadanes algorithm with minor hints and ended up with an almost clean solution. Llama should try to write optimal solutions sooner in the interview to get to follow up questions.

Feedback about Epic Iguana (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

1/4

How good were the questions?

4/4

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

3/4

1/4

Interview Transcript

Epic Iguana: Hello? Awesome Llama: Hi, how's it going? Epic Iguana: Hi, can you hear me fine? Awesome Llama: Yeah, I can hear you. Epic Iguana: Okay, hi. So since we're doing this on interviewing.io, we'll just skip the formality at the beginning and go to the technical question if that's fine with you. Awesome Llama: Sounds good. Epic Iguana: Okay, so this one's called the largest sum subsequence. And if you've heard this before, you can tell me. The question is, essentially, you're given a list of integers. And they can contain, like numeric features. And what you have to do is, given the list you have to tell me a range, which word have the largest sum possible. So if I take 2 4 5 10, this has a maximum sum possible. Because if I take this minus two as well, we'll see... So you have to select a segment of the array. Awesome Llama: Okay. And these have to be consecutive? Epic Iguana: Yeah, the array has to be consecutive. Awesome Llama: Okay. So in this case on... Epic Iguana: This particular segment. But if that was minus five, let's say, the answer would still be this particular segment. Awesome Llama: Okay. So, I mean, the brute force thing to do would be to do a double for loop, and just sort of test every single window, and then keep like a variable to store like the... So the goal is to find the window such that the numbers add up to, you know, the greatest number? Epic Iguana: Yes, yeah. Right. Maximize the sum of the numbers you select on the range, yeah, yeah. Awesome Llama: Yeah. Okay. And I need to return the range. Right? Epic Iguana: Yeah, you could actually return the starting and the ending point. So the indices in this case, it would be 2, 5. Awesome Llama: Yeah. Okay. I see. Yeah, so what I think I'm doing is just doing a double for loop where the outer loop is going to be representing like the starting of my intervals that I'm testing. So first, we'll start with my outer loop, we'll have i equals zero. And then the inner loop, I'll first test, you know, just one, and then my max will be one. Then I will test one, negative two, and then that'll give me negative one, it's not bigger than one, which is my max. So I won't replace my max and then I'll add two there. And then keep repeating the process. And then after that inner loop is done, I then go to the second iteration of my outer loop. And since I've already tested every interval that starts with one, I could... I don't, I only need to look forward. So I start with negative two. That's my first, the smallest interval, and then two, negative two, two, so on and so forth. And there probably is a way to optimize it to O(n), but I'm going to start with this and then see like, if I can find any inefficiencies in my solution. Epic Iguana: Okay, sounds good. So what do you say the complexity of this implementation is going to be? Awesome Llama: So it's going to be O(n^2) because I'm going to have two for loops, one nested in the other. Epic Iguana: Okay, sounds good. Let's see it implemented. Awesome Llama: Okay. Okay. It will take an integer array. You need two for loops. And quickly copy and paste it. This one will start at the new beginning. We'll go to the end. And then I need to keep track of my max. And also what range that max represents. So I'll just say max sum equals zero at first. And then I'll have the indices of all this range of max sum. And I think I could just copy that. No, no, I might be wrong, but let's see. Okay, so here, I'm going to evaluate a new interval, which starts at i and ends at j. So initially, when i equals zero, now j is going to be equal to zero on the first iteration. And so the very first interval I'm gonna check is just like from the zeroeth index of the ith index. So what I need to do is I need to find the sum. I don't, I'm going to quickly get like a... I think there might there might be a sum function. But actually, I could keep a current running total of the sum, actually. Yeah. So I could call that current sum starts at zero. And what I want to do is add the current number to the sum. Yeah. So I want to say current sum equals sum, I forget if there's a quicker way to do that, plus equals, C sharp array. Yeah. I want to add that, and then after I've added that, and have a new sum, and I'm including the value of the next j in my interval, I need to see if current sum is greater than the max sum that I've been able to find. If current sum is greater than max sum. And what I want to do is I want to replace max sum with the current sum, and I also want to replace the interval, too. So I want to say, yeah, range, max sum zero equals i. Starts at i, range of max one equals j because we end at J. Okay. So at the end here, we just return range if I just change this to return an int, array, range of max sum. Yeah, that should give me the interval. Um, let me just quickly look over this. One thing I could do is if we have an empty array... Epic Iguana: You can assume it will be not empty. Let's have a code run. Let's put some padding to it. Awesome Llama: Yes. Okay. Yeah, sounds good. So I'll go in here. And I'll do my first test case. I'll copy what you did here. Yeah, so I'll call this test array one... Yeah, okay, let's run this. Oh, I see. Oh, I see. Yeah, this is uh I'll just call this method interval with max sum. Epic Iguana: You can just create a main method to execute the code. Awesome Llama: Oh, you're just okay. Okay. Yeah, just second. Let me see what's up here. Oh, I see it's a non static. So if I change this to static actually... cannot convert null to int. Okay. Okay, I'm just gonna say I can do this. Right. This is capital. Okay. So, really quickly, I'm just going to write a quick thing out. Call it crank. Yeah. I'll just do this. Make it easier for future tests? Epic Iguana: That's the correct answer. Let's try to run this with negative numbers. Awesome Llama: Let's see. So, if we change this to like, if we just made all of them negative, for example. Epic Iguana: Yeah, what should the answer be? Awesome Llama: Well, anytime I add any number whatsoever, it's gonna make them, it's gonna make the numbers small. So negative one should be the answer. Well, I mean, it should be the interval with just negative one. Okay, yeah. From zero to zero, inclusive. Epic Iguana: Okay, can you change the negative one? To negative 10? Awesome Llama: Yeah. Epic Iguana: Yeah. So now it should be negative two. Could you run it again? Awesome Llama: Yes. Okay, interesting. Yeah, so I get 0 0 again. So interesting... on the second. So on the first iteration, I have negative 10 as the start of my interval. First, the current sum is going to be negative 10. I'm going to see if negative 10 is greater than zero, negative 10 is not greater than zero. It's going to say zero. So yeah, I think the my max sum here doesn't... it assumes that I'm not going to have any negative like, sums. So yeah, yeah. In that case, what I need to do is, let's see here. Um, there's two approaches I could take. I could either use the negative infinity, or I can, if it's, I can set it to null to start with. And I could just add a condition like if it's greater than or if max sum is null. So I mean, I think that would be good. Epic Iguana: That sounds excellent. You can just do negative infinity. Awesome Llama: Let's see. I think it's maybe... Yeah. Oh, it's dot. Okay. Yeah. That's what it is. Epic Iguana: Okay, that seems correct. So you told me this is O(n^2) runtime? And what is the memory complexity of the solution right now? Awesome Llama: So at any given point in time, I'm only keeping track of these variables. And they don't grow at the size of the input. So it's just going to be our constant space complexity. Yeah. Epic Iguana: Okay. Yeah. So the space complexity looks optimal to me. Is there any optimizations you can look for that can make this faster? Awesome Llama: Um, yeah, so what I'm doing currently is I'm looping through every single number more than once, I might just need to loop through them all at once. So what I do is I go to the first number, like in this case, one, and then I look at all the numbers past that to look at all the intervals. Um, one thing I could do, maybe I could start looking at the intervals that include negative two as well. Yeah, so if I have one, I consider one negative two. But then at the same time, I can also use the fact that I'm already at negative two to maybe consider that interval. Epic Iguana: One thing to think about is when does it make sense to keep a negative number in the final range? Awesome Llama: Well, I guess when maybe there's a number right after it that's big. Like if there was maybe like a negative two but maybe there's like a 50 afterwards, you know, the negative two is worthwhile to keep. Epic Iguana: Yep. Yeah, that's the direction you can think in. I think good idea of traversing the whole thing just once and get what you want out of it. Maybe you can try doing it on another array how you would do it yourself if you were to manually do it. Awesome Llama: Yeah. Like if I mean, I got to If I had like, maybe like 10, -2, 40 maybe. Or look at 10, my current max of 10 is negative two. Then 40, I have included this negative. After I'm here, I may not need to keep the previous number, or maybe... Oh, I see. And then I go to 40. Huh. But once I'm at like negative two, I see. So one thing I realized is it's like, it's all positive numbers. It doesn't make sense to lose any number. The only time you'd ever want to sort of consider whether or not you want to consider whether or not to make it the entire array or not necessarily keep the beginning is if there is a negative number that makes it not worth it to keep what came before? Okay, it's pretty straightforward. So if I reach my current sum, which is like 10. And there could be no other numbers here, right? It might not just be 10. If there's many numbers and I reach negative two, if the current sum is greater than, well, if the current number if the current is greater than the absolute value of the current negative number, right, then it makes sense to keep the negative number. But if the current sum is like four, but the negative number is five, negative five, then I lose one by keeping the negative number. So make sense to drop everything that came before and how the whole start at one after the negative number. Epic Iguana: Yeah, it make sense to me. Can we see it done? Okay, this is we said about the starting, that's pretty much can tell you where the range would start. How do you find out whether it goes on? Awesome Llama: Yeah, so once I hit a negative number, and I do that evaluation on either the range is going to start at that negative number, or it's going to start one after that negative number, right? So like in this one, for example, here, I do evaluate, okay, my current sum is one and then negative, in that I have negative two, negative two is bigger. So I abandon like, one and my new, start to my range is two. Epic Iguana: And then the other case? Awesome Llama: What other case? Epic Iguana: The first number is 10 and then -2, so it makes sense to keep it. Awesome Llama: Yeah. So if I, I see 10. And then negative two, my current sum is 10. And the current negative number I'm out is negative two, absolute value of negative two is two. So it makes sense to keep it so I keep the start of the range where the negative number is, or not with a negative number. Sorry, I leave the start of the range unchanged, which might be somewhere back here, like at the negative 10. Yeah, basically. Epic Iguana: Okay. Yeah. And how do you find out where to end? Awesome Llama: How do I find where what is? Epic Iguana: Where the right end is, right? This description looks fine for how do you find what to leave at the beginning, know how you find what to keep at the end? Awesome Llama: Oh, I see. Epic Iguana: How you can think of the starting and the ending point. Awesome Llama: Yeah, so as I keep reaching new numbers, I'll keep changing the end to the new index that I'm at. So if here, for example, I keep negative two, now the end is going to be at negative two. And then here if it's positive number, I will just keep it and I'll keep changing the negative the ending interval, the ending index to be at each new number I reach and the only time where I will start, the only time I'll change, like, for example, if this was one, right here, so it starts at one, and then I go to negative in my ending index is also one, and then I go to negative two. And when I decide now to keep negative two, now, my start and end index are going to be set to be the next number. Epic Iguana: Right, that makes sense? Let's implement it. Awesome Llama: Okay. I'll call this interval with max one pass. So this is gonna look similar. So I'm gonna only need one for loop. So one thing I could do is, yeah... And I don't even think I need a for loop, I think I just need a while loop in this case. I mean, I could use a for loop, I think. So I consider the first element, if it's positive. So if it's positive, I'm just going to update this value right here at the end. So if array i greater than zero, then I simply just want to, say max sum... well, maybe not always going to be updated. I think I do want... this might be reset a few times, like when I abandon like, everything that came before because of a number. So um, start off at zero initially. But if I do that, if I have a number that's positive, I'm going to say current sum equal to current sum plus array[i], otherwise if it's greater than or equal to because it doesn't cost me anything to add zero. Otherwise, what I want to do is I want to check and see if it's worthwhile to keep the negative number. So I need to see if current sum is greater than the absolute value of array i. Actually doesn't make a difference because, yeah, it just amounts to zero. So um, so current sum is greater than the negative array. If it's greater than we want to keep it and we want to do essentially what we did here. So I could add just this as an or statement right here. So many times we want to keep the current number as if it's greater than zero, or the current sum is greater than the sum with the greater than the negative numbers absolute value, okay. And then if that's not the case, and our else condition is to just, well, there's a few things we want to do, we want to reset the current sum back to zero. Um, another thing I want to do here really quickly, though, is double check if current sum is greater than max sum, I want to update the range for the end only. So range of maximum that's going to be at i, going to be it's going to be used one at the end and it's going to be is going to be the end. Yeah. Otherwise, if we're going to reset, we want to have the range and add the next index, if it exists. Because it might not, if we are at the end of the array right here, I need to double check that. If i guess i plus one is greater than or equal to array dot length. So actually, what I want to do is if it's less than the array dot length, so if there's still something else beyond, I want to set my new current interval to be that. I think I need two variables for this instead of one. I need one to keep track of the current range, and one to keep the maximum range. Epic Iguana: I think that makes sense. Awesome Llama: Yeah, so I'll say, current range equals new int. Hmm. Well, I may only need the start. I think I'll keep that just in case I realized I need it but then I don't think I do. Start was called crunch start. Zero, yeah. So it's going to be zero until we hit any negative number, which would cause us not to. So I could say because the i itself is going to be the end. So I could just see a current start is going to be equal to i plus one, if there is any room there. And then the current sum would be zero now. But if there's nothing beyond that, then we could just return the range of maximum. So I also want to point out. Yeah, so I changed at the end right there. And range of maximum beginning, the current start. I want to change the maximum sum. Yeah. Okay. Epic Iguana: Okay, let's try that on the test case for this. Awesome Llama: Okay. So what I could just do is I'll try this... Yeah. Oh, actually, yeah, I'll try the one that's already there for now. Um, okay. Um, yeah, I need to change this to call the other one. Missing a semicolon somewhere. There it is. Okay. Yeah. Yes. What I suspected. So even though I think this condition is always going to get hit, because eventually there will be a well, actually not necessarily. Yeah, I need to eventually return here. Right after the for loop, I need to return the range with maximum. Epic Iguana: Why is it returning at the end? Awesome Llama: Um, so if we reach the point where like there's a negative number at the very end? Yeah, though, I think that it would work just as fine without it, because there won't be another loop anyway actually. So in a way, this sort of just clutter and in fact, actually, I don't even think that this if statement is needed. Yeah, because it's unnecessary. Yeah. Okay. Epic Iguana: Okay, let's run this. Awesome Llama: Yeah, this one. So that was, that's not right. Epic Iguana: Yeah, that's supposed to be one, one. Awesome Llama: Yeah. So if array i is greater than, so I'm first I'm gonna evaluate... I'm going to look at negative 10. Negative 10 is greater than... zero? Is it greater than? Okay, so, yeah, it's greater. It's not greater than zero. Current sum zero is the current sum zero greater than the current negative number? Oh, I see. Okay, wait, is it greater than the current? Hmm. I see now. I do think I need an offset. Because I need to do this strictly when this is not true. Yeah, yeah. Okay. So if I have a positive number, do that. If I have a negative number, I do this. If I have a positive number, I do that if I have a negative number... I want to see if it's greater than, if the current sum is greater than the absolute value of the negative number. If it is greater, then we're going to keep it. So we want to do exactly this, I believe. We want to add it. But I know for a fact that we don't need to do this because it won't create a new maximum. So we only do need to do this. So if it's positive, do that, and then these two are the cases of if it's negative. Yeah, so then if it's negative, and the current sum is greater than the current negative numbers, positive value, then you add it. Otherwise, you set the new start to be the next index and you reset the current sound, okay. I'll try running this now. Okay, interesting that I got that again. Current start is zero. So let me walk through it real quick. So I got negative 10 to start. Is negative 10 greater than or equal to zero? Epic Iguana: I think the code won't reach this logic because this line indicates that it has to be positive for this to happen, right? Awesome Llama: Right, negative 10. Negative 10 is less than zero, so it won't reach this. Oh, I see. Yeah, negative 10 is, negative 10 is less than zero so it won't reach, so it'll go here. So the zero and 10, it won't reach this. So it'll go here, but it doesn't even have anything yet. I realized, yeah. So if it's negative, I can... so it's negative. So the times I want to add it is if. Okay, so if it's positive or um yeah, current sum. Okay. So I also want to add it if, if there's nothing there yet. So negative 10. Here, so then I check. Current sum is going to be zero. If current sum is zero, then we have that... well I wonder what would happen if I did the other... what would happen if I did or max sum equals min value. If I did this... Epic Iguana: The only piece that's actually setting the range of maximum and minimum is at line 40 and 41. Which is ever only happening for positive integers. Awesome Llama: So I see. So I'm not doing it for if I decide to keep the negative integer yeah, that's true. Epic Iguana: That's the only thing. I think right now I think if you run this code with even a single positive number, it's gonna work. The only case it doesn't handle is all negatives. Awesome Llama: So I need to do this right here. Yes, I need to update the ranges. Epic Iguana: Do you always need to do that? Awesome Llama: So if I got a negative number in that number and this is zero, current sum is zero. And this is going to be 10, ah so if I decide to keep it... but this is... Yeah. Well, yeah, I do. Always want to. Well, I don't want, I actually I don't need to update the current... I don't necessarily need to update the current start. Or do I? Yeah, something? Epic Iguana: One easy way to fix this would be just have a check whether all the numbers are negative beforehand. And if that is the case, then print the minimum of those. Oh, sorry, print the maximum of those. Awesome Llama: Oh, interesting. Yes. Wait, if there's any minimum or if there's any. Epic Iguana: If all the numbers are less than zero, then print the maximum of the numbers, and otherwise follow this algorithm. Yeah, so that gets the previous state. And we can run it with a single positive integer and see if it works. Awesome Llama: Well, I will just run this very quickly. I think I'm still gonna... Yeah, get that. But yeah, you're right. If I have, like, five, right there. Epic Iguana: Yeah, now you don't need these two lines. Yeah. Okay. I know, you'd be able to definitely write that logical checking all numbers and negatives. So you don't have to demonstrate that to me. But other than that, I'd like to conclude the interview, I think you solved the question well, and you came up by yourself with something that's commonly known as Kadane's algorithm. It's a single pass algorithm to find maximum sum subarray. So you can write the name down. Yeah. So that was good. There was going to be a follow up if the question had gotten over in time. But most interviews with Google are just 45 minutes. So I'm going to keep this to that as well. But the follow up question, just in case you're interested and want to solve it later was going to be that you have to select the maximum sum subarray again, where you're allowed to get rid of one number from it. So you could select one through 10, and then get rid of this minus two. So what's the maximum sum you can get if you're allowed to select any segment and then remove one number from it? Or not remove any number, up to you. Awesome Llama: So if I have the option of removing any one number from the list? Epic Iguana: Yeah, well, that's the same thing. Yeah, you have the option of removing any one number from the list, and then getting the maximum sum sub segment. And what's the max you could get? That wouldn't have been the follow up question. Awesome Llama: Oh, well, I mean, only if there's a negative number, right? Epic Iguana: Yeah, only if it's negative, yep. Yeah. But it can be tricky cases where you might not want to remove like the most negative numbers. That might not make sense. But there's also a linear time solution for that. But yeah, that was just in case you're interested in the follow up. Other than that, is that any questions you have for me? Awesome Llama: I'm really just, um, you know, I'm starting to interview again, it's been a few years. I know that sometimes, some questions are asked more than others, you have any sort of suggestions for questions that would be more well worth my time focusing on versus not, you know, like, I know that some there was one year like when I was interviewing for internships that I studied dynamic programming a lot and I got no questions around that. So I was just wondering what you think is a good thing to focus on, you know, good other questions to do in my free time? Epic Iguana: Yeah. So if you're planning to apply for one of the big names like in the FANG, like Facebook, Amazon, Netflix, Google, then I'd definitely recommend brushing up basic dynamic programming questions, at least common recursion. And I'd also recommend doing common tree questions like dfs, bfs questions. But if you're not applying for these top tier companies, and you're just focusing to get into a regular, you know, software engineering role, then these are not really required. Then there's a set of questions that much smaller that you can focus on and attack the interview. You probably definitely heard of leetcode? One of the best sites for interview purposes. Other than that, you can look at geeks for geeks. They have all common questions and common recurrences. If you find a question that it's probably best to know it. They also have some that are company specific. So if you're interviewing for a particular company, then give that a look for more advanced topics. Topcode, code forces, and code champion. But this is only if you're trying to apply for FANG. One of the big companies. Awesome Llama: Interesting, okay. Yeah, I'm in the process with Amazon, but I haven't had my first interview yet. Epic Iguana: So yeah, Amazon, the easiest of the lot. They're expanding a whole bunch right now. So yeah, that's a plug for the interview. Awesome Llama: Okay, awesome. Yeah. Well, thank you for taking the time to mock interview me. Epic Iguana: Yeah, yeah, sure. Thanks. All right. Have a good rest of your day. Awesome Llama: You too, thanks. Bye.