Python Interview with an Apple engineer

Watch someone solve the longest increasing path problem in an interview with an Apple engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Longest increasing path

Interview question

1) Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right]. 2) Given an m x n integers matrix, return the length of the longest increasing path in matrix.

Interview Feedback

Feedback about Swift Pigeon (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

Summary feedback: The candidate showed very good problem solving skill. He was able to come up with the best possible approach pretty quick. Before start digging into the most optimal approach he came up with a brute force approach and was able to correctly estimate the time and space complexity. Overall the candidate lead the interview, communicated pretty efficiently, and kept me on the same page. He rushed a bit early into coding, and therefore the coding phase took a bit longer that it could have taken. But nevertheless he solved the problem with best possible way in terms of the time and space complexity. As we discussed, please practice Graph Theory, DP, and Graph Theory + DP problems. Based on the second problem we had, it looks like Graph Theory + DP is one of your weak spots.

Feedback about Mutable Alligator (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

Very helpful session!

Interview Transcript

Mutable Alligator: Hello. Hi can you hear me.

Swift Pigeon: Yes I can, can you hear me?

Mutable Alligator: Alright, yeah, I can hear you. How are you?

Swift Pigeon: I'm doing okay, thank you. And you?

Mutable Alligator: Good. Thank you. So we are going to have algorithms data structure interview session is going to last for 40-45 minutes. So before we start with this, tell me about your experience and about your goals.

Swift Pigeon: Yeah. I am a recent graduate. I just started working a few months ago. And I am looking to switch jobs. So I'm going to start interviewing by the end of this year. And yeah, I currently, you know, just a few months on the job, front end, software engineers. So just looking to get some practice.

Mutable Alligator: Okay, sounds good. Do you have any plans in terms of like, what companies you're applying for?

Swift Pigeon: Yeah. FAANG companies and, you know, other top companies, I guess.

Mutable Alligator: And what position? Okay. Okay. You said the new grad, new grad, okay. So it's probably going to be something like entry level position.

Swift Pigeon: Yes.

Mutable Alligator: Okay, in this case, I think I'm going to just ask you a regular question that I usually ask on a real interview. Yeah. So let's try to solve this.

Swift Pigeon: Okay, given an integer array, and two integers left and right. Okay. Return the number of contiguous non empty subarrays such that the value of the max is in the range of left to right. Left and Right. And we're saying return I'm just going to highlight the return number non empty sub array then the max array element in that subarray is in the range left to right. Right, I think those are the two main points. So the left and right is that include inclusive of the right? Correct and left, okay. And then this example right? The max is in the range two, three. Okay. Do we have negative numbers in in array?

Mutable Alligator: Yeah, there can be negatives.

Swift Pigeon: Okay. And what's the what's like the maximum number I can have.

Mutable Alligator: I think we can like basically think about some solutions before we jump into basically becoming something that there's nothing special about this numbers.

Swift Pigeon: Okay. Okay. All right, okay. So, the thinking number of sub arrays in that range, okay. So the brute force solution would be to say, get all the subarrays right and then check, get all the subarrays and then check which ones are in that range, from left to right. So for example, you say for... Let me... Can I just quickly just demonstrate what the brute force looks like in pseudocode so you say for you know for num in nums and for well it says something like this. And then you start your other loop from from j in range i to the end. And then for all the subarrays from i to j, you'd want to test if the subarray is that range, right? So that would give you that will give you time complexity of O(n^3) where n is the size of the array and it gives you space complexity of constant space.

Mutable Alligator: Yeah, that's correct.

Swift Pigeon: All right. So to improve upon this. Okay, I'm just going to make one quick comment here. Saying check that... check that the sub array is in range. O(n) time. Okay, okay. Um, a better approach let's see. So for number sub arrays, we can let's say we have one two and three. Is it okay to include duplicates? Yeah. Okay, okay. That's all we have one, two, and well, we still we have one right there just once up there. If you have one and two. That's just one. Yeah, that's just one, two. And one, two. Alright, if you have one two three, we're taking all of the previous sub arrays, and then we're adding one, two, rather than three, three. And one, three. Correct. Right. So this I...

Mutable Alligator: I think also we missed just three.

Swift Pigeon: Yeah. So that means there one, there's one sub array right? There. Yeah. So...

Mutable Alligator: Sorry, are we talking about when left and right is 23?

Swift Pigeon: No, I'm just trying to find a way to quickly calculate the number of sub errors between a range. I see and the range of work between let me know say range when there are n. API n numbers in your sub area right three numbers so very ominous others. Yes, three numbers in your array. Amin sub arrays. us that's what I'm trying to quickly find. And then I want to use that to the to like reduce the complexity. Is that does that make sense?

Mutable Alligator: This is one way of doing that. Yeah but maybe we can also I guess here we are aiming for maybe something like linear solution here okay maybe maybe we can also work on this solution that you propose here and see if we can like somehow optimize this one's that.

Swift Pigeon: Okay. Yeah. So okay so for this one I was I was going to say that it looks like you can reduce this complexity of the check in you can reduce it to constant because the number of subarrays if you just if you're taking one number well wait if I was trying to demonstrate that the number of sub errors right if you have let's just say some random numbers 789... and then the numbers others is really the sum of numbers so in yet you have four times four plus one divided by two so... In here right 20 divided by two that's just 10 right? And if for our case, if n is three that would be three times four divided by two is six so that's six subarrays. So let's see if we can... Okay, let me go back to this question. If I know how to if I know number of subarrays given... some areas size I think I can then do a two point approach... Right. So I would say given two one four three, if I said keep extending the array while so right. I was going to say okay, find a subarray such that the max number is right isn't a range, that's right. So if you extend this one is not well, the maximum right one can be included in the in the sub array, as long as the max number is in range, two to three, right? So if I then extend this again, Now the max in that sub array is four right? So, we take this subarray and then we find we use the formula to find the number find the number of sub areas right given you know, two items and the subarray right. So, if we add that say to create to for example let me add one more... Yeah. So, initially it would get to one zero, right Max is in that range, then once we get here, we reset the pointer and this is outside the range just move forward again. And then this one is inside the range. So we calculate the sum of numbers for high numbers right and we asked them up you know, but how do you think about that? Yeah, let me think about edge cases. Alright, for this one, like if you have 210 and you calculate the sum the number of sub arrays we actually want to exclude arrays like one zero or zero or one right so 210 sum of numbers that will give you three three times two divided by two. Sorry, three times three times n times n plus one yes, that gives you six sub arrays right? However, we trust them the year two, we have to actually exclude correct so there is like 10 right. So let me think about that for a second. Right. We want to exclude sub areas that exclude subarrays that are in the range negative infinity to left minus one all right. So because right. If we if we find sub arrays that in their range thinking of other education is now to the treaty. So okay, right now, and just saying find subarrays were there max is okay, okay. All right, that though, use the sliding window is slightly. Then window to find salary in the range. So what I was doing... Yeah, right, we included one we included zero, even though they are less than less, right? Because numbers that are less than left can be joined to like can be joined to numbers in the in the range. Okay? So use sliding window to find sub array in the range negative infinity to right? Right? Because we do we do not want a number like four in our subarray age don't want that. Well, we want our numbers from one when our numbers in the range and lower than the range. And then we want to subtract that. You say I'm just gonna copy this. Right, so once you get this one, we want to exclude like we said, subarrays like this. So you can just say, yeah, you can just say subarray. All of the sub arrays from negative infinity to right minus salaries from negative infinity to left minus one. And that would give you the sub areas from left to right. Yeah, yeah, that's my approach.

Mutable Alligator: Okay, so basically, yeah, I think that what you're, you're gonna have is like, a repeat one more time. How are we going to calculate this? Number of subarrays? I think the range. I say you're going to iterate through this array with these parameters, basically, minus infinity and left minus one, right? Yeah. Okay. And got it. Yeah, I think that sounds good to me.

Swift Pigeon: Yeah. Yeah. And the complexity would be linear time. And this space complexity should be constant. Constant. Okay. Stack. Okay.

Mutable Alligator: Yeah, I think sounds pretty good. Yeah. Let's try to implement it.

Swift Pigeon: Okay. So, see, define get range. So you have left, your right. And this returns an integer. Okay. So we're using three pointers. You can say left pointer. Close, right, pointer equals zero. Such size and the number of course, sequences of numbers. Okay. Do you want me to talk through my code as I'm coding?

Mutable Alligator: Well, you can do this yeah. I think it's up to you.

Swift Pigeon: With that, okay. Let's see. Yep, 2143 you'd want to extend the right pointer. So right, that's less than size. And so we want to include numbers in the range left to right and left. Let's look at that again. So yeah, right point. We also want to make sure that the maximum in that sub array is in that range. If I just used this one would include as long as the number is okay. So this is really the just a helper method. Let's get for this for this two pins. Right. So as long as that number is within left and right, okay. So, right pointer starts from zero, and then right, it gets zero, nonsense, zero, move on. Try not to point to tried. So once you move the pointer, and it's outside of the range left to right, that's when we stop. So now you have the number of sub arrays as left just say array size would be equal to right minus left, right, since the rights would stop at a number that is outside the range, and the left would be the first one. So in this case, you'd have like two minus zero, if it is two numbers. Okay. So array count would be equal to array size, times the size of this one divided by two. All right. I'm just gonna count. Count plus equals count. And then once it you can left pointer equals right pointer. And yeah, we can just say, yeah, we can say it's quantity is greater than, right? While left pointer is less than signs, and that is nonsense. That pointer is greater than the right. Right? We want to skip that number. So a greater than, oh, no, Okay, that looks good. And it's a greater than or equals button. So you skip that number. And then once you get to where you want to start, right, then you make sure the two point is on the same number. And then yeah, you just keep extending the window until you have a number that doesn't match. And then once you're done with, you get the average size. Okay. And then she's done a return count. And then you can say... Get count. Left, right. This is count. Right? Okay. And now I just want to say get number sub arrays and arrange negative infinity to left minus one and negative infinity to the right. So let's call this let's call this all right. So if there was a if it was empty we I didn't even pass if it was empty then the solver just becomes zero right and also with firewood duplicate I mean look at this one more time think implicitly next sure that the maximum is in the range left or right. That's the one thing to strive to this time. Yeah. As long as you only include numbers so okay, negative infinity that's minus one right negative infinity right?

Mutable Alligator: Okay yes I think looks looks good to me I think. Yeah. I think yeah, I think it's pretty good I think that. So generally, the question I generally ask I think you you did pretty well and if you want we can we have time for one more question and choose a topic that you would like to practice maybe.

Swift Pigeon: Yeah, let's Yeah, so there...if there's really not the topic in mind, I don't mind

Mutable Alligator: What company are you applying for? Like maybe What's your dream company? Like Google for example or...

Swift Pigeon: Yeah, Google, Facebook. Apple.

Mutable Alligator: Okay, let's ask some ask you something that you may face it at Google. Okay. Okay. Yeah. Okay. Let me ask you this problem. Let me also sent you the picture address to the picture because I cannot copy paste the pictures.

Swift Pigeon: Given an n by n integers matrix, returns the length of the longest increasing path in matrix from each so you can either move in further actions. You may not want that in it or move outside the boundary. Wrap. All right. Okay. And then, given my mind 4668 and 211 the longest is 1269. Okay, Okay, the brute force solution. We all know is this. How, how big is this matrix? What's the maximum?

Mutable Alligator: Yeah, we can assume that. I guess like you can propose a solution. And again, like, you know, go take it from there.

Swift Pigeon: Okay. Yeah. Okay. Okay, so the brute force submission. See, you'd want to find every single path. And then you know, just see which one is as the longest. So the complexity for finding every single path. Let's see. So, okay, in a matrix you can move right? Or you can move down. Usually, you would not want to think usually you would not want to move. Move left. Okay, yeah, you can move. You can looking for directions. I want to say the complexity with the same complexity for brute force. Right with the, for to the, since it's basically just a tree and four direction, the four was the four children of the tree and the tree is as long as the number of items so n times n. Although more realistically you're not you're not always going to be like, moving for directions because you're coming from somewhere. So it's noisy matters and Pico, but I think it's more closer to three to the n times M. But anyways, yeah, it's there's such a... The space complexity. Usually, I would use recursion, if I was going to solve it this way. So this space complexity which is DD, stack, recursive stack, however long it is, which will be an exam and yeah, we don't need to keep track of the well we don't need to stall the path. We can just take it along and the recursive stacks. Yeah. So it let's approach let's see. Let's see. Longest and crazy long. Thinking about dp then I'm programming jumps with dynamic programming. We can we can prune brute force solution by saying if you know you only want to get something that's increasing. Well okay, that's more like in the real world. If it Spiegel the worst case, everything is going to be in prison. So Almost paths are going to increase and it still comes down to the same time complexity. Okay, so dp so it's basically just like longest increasing is the same as the longest decrease on so you say the diagrams and really also go from nine to six to two to one then have to go from one to two to six to nine. If you had any simplify this problem if we asked just one if we had just one array let's say does the number is negative numbers is that included it's possible yeah yeah, okay.

Mutable Alligator: Well if you want that video not have negative numbers like why I asked him.

Swift Pigeon: I was thinking you know, there's complexity because negative numbers can like cut down the paths that's increasing. See, I've wanted to negative one, four or five for example. And easier like some I guess it's strictly increasing right? If you have 3345...

Mutable Alligator: Right, it has to be strictly increasing. Yes.

Swift Pigeon: Right. Yeah, so if it was just one if it was just one array. Yeah, it's a whole lot simpler. Yeah dp please. C is the longest increasing and then i j. So we only care about left and up. Because... so down those well down is on explored more as a call it unexplored node. And write is also unexplored nodes like the future. But less is where you're coming from an OB can also be where you're coming from. Right. So that means we can say something like dp of ij is equal to the max of DP of i. So well, okay. Up is i minus one J. And less is i j minus one. And then you add that.

Mutable Alligator: So can I ask you? Why do you want to consider a left and up?

Swift Pigeon: So left and up only because I'm starting from the top. I'm going to start my loop from the top left.

Mutable Alligator: But how about if you have a path? Something like that? 6543?

Swift Pigeon: You mean if numbers? Correct? Yes. Right. Yes. So this would you would say? So for example, the beauty of this position?

Mutable Alligator: Right? Well, are you saying, well, there is not always a left? Is that what you're asking?

Swift Pigeon: Yeah. So in this case, you will, you'll have to go from the from the from the bottom to the top, right. So it's great. I think what you're doing is, Oh, wait, I think you're sorry, I think let me give you this. Oh, but yeah, I think what, what I was going to say is that if you have for example, like this, actually think this will contradict your approach, right? Because you have to go down now, instead of going up?

Mutable Alligator: Well, we can just do two way, let me think about that. I think we can solve that by doing three different DPS one where you start from the top left. And another way you start from the bottom right.

Swift Pigeon: I think it's also so well, it's I don't believe it will solve the problem, the problem because we might have also a situation that we have sort of like a zigzag, you know, we have like zigzag. And this would require us to like, apply your solution from like your first solution several times. And again, you're another solution. But that goes from different direction. And again, first one that again, second one, if you have some kind of zigzag zigzagging situation, right?

Mutable Alligator: Doesn't make sense or so. By zigzag. You mean let's say we have let's say we have...

Swift Pigeon: Let me give you example, we have for example, 99763, the exact 543210. The here you will...

Mutable Alligator: So you know what I suggest I suggest to leave this as your homework because five interesting topic that probably you want to explore it a bit more. So I can grant graph theory plus, plus, plus dB. There are lots of like problems like that you may face at Google that require this some type of graph traversal and some type of memorization. And what I can tell you solution either now or you can just probably export it.

Swift Pigeon: Is it? I assume it's it's a leetcode question, right?

Mutable Alligator: Yeah. So let's go to Yes, and I can give you a link. Yeah. Here's the link on the line 73. I can see more mud. But definitely, definitely your time complexity and space complexities. It's not like it's like closer to right size that you are able to Understand that complex approach. And another positive thing is that we're able to see that DP hand. Also the pruning that you're suggesting to us is also useful. And but we still have to use dp. Even for us pruning. Yeah. So yes, I think that you were on the right direction. That's sure you just need probably more time to think about this problem. And also, the getting the first problem. Yeah, I think it's a definitely have a very positive feedback about the first problem. You were, your technical skill was pretty good. You're like, code the way you code is yet was very good. It's very, very easy to understand. your thought process was very clear to me. Yeah. And with a brute force approach is also very nice. Yeah. I'm so in terms of like problem solving. Yeah, you were able to figure this out without my help. Yeah, it was nice. It was the best possible approach in terms of time and space complexity. Yeah. Yeah, in the communication was very nice. You were like, you walk through this approach. Maybe what you could improve in terms of communication. So is kind of like, as you probably not just we kind of it was, it's just like flight might be improvement that you could take, before start coding, you could maybe kind of walk through this approach a little bit more to, you know, to kind of visualize it a little bit better for yourself. So you, so you did not like get stuck at all, right? When you were when you started coding? Maybe this is like just one improvement, improvement you could have done because maybe, because as you can see, if you just like, see the number of lines of code that we needed, it's only what is this, like, 17 lines of code, right? 18 and 484 18 lines of code we spent about was about like 17 minutes or so. Which is maybe you could have spent less right? Even though literally can code it to means you just need to work. But for this, you need to like kind of get confident about your approach and like know, your approach pretty well, especially with this when you're dealing with two pointers. You know, when you're dealing with two pointers, it's nice. It's very nice when you do some type of visualization, probably. So you like understand it better. But nevertheless, I think you'll be able to, like solve it. Yes. Within the appropriate time. So I think, yeah, it's definitely would be a positive feedback. For me. Yeah. Yeah. Do you have any questions?

Swift Pigeon: Um, no, I don't think so. was like the questions. And I would look, I would look into this.

Mutable Alligator: Yeah, try to look at this. There is also some question that I had some time at Google. It was something like, I also had to, there was like a given like a ticket numbers, certain ticket numbers, even like a ticket ticket, like air tickets, right that each ticket has, has like information about destination, source source, airport, destination airport, and also like time when it flies. And those problems, it's also like graph problems. And it's also frequently asked at Google and on the Facebook as well, in those like a top Python db. They're just like for this one. So yeah, you want to look into this one. After the after this after looking at this one. Okay, then that's pretty much it for me.

Swift Pigeon: Thank you. Thank you.

Mutable Alligator: Yeah, have a good day. Yeah, good luck. Bye.Ï