Java Interview with a LinkedIn engineer

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

Interview Summary

Problem type

Contiguous subarray sum

Interview question

Given a list of numbers and a target, return the pair of indices whose values in the contiguous subarray from the first index of the pair to the second index of the pair sum to the target value.

Interview Feedback

Feedback about Stochastic Buffalo (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

2/4

What about their communication ability?

3/4

Good job in there. Like I said: - Better to start coding late than to start coding the wrong algorithm - Moving as fast as possible but not faster is the key to giving yourself time to check edge cases (or get hinted towards them). - These interviews are designed to be hard, but they are an acquired skill like anything else, and they're not a reflection of your worth as an engineer. - You can recover from more than you think

Feedback about Existential Crumpet (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

Great communication and great feedback. The interview experience was stress free.

Interview Transcript

Existential Crumpet: How's it going?

Stochastic Buffalo: Hey, hello. Hey, are you able to hear me fine?

Existential Crumpet: You cut out there for a second actually.Can you hear me?

Stochastic Buffalo: Yeah, I am able to hear you fine. So how about you?

Existential Crumpet: Seems like you're clear now.

Stochastic Buffalo: Oh, okay, awesome.

Existential Crumpet: Cool. So is there anything in particular you want to practice?

Stochastic Buffalo: So like, I just started preparing for my interviews, like I'm still practicing some problems, so like I would like to get a feel of like how the phone interviews go, so yeah, so that's my kind of goal as of now.

Existential Crumpet: Okay, well I can definitely give you a taste of that. The exact situation, right? A lot of times you're doing these interview practice things and you might actually be doing them onsite on whiteboard. In this case, it's exactly what you have. Cool. Let me get a problem for you.

Stochastic Buffalo: Okay.

Existential Crumpet: So, I'm gonna describe this to you. And then give you a test case. Given an unsorted array of non-negative integers, I want you to write a function that finds the indexes of the continuous subarray, which add up to a given number.

Stochastic Buffalo: Yes. Okay. Yeah.

Existential Crumpet: You know, what language you're gonna be using?

Stochastic Buffalo: Yeah. I'm using Java.

Existential Crumpet: Okay, so say I give you this array and this number. Do you want me to write the signature for you?

Stochastic Buffalo: No, I can write the signature, that's okay. So I have one question though, so like in this array, there are two, like seven and five makes 12, right? Like so in that case, like how do you want to solve like target, like can just the first set of arrays that add up to the number?

Existential Crumpet: That's right, you can return any one of the sums.

Stochastic Buffalo: Okay, okay and and there are no kind of limits, like number of elements in the subarray, so it can be two... so the minimum has to be two, right?

Existential Crumpet: No, actually let's say I provided the number zero. You would actually want to get a special answer, or you could give me... Why don't we make the second number exclusive, so in that case, your answer would be zero zero, so second number is exclusive, then zero zero is a good answer for any target of zero.

Stochastic Buffalo: Oh so, how about like if the array has like just zero and one, so can I say zero plus twelve is twelve, so can it give this as a path?

Existential Crumpet: There's a number twelve, then yeah.

Stochastic Buffalo: Okay sure, got it. So I just wrote down the problem on my paper right now so, so the immediate thing that comes to my mind is like so since you know the target sum, so you start with the... you take the first element of the array and start adding the elements after that, let's say five plus one, plus 3, plus... so so now it's like 6 plus 3 plus 9 plus 2 is 11, plus 9, so at the index 2, you got the sum of 11 and if you add 9, it's going to go greater than 15, so you cannot include the number 9 in the combination, and moreover since you said it needs to be a continuous array, so I need to kind of... So somehow come back... so let me see what is like... okay, so if I include 9, so it's like 11 plus 9, it becomes 20, so in that case, I have to see if I can go back from the initial count and keep subtracting the number, so if I can get the number 15. So in that case what's going to happen is like I will take 5 plus 1 plus 3 plus 2 plus 9, so after adding 9, the sum becomes 20, it is greater than 15, so what I'm going to do is like I'm going to start subtracting from the initial beginning of my array, so that will be like, I'll subtract first 5, so 20 minus 5 becomes 15, so yeah, that's the sum I got. So in that case, the... oh I'm sorry, I am using a different like... I wrote an example on my paper and I'm kind of working with that. I'm really sorry. I'll take this example and explain what I'm trying to say. So one, two, three, seven and five and the sum is 12. So what I'm going to do is calculate one plus two plus three, that becomes six, six plus seven, that becomes thirteen. So now thirteen is greater than twelve. So since it is greater than twelve, I will start subtracting from the part what I came in, so that will be like starting from one, I'll subtract one from 13. So then it becomes twelve, so now I know that the sum is from two to seven, is the index where I can find the sum. So I think like this is one way we could solve the problem and if you like the runtime complexity of this should be like, it should be O(n), yeah. The worst case like you might travel the the entire array two times, like I think yeah, it should you O(n), the complexity of this should be O(n), so if this explanation is good, can I start writing the code?

Existential Crumpet: Please do.

Stochastic Buffalo: Okay, so let me start writing the code. So, I will define a... Let me define a function. Okay, since this is gonna return a pair of numbers. I'll just create a class maybe. So here this is an integer, so I'll take an integer array. So one thing is like, if the array is empty or if there is... so one case would be like, assume that array has only one number, and that is the sum you are expecting, so in that case I can just return the number? Index zero?

Existential Crumpet: So you're saying if the array has one number, and the expected number or the target number is that same number, you're asking what to return?

Stochastic Buffalo: Yeah.

Existential Crumpet: Yeah, we'll just return the array over that number.

Stochastic Buffalo: So what I'm going to do is I'm going to start with... So what I'm thinking is like let me just write down the complete code and I will later come back and kind of explain it at some point.

Existential Crumpet: Okay.

Stochastic Buffalo: So now here, the current sum is not going to be greater than expected sum. I don't see whether at any point in time there will be a situation where the sum will never be equal to the expected sum. I don't think that will happen because at any point we'll definitely get the sum. Yeah because we included something and we are reducing the count. I think it definitely will. Okay, so I don't think I need to check that case, so if j is less than i...

Existential Crumpet: Mind if I jump in? Okay, so what happens if we devise an array that looks like this? Your approach gives me...

Stochastic Buffalo: I think I understand what you're saying. I think yeah.

Existential Crumpet: See what I'm saying.

Stochastic Buffalo: Yeah, yeah, I think I got it. So basically like I cannot stop just like this, like I need to continue from the place. So basically like once they reach, so... Sorry... So if my j is here and if my i is here. I think this algorithm will anyway will not calculate, it will assume that there are no more sums, but three plus one is four, so I should start again like from here, like I should go back. I should mark my j here and start the same group. Yeah. Okay, I like add this case yeah, but even if you look at... Let me just validate it once again on the paper and just writing down here on the side. Yeah, I think this should be good.

Existential Crumpet: Okay. So, I see... the problem I see with it...

Stochastic Buffalo: Yeah, I need to handle the case where there is no sum in the array. I need to handle that. I think this should work.

Existential Crumpet: You wanna walk me through the case I gave you on line 19?

Stochastic Buffalo: Okay, so 19, okay, so let's... Okay, so let's start from here, so j and i both are here, so first is like... So now what happens is the current sum is like currents sum minus three.

Existential Crumpet: Why is current sum -3?

Stochastic Buffalo: Current sum is zero now, it's not -3.

Existential Crumpet: So okay.

Stochastic Buffalo: So now j, so at this point like I increment j, so j is less than equal to zero. j is not less than or equal to i, so I break this loop. Now I make the current equal to i. So I also need to make j equals i. So if you make j equals i after setting this back, so now both j and i are in three and current sum becomes three. Okay, so now, I move to one, so the current sum becomes four. So now I see the current equals the expected sum yeah. So do we think this the case that I missed? Like resetting j back to the current original point, like the starting point?

Existential Crumpet: So what was your question?

Stochastic Buffalo: So now, I did not set the j to the starting point again after I hit the current visit the` current sum, once the like your case, like once it reaches zero, now it's not the expected sum, so what I'm doing is I'm still inside the for loop, so I'm setting the current sum to the value at j and then I also set the j value at index is i, so now it will still go through the the outer for loop, so now the current sum becomes current sum three plus one = four, so we get the expected sum.

Existential Crumpet: We're looking to get eight, not four.

Stochastic Buffalo: Oh yeah. I don't know why I did 4. So basically what I should do is like, so once they reach 9, sum as nine, and I start my subtraction from the beginning, so once I see the sum going below the target sum, that is eight, I should start incrementing my right hand side index, that is the i, so that I want to check again, my thumb is making the value. So I think that's what I missed.

Existential Crumpet: Okay yeah, that's correct. As you... these interviews are actually a little bit shorter than real interviews, so let's try to wrap up. So I'm going to make a suggestion to maximize your chances. I think as you take into account this fact, you should not be afraid to rewrite code here. I think you know what you need to do now. Don't let your existing code hold you back. I think that's good advice for interviews as well. I've seen a lot of people try to retrofit old solutions that are good, but they're not the optimal solution, and that's not as successful usually.

Stochastic Buffalo: Definitely. So one of the solutions like, so when you are evaluating right? Do you look at both like the the solution and the implementation or like assume that like you are you know, sometimes like a problem is really complex, so if I'm able to give you the correct solution, but I'm halfway through the coding, so how do you kind of judge in that case?

Existential Crumpet: In terms of order of importance. I think the most important thing is completion. It has to be a working solution, so that's the first part. And the next important thing that's pretty high up there, it's the efficiency of the solution. So you want to make sure that your solution is really the correct solution, because as these programs usually go, you usually don't get get a lot of O(n^2) solutions. So if you figure out an O(n^2) solution to an O(n log n) problem, that's tough. But let's say you figure it out by the end, this is how I would do the optimal solution, then that's forgivable. So that's that's how I think about it. I think for code quality, solution is a little bit less important, but typically if you come up with the right solution, you're going to know you have a pretty good idea how to make it look clean.

Stochastic Buffalo: Got it. So I honestly I haven't seen this problem before, so how do you rate this problem? Like in the order of the easy, medium hard, how do you rate this problem?

Existential Crumpet: I'll say this problem to me, to be perfectly honest, on a 10 scale, yeah, let's say one is the easiest phone screen. So that's you know, you might actually get that as an intern. And then 10 is like a principal engineering like problem, this one problem is probably a four or five.

Stochastic Buffalo: In a typical phone interview, do you expect one problem like this?

Existential Crumpet: This one is more of a one problem, it's definitely possible to get it done in enough time, but the interview is pretty short.

Stochastic Buffalo: So like maybe like so how do you rate my solution for this interview?

Existential Crumpet: I think... Well, I think your solution is definitely the right time complexity, although I guess with this problem, it's kind of obvious what the general idea is. We're looking for the biggest continuous subarrays, makes sense that you can check continuous subarrays. You're gonna have to quickly get it. You know, I would give you, I think you did well, but you probably wouldn't move on.

Stochastic Buffalo: I understand yeah, this is really good feedback, thank you. Yeah, so I think so those are the questions I like specifically had with respect to this interview. Since I'm kind of preparing myself, so these are like really valuable feedback for me and I really appreciate the time you took to take this interview for me, like this is good feedback for me.

Existential Crumpet: Yeah. I know you are just getting started, but I think what's most important in this to keep sight of the fact that these are just interviews. These questions that are designed to test you, not necessarily like whether you're qualified, it's a signal of motivation. So if you're prepared for them, that means: a) you're capable of doing this algorithmic stuff, which is you know, proof that you're smart guy, but b) you prepared for them, you're ready for whatever job. Keep your ego out of this stuff. I think a lot of people, well the question is not going well, you missed the case and it's like, you're halfway through, I think what can cause people to panic sometimes like you know throw an interview that they weren't doing so poorly at is to start sort of like make it more of a bigger deal than this really is. So that'd be my piece of advice. Just you know, try to keep calm and try not to associate your view of yourself as an engineer with these questions.

Stochastic Buffalo: Yeah, so like, I had one other question. So just take the case of this interview, right? Like you gave me like a couple of edge cases which I missed, so if I am able to write the code and solve for those, so do they add value to it, like in the sense that like do you allow me to go to the next round since I have kind of wrote the code for all your edge cases, or do you say that like he did not think about the edge cases, so we will not take him. So, how do you evaluate on that?

Existential Crumpet: Yeah yeah well, I mean everybody knows that let's say I give you the problem you're able to code it up without needing my help, you anticipate every edge case, you're trying to get a hundred percent on the test, then obviously you don't need my help. But if I do sort of point out an edge case, or I'd say hey, okay, it looks good, but I do see one or two issues with it, what I'll do is that I 'll give you a test case that demonstrates it. I think that's the perfect amount of hinting. I don't do anything except introduce something that already exists that you didn't think of. And then you go through it and I think that the key there is to make sure that when you see an edge case, or when the proctor gives you a case, you want to generalize sufficiently. So if you don't generalize enough, I think I gave you this case on line 19, and what you really needed to do was quickly figure out that this isn't going to give you 8, and then boom, how do we fix it so that it gives me 8, and then boom this is what I need to do to change this algorithm. And if you had done all that, I think you're definitely capable of it, then you would have passed. Because the most important part of these interviews isn't being able to see the trick under pressure, although that's certainly important, the most important part is keeping your communication skills up, and being able to see that okay, this is a greater problem that they're trying to suggest, and then like staying connected to the interviewer, that's what gets people going.

Stochastic Buffalo: Got it, I think this is very good feedback, this was really helpful.

Existential Crumpet: Sure, sure. Do you have any more questions?

Stochastic Buffalo: No, nothing else. Again, thank you for taking this time, this was very helpful.

Existential Crumpet: Okay, thanks a lot.

Stochastic Buffalo: Have a good night, bye bye.