Python Interview with a Microsoft engineer

Watch someone solve the non-decreasing array problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Non-decreasing Array

Interview question

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

Interview Feedback

Feedback about Winter Penguin (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

5 star on everything for L4, slight weaknesses for L5 but overall, great! You're doing an amazing job, and Amazon would be lucky to have you. Goodluck in your interviews. Feedback Non Decreasing Array Targeting L5 -Expecting technical solution and overall good comm flow. - Also expecting very deep complexity analysis. Technical Feedback - Immediately wrote wrapping function, good py3 syntax. ++ Fast - Immediately jumped to code, might be beneficial to write pseudo and maybe proof check logic relative to examples. ** - Consistent coding style , pep8 - Avoid navigating sliced copy of array, pointers guarantee access without slicing - - Quick to code functional solution, able to run through fairly fast. ++ FAST - Thought of bin search<- Won't be necessary given the search has to be linear and we will possibly have multiple values not following the pattern — - Exploring use case for bin search- Can harm you if you contemplate the use of an algorithm you don't have a grip on. Great perf, but not seeing bin search as an invalid option might be a red flag - - [Passive negative] - Able to think through bin search, caught up exposing weakness with it. [Bin search can perform on equal values in array, be mindful not to expose a weakness in this regard. Cover the fundamentals. [ - -]] - Hint of splice [Able to figure out that splicing is O(n), optimized it fairly + Slow] - Able to think through generalization case ++ Fast [Testing on distributed computation] - Evaluating use of either distributed computation or parallelization. [+ Slow, always jump to map reduce when the computation is huge] - Excellent [Was able to catch the split point issue with distributed computation +++ Fast] Communicative Feedback - Has a thought first, code later approach which is organized ++ Excellent - Is able to mix up speaking and typing, doesn’t. Able to keep up with much of the logic. ++ - Smooth communication style, confident. Never was confrontation when interrupted.

Feedback about The Legendary Avenger (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?

3/4

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

4/4

Really lovely session! I greatly enjoyed your feedback, it was very well structured and had good take-aways on areas of improvements and some of the subtler strategies to interviewing. My only suggestion (and take this with a big grain of salt!) is to perhaps ask questions that either focus on the more tricky points of arrays, or more complex data structures. Personal opinion, but general array questions tend to be the "freebies" in interview loops, versus the more challenging DS such as graphs, or trickier concepts such as backtracking/recursion in general. Again, take this feedback with a grain of salt! You have the interviewer experience, not me :)

Interview Transcript

The Legendary Avenger: Hello.

Winter Penguin: Hello.

The Legendary Avenger: Hey can you hear me?

Winter Penguin: Yeah, I can

The Legendary Avenger: Just a quick check, don't know if you can hear my fan in the background.

Winter Penguin: All right it got real bouncy there for a second it kind of buffeting.

The Legendary Avenger: Oh, sorry. I was asking I have my fan running in the background and I wanted to confirm if you could hear cause it's kind of hot I'm in Seattle and it's kind of hot here.

Winter Penguin: I'm in Seattle to, I get ya. Is it like an oscillating fan.

The Legendary Avenger: Yeah.

Winter Penguin: Yeah when it comes by its giving a really windy noise but when it's not like running right past you, it's fine.

The Legendary Avenger: Okay, I'll keep that off. I mean, we have about an hour here, so I can bear that. But anyway,

Winter Penguin: It's like 90.

The Legendary Avenger: I know a man. It's, it's kinda insane. But we have to survive. Alright, anyways assuming everything is checking well, so. Well, let's maybe start from here. I can, I want to get like a couple of calibrations before we get started. So maybe give me a quick overview of what you're targeting with the interviews or what levels you're targeting to interview for, and what exactly you'd like to get out of this.

Winter Penguin: Yeah. So I haven't interviewed for like, years at this point. And I keep getting a bunch of Amazon people reaching out to me, so I was kind of looking towards like an L5 level thing. If you're familiar with Amazon's levels, I'm kind of am assuming you might be since you're in Seattle, but yeah, just kind of general. Like, you know, the the leetcode-y software engineering interview type thing, just trying to get some get some rust out, you know.

The Legendary Avenger: I hear Yeah. Yeah. Fortunately for you, I've actually interviewed with Amazon before and gotten an offer at that level. So I actually have a couple of questions I can suggest you look at after this. Unfortunately, Amazon is known for having a bit of tricks in their questions. So before I even go into the question I wanted to ask, I'll give you the question. They asked me so that you can check it out later. It's not what I wanted to ask you today. But when you mentioned Amazon, I was like, Oh, you know might be pointing this out. So I don't know if you know the next permutation question.

Winter Penguin: Next permutation question. I don't know if I do.

The Legendary Avenger: So let me share it with you. I'll just paste it in leetcode here, and so you can check it out later, I had a different question prepared. But lets paste it at the bottom. So this is something I've been asked in the past. This is also another question they've asked me in the past. So let me share this right now. So just a second so it was next permutations next permutation and maximum water level, those are the two I remember. I'm not sure why. But yeah. Yeah, one sec. Is it pour water or maximum water level. Yeah, here it is. Trapping rainwater. That's what they call it. Yeah. Yeah, right. Okay. So those two, those are two questions I was asked earlier this year, actually. So if you have time, I'll advise you check them out, just in case they might give you good practice anyway. But yeah, okay. So you're targeting L5. So for context, I'll gauge based off of a couple of parameters, ranging from communication style, so try and evaluate. If I can give you any feedback, like the point of what I'm going to try to get out of this for you is not just a solution, but rather give you at least any point of improvement. So even if you've seen the question before, that's totally fine. Of course, you know, tell me that I can calibrate my expectations based off of that, then make sure that I actually give you feedback that will be helpful. Is that Okay.

Winter Penguin: Sound's good to me.

The Legendary Avenger: Awesome. So the question we're going to go through today is the non decreasing array question. So paste it right here. One second. So let's get to this. And I'm assuming you're gonna use Python, right?

Winter Penguin: Yeah.

The Legendary Avenger: Awesome. This is the question you're gonna solve. It's called non decreasing array. And the gist of it is given an array of integers, purely integers, you're essentially allowed to change just one element to make sure that it's non decreasing, like non decreasing I.E. it could be equal numbers or whatever it is, but the point is, it should be strictly incremental or flat. And, you know, you can find discrepancies here and there but you're only allowed to change it once and so you're supposed to return to Rule either if the array is non decreasing, or if a single change is sufficient to make it non decreasing and false otherwise.

Winter Penguin: I'm just going to write that down real fast. That that makes some sense here, I have not seen this problem before, so, kind of take some notes thats, well I'll just kind of figure some, but just start off defining a method, I guess, decreasing is, array, and let's see, so we're taking some array numbers and popping out no it's not array it's list. Send out some bool. And that's that. So let's see. So we're given an array of numbers and just check if it could become non decreasing. So the thing that pops up to me it's like the the, the obvious solution is to just kind of go through it, keep track of the previous elements, right? This counting the first element, because there is no previous and then see if as you go through it, you can check if it is consistently increasing or the same, once you hit the first one, that is not decre- that is not increasing or the same. You can just I was gonna say you could keep a count, but you could really just make a bool that says, you know, have you incremented yet right? Or deleted something yet, and then continue going through it. And if you encounter another one of those cases, then you return false. And if not, you get to the end you return true. So that's kind of the approach, I'll probably start coding here. I'll do the easy things first, if not num, I'm going to assume that counts because it's not, it's a non decreasing array, because it's not an array. And then otherwise, lets see previous element is going to be zero, just kind of pass that first element and then current elements and getting past that first first element again or set up a removed variable, initiate this false. And so if previous elements, let's see if it's going to be less than or sorry, if it's gonna be greater than current. That means we are in a non decreasing state. So we can say, is true, because we need to remove this to make this true. I'm going to come back to this because there's a little bit of trickiness here when it comes to what is previous elements at this point. And then, otherwise, this particular for loop we're just going to say is equal to cur element. If not removed then we'll do this. And otherwise, loop. So yeah, basically comes down to the tricky case of if we have not remember this before. So I think the the initial thing I want to do here is just I'm curious if this works, right as it does where we still just set prevails previous elements current elements. I'm going to say, technically if we're removing this elements here, then no it shouldn't work, because our previous element should stay as this current previous element because cur element is getting skipped over. So I'm going to actually just tuck this prev element equal to current elements in our. That way, so we're going through previous element is greater than the current elements. And non decreasing if we haven't removed anything yet, trigger that Boolean. Don't change previous element because previous element needs to stay the same because we're, quote unquote, removing elements here. We have removed something. And that's the second case we're it's not going to work. All the cases we do this little statement here. Yeah, I think that should probably work here. Let me see if. I think I have to import something for lists. I don't remember what it is exactly. But yeah, I think this should probably work. If I were to go through a, let's see if I can just make up some sort of case here. Zero one, three two six seven. Something like that should return false. So if I go through here now and just check what's going on here.To pass this not nums previous element is zero. I'm gonna actually make this a little smaller. Because It might take a little bit of time to go through

The Legendary Avenger: By the way the audio keeps cutting in and out,

Winter Penguin: Oh it is cutting out on my end?

The Legendary Avenger: Sorry, yeah. Yeah, it keeps you keep speaking then it cuts out and comes back in but should be back now.

Winter Penguin: Okay, yeah. Sorry about that. I'm not sure if there's anything on my end that I can see right now that would be causing that, unfortunately.

The Legendary Avenger: All right.

Winter Penguin: I think i'll check that out after this. Yeah, so let's see. Got this set up. So here's our test case. So initially, previous element set to zero. And we'll go through all this. So previous element is greater than current element. Nope. All right. So current element is now three come through or previous elements is now three current elements is now two previous elements is greater than current element. Yep. And not removed. So we're setting this remove the true part here. Previous elements staying at three, then we come up here. Six, so previous element is three current element is six, this is false. Go through. And we have six as our previous elements. Current elements is four. Previous element is greater and current element our removed is true. So we can put this false statement and yeah, so that seems like it works. I'm fairly confident that this should be fine. And this should be a nice easy O(N) time and O(1) space algorithm.

The Legendary Avenger: Alright, let's see. So let's say let's say so this is a false case. Let's see the case is 321. Yeah I'm just I'm just gonna do a quick analysis on this. It's one but this shall return false too. And save not nums, of course, it will set previous number to three remove to false for current element in situ, look at one one previous element is greater than current element, of course. And then you have not removed currently, it's false it'll be true removed is going to be set to true, else it's gonna return false. So it'll set it to true. And then to go on the next iteration where previous element uh what do you call it previous element will now be, what is it going to set it to? It's still going to be three. So it's going to be three and then we're going to look at two uh we're going to look at one is the current element, and then previous element is still greater than current okay. So you're going to hold the previous element to the largest. You've seen the past, right?

Winter Penguin: Yeah.

The Legendary Avenger: All right. So you've said the complexity of this is currently O(1) in terms of time.

Winter Penguin: O(1) for space. O(N) for time.

The Legendary Avenger: All right. All right. Okay, good. So far, doing well. So just a quick feedback on that, but do see any way we can make this a bit more efficient, especially complexity wise, do you see as if there any unnecessary operations that you can avoid?

Winter Penguin: Let's see. So for this current algorithm here, I'm not seeing any obvious improvements, to this particular algorithm, I have been trying to think as you're kind of walking through your analysis, if there's any other iterations of an algorithm like this, that we could try to utilise to figure out like a solution here, quicker. And so it's tricky with O(N) algorithms, right? Because that's usually generally pretty fast. The only thing that's generally any faster then that tends to be binary search algorithms, because you get that log N thing. I'm trying to go in my head here and figure out can we do anything any binary searches in here that makes sense. And so what would we be looking for in the binary search, right? So I suppose if we were the binary search here, on one of these, one these arrays. The first thing we'd want to figure out is, so we have a start and an end. And the end should always be greater than or equal to the start. And we're going to want to look for an element or multiple elements that don't follow that pattern. And that's, that's an interesting thing for me to think about here. Unfortunately, binary search isn't my strongest suit, even though it's a relatively simple thing to think about. Because generally, you want to work with sorted array, right? And so that kind of leads me to think All right, so let's think about a weird false case, right? Like if we had something like one, negative five and negative four, whatever. Something like this. Here, our endpoints make sense. But then when we try to do like a binary search, we select midpoint and go left to right, that gets trickier because you'd end up with numbers that don't make sense. I guess you could utilise that and be like, alright, this number doesn't make sense here. So you know, you have found something that's wrong. And then, then the tricky thing is, you found one wrong thing. Do you want to do like a removal in like an actually edit the array at that point? And do some like, Alright, got your midpoint removed during that removal from a list like that, though, is what? Technically it's o n. So that wouldn't actually improve efficiency at all, if you did this kind of thing. So if you weren't to do this, then then what would you end up doing, then would you end up doing another round of binary searches within sub arrays, but then it feels like you'd still be at the point where you're going to end up wanting to cover every single, potentially, in a worst case scenario, you'd end up wanting to cover every single elements, right? Because like, the worst case scenario, is everything's fine. You're looking for a case that doesn't exist, like you have the 1234, etc. So, since o n is still worst case, that would still be big O of n. And it would be a much more complex algorithm. So thinking that that's probably not an actual solution, and that might be most effective.

The Legendary Avenger: Alright, so a couple of things here. So just out of curiosity, when would you use binary search in a general sense? Like, when would you use it?

Winter Penguin: General sense when you're looking for something? Like you're looking for an element in some sort of list array whatever. Where the array in question generally, I'd say is sorted in some fashion, like it has some sort of order to it that lets you bisect it. In way where you know, what's going to show up on both ends.

The Legendary Avenger: And what if they are racy, has you call it has the possibility of equal values like it's not strictly non increasing or non decreasing? Like it might have equal values so strictly increasing or strictly decreasing in this case? No, no, actually not. It's not strictly increasing or strictly decreasing like it has the possibility of equal values on occasion, like how will bin search perform form in that case?

Winter Penguin: That's a good question. Actually, I don't know if I've actually fully thought about that before, I suppose. In that case, you could end up I guess you can't really search through that, can you because like you're relying on the whole, like, one end has, you know, what, for the easy argument where you're doing like, increasing order, right, you have your left side is going to be lower, your right side is going to be higher, you pick the middle, the middle is too high, you go left, or the middle to low you go, right. So if ever if you have equal values in there, and the equal value isn't something you're like, specifically looking for as part of your problems, then I think you can't really utilise the binary search. Not super confident on that answer. But that's my, my thought.

The Legendary Avenger: I hear you. Okay. And out of curiosity, do you see any, because you know, complexity wise, you're correct. This is probably the most efficient approach, we can get O(n), o(1). But do you see any, any way we can optimise this to avoid any unnecessary operations? Like do you see any way we can code this a little bit better? Because now basically, what I'm looking for is Python knowledge, because clearly, that's the language we chose, is there a way you can see that we can improve this?

Winter Penguin: Let's see. So we're thinking Pythonic stuff. As I'm looking at this, and wondering if we could do something. I was gonna say we could do maybe something ternary in some of these if else's. But I don't think that'll actually be better.

The Legendary Avenger: Let's see, specifically, let's look at line 22. Do you think that splice operation is necessary there? And what does that have in terms of memory? So assuming we have a very huge array?

Winter Penguin: So actually, you're right, I think Python does copy that doesn't it and then create a little splice. So I guess in that case, maybe the better thing to do is just a range loop for I in range one the length of nums and then. Then you can kind of drop that guy, you have the same behaviour there. Just a little bit more efficient for space usage.

The Legendary Avenger: Awesome. Yeah. So basically, the reason why I was looking at that, because technically, they're still O(N) in terms of space. And so by making this change, it now assures us that we are going to be O(1) right? And let's see. Assume, so one out of curiosity, let's do some memory games here or some what do you call it some mind games, so you don't have to code anything. But say we want to generalise this to a point where you are allowed k number of changes, how would you modify this code, such that it will return same, you know same output, but telling us whether or not, you know k number of changes.

Winter Penguin: In that case, if you have K number changes, the thing that I would assume would be changed is this removed, instead of being a boolean which is really a 01, which is perfect for 01, non decrementing moves, right? We would change that to be I would make it K. Start it off as K here. And then in these cases where we have if not removed. Instead of doing remove that equal to true. I'm actually just going to type it out for sake of clarity here, but like say that here we do something like removed minus equal one, if removed. You will have a zero return false. Something like that where here removed is now equal to k. In that way, yeah, every time we're seeing something that's going to be breaking our condition or our variance isn't quite the right terms, I guess breaking our condition. We just keep removed, like marking items for removal. So we had K removals available to us now we have K minus one. Eventually we'll have zero removals available to us and then we're gonna have to return false. And actually, I think it would actually be something more like that, to begin with. Where you check it for move is already at zero first and then if not move things otherwise, yeah.

The Legendary Avenger: Awesome. All right, so overall doing very well so far. So I know its L5. So I'm kind of gonna push you a bit more, of course. So say, say we have. Okay, so we're gonna get like a, you know, take a step back at this. So you you've answered this correctly. So good job so far. So say we want to actually evaluate that solution where we have k possibilities. And the big question we have now is, how can we like to say we have a very huge array? Now we have a very huge array that, you know, if we were to process it serially, it's probably going to kill us. How can you leverage? You know, let's say you have an unlimited competition here, you can do whatever you want, how can you leverage the computers in order to evaluate this as fast as possible?

Winter Penguin: Interesting, um, this is stuff that's a little bit outside of my general comfort zone, which is good. But let's see. So the issue here is so giant array can't, is the thing basically, we'd be streaming in numbers, instead of, instead of being provided just an array off the top, we have like a stream, and we can do something like nums dot get next or something like that? Is that generally the gist of where that's kind of going? Or is that a little bit different than what we're.

The Legendary Avenger: Alright say, we don't have an iterator per se, but instead of a stream, think of it as we actually have an array, it's really huge. But this array is going to take, like, if you were to process it serially, O(N) like this, it's gonna take millions of years, like assume, you know, we're back in the days, but how can you like leverage different you know, I'm looking for different computational paradigms. You don't necessarily have to code it. But how can you like leverage a computer like a modern day computer in order to process this as fast as possible? Do you have any strategy?

Winter Penguin: Yeah, I guess. So. I suppose you could parallel parallelize this a little bit, right? Like you split the numbers array into, I don't know, let's say, n number of arrays. And you basically pass those n arrays to each of these to a function that does this, right? So you have so many threads or processes or whatever, you have it doing one of those computations. And then you'll get, you know, so many answers back, the issue there is going to be right, when you split the array, you're going to reduce one particular check right? The split point. So you'd have to do that, you'd get some sort of result back. But then you also need to make sure that you're going to check on that kind of split point there. So like previous of arrays, zero versus the first of array one, that sort of thing. I think that would probably get it done. I think that's the main edge case there if you're gonna split into sub arrays, and send those sub arrays out to different processes. That's the first thing that comes to mind, trying to think if there are any other solid solutions here.

The Legendary Avenger: You know, the name of that process of splitting along split splitting and, you know, distributing along multiple computers, multiple processes.

Winter Penguin: Right, or was there a more specific term?

The Legendary Avenger: It's a MapReduce, essentially, what you described was MapReduce. FYI, congrats on actually identifying the weakness even without me asking, that's actually a huge bluff. And that's actually something I was asked. So good job. Yeah, FYI I was asked by Amazon specifically. So you catching it without even being asked that, commendations for that? And

Winter Penguin: I don't do any of that high performance stuff ever. So I'm glad I was able to think back to college days.

The Legendary Avenger: Yeah that's totally fine. You know, the downside to it is even if it's not necessarily, it's not necessarily a high performance interview, oftentimes, they would consider this basic knowledge at L5 and above. So it's just good to know about it, even if you do not necessarily code using it on the daily right. All right, then let's see. Do you have any other inquiries actually, say say back to the streaming idea. So this is probably going to this is going to be my final push, push on and then we can jump in, just back to the streaming idea so say we are not able to fit this in memory. And you actually get you have your iterators you had infered initially. So how would you navigate keeping track of the same numbers? Do you see any issues that could arise? If you're using an iterator in this case, looping through this.

Winter Penguin: I think the main issues is going to be your initial step, right? Where your initial step is together, make sure you do like, prev elements is equals to nums dot get next, and then your, your iteration changes, right? Like it's, I assume, if you're going to have to get next you'd also have something like nums dot have next. And you can do this kind of while loop to replace what's on line 27 here, then otherwise, I think, you know, you're just gonna be cur ele equals nums dot get next. And the logic besides that stays the same, right? Like, either if it's 01, or if it's going to be k, you can stick with that kind of thing. I think the main thing to like look out for there's just, you know, running out of elements in your iterator, right. But besides that, I don't think there are any other real gotchas.

The Legendary Avenger: Alright. Just a sec. I think that should be all honestly, you kinda went through the questionnaire fairly fast. So I didn't really have any other deep extension. So I'm hoping that so far, you know, maybe you can just jump into this. And maybe you can have a deeper feedback session in this case. So how do you feel you didoverall?

Winter Penguin: Pretty decently I think, luckily, like, you know, array stuff isn't my my weakest spot. There's plenty of other things I'm not amazing at but array stuff tends to be reasonably straightforward, right? My main issue is overthinking things. And on that note, I'm curious, so I kind of went through my thought process on binary search approach. And I'm curious, how would you have interpreted that whole kind of segway on your end?

The Legendary Avenger: That's actually a good question. So in that case, then I'll paste my feedback. And then you can go deeper into this. And then if you because you probably will have a lot more time at the end, assuming so we can actually also delve into the some of the questions I pasted up, see if you can think through them. But in the meantime, because you know, they are a question. So clearly, you have a good insight on them. But here's my feedback. And I'll just give you a quick debrief, and then we can go through the individual. Individual questions after if that's okay. Is that okay?

Winter Penguin: Yeah perfect.

The Legendary Avenger: So pasting it at the top. Alright, so here it is. Can you see it?

Winter Penguin: Yep.

The Legendary Avenger: All right. So initially, I was trying to establish expectations based off of understanding your level, because obviously, if it was L4. I wouldn't be expecting a perfect solution. So in this case, set expectations for the thorough and correct complexity analysis, as well as a proper technical solution, overall communication flow. And my technical feedback on this will be one, I really appreciated the fact that you started by writing, or writing a wrapping function. You know that's, that's just always a good idea. And defining the output format, as well as the input format, that's always a good idea. And it's good that you actually know the per paid on Python three syntax, that's actually something you know, If I was particularly looking for, you know, knowledge of their language, that's a plus, it's not necessarily something I'll be evaluating for. But if you had it, and another good candidate in target, I'll probably prefer you. So at Amazon scale, they probably have a lot of that. The one downside, I noted is you immediately jumped into code at that stage. And so if I was interviewing you, I might have a sense, oh he might have seen this, that's why they're able to jump into code without really thinking through the weaknesses. So sometimes, it's just good to write some pseudocode and then even if even if you've seen the question before, just pretend you're kind of going through it, just to make sure that that suspicion that this person has seen this is not there anymore. So you know, jumping into code really showcases experience with these things and it's not always a good thing, it can actually bite you back if you are actually accurate really, really fast. And so a good piece of advice here might be think through an inefficient approach so you know always if you can if you can think through the efficient approach immediately well and good but you can also see an inefficient approach just suggest it for the sake of it and then kind of deduct your way onto the efficient approach. It shows some sort of thought process which is always gonna be better than just jumping to the efficient solution. So I appreciated the consistency in style and so here I put plus plus because personally, that's a big deal for me, like people actually follow the standards you know if you're gonna use Python, make sure it's camel case. Make sure its snake case and you actually following the right standards in this case, that's always a good thing. And you know, the one thing to note, it should always avoid slicing when doing iterations. If it's possible to use pointers, it's always a good idea, either use an inbuilt iterator or use a pointer just to avoid those copies. Because those are the gotchas right? Like in this case, you might say O(1) and while you know, I wouldn't punish you, but L5 I would expect a more efficient approach. Because when you're working with large, large arrays, then that can be a problem. If you're doing the slicing, that would lead to a very inefficient code. And so that's one negative, not too big a negative. I'd say there's only one there. And so I appreciated how fast you're able to code a functional solution. And that was, that is always a good thing that you clearly know what you're doing in this case, and I was able to follow it through. The one thing that I think can use improvement was after you've written the solution when you're doing the run through. So like when you're doing the line by line run through, quick tip that I tell people is use a cup. So instead of talking about values on the fly, do this, go under your example input, put a cup underneath it. And then as you go through a line, let's say you point here, if there's any change, you can use this cup to navigate it. So you can say something like P one right here or something. And you know, and it's simple and pedantic things. But let's say that P one and maybe another P two, somewhere here, and you put it elsewhere, this will allow you to navigate this visually, it's, it's easier to see for the interview, it could be the actual p one or P two, whatever it is. But this is a lot easier to navigate. So when you make a change, you increase one, you decrease one and you know that kind of comparison with allow the interviewer to follow a lot to follow along your code a lot better. And it will allow you to, you know, it will allow you to pretty much have the process that you're talking about written down to no longer be something you just talked about during the code, during the interview to be something that you know, you've already given or given them a record for that. So try and visualise your thought process in this case, not THE worst thing, but it's just a point of improvement, as I said, so actually, right. Run through or debug processes, you go through it. I have to

Winter Penguin: That's a good suggestion, thank you.

The Legendary Avenger: For sure. And I appreciated the consistent sale, I think I've said that pointed out, pointed out the call it the issues with navigating now here's been such part actually. So I felt like you should have caught the fact that I've bin search might not work well, faster in this case, mainly because there's a possibility, I mean, the false gift that we're looking at is a case where we have to two or more non decreasing, non decreasing or increasing areas like there are two or more in the array then that's an issue. And so by virtue of that, our array will potentially be unsorted in some instances and so that automatically renders a bin search such out of the question. And so it's something that I would have hoped to caught immediately because, you know, I was, I wasn't particularly gauging you for bin search, but I let you go on because it also gives me a chance to test you on something that I would otherwise not have tested. But it kinda, you know, it might reflect as a negative thing, if let's say you say something wrong. And so it's good that you're able to think through a bin search yes, I could tell that you have your familiarity with it. But at the same time, there are some things that you said that were a bit wrong. And you know, the precedents of even jumping into bin search itself was actually wrong, like this is something you should have caught immediate, like yeah, there is a possibility of two unsorted aspects in this a bin search won't apply. Like a bin search is strictly when there is an order either increasing or decreasing. Like I particularly asked you when let's say there are two equal numbers and actually a bin search one still like if let's say you have a series of equal numbers, because in that regard, a bin search only needs to know the length of the remaining half that it needs to be looking at. And so while let's say I go to the midpoint, and let's say I'm looking for an increasing element, if the midpoint is still equal to my left, then I know the increasing element is still probably on the right, even if it's equal. So equality does not necessarily rule out the effectiveness of bin search. And so that was a trick to try and catch you you said it might not work, which you know, might be a red flag, if that's something I'm particularly testing out to see if you know and so if you if you're able to roll out solutions that don't work, don't give the interviewer any room to try and dig through your knowledge of something else that you might be weak at, does that makes sense?

Winter Penguin: Yeah that makes perfect sense.

The Legendary Avenger: And so my suggestion on this, just try and dig a bit more into bin search. I know you're probably going to put time into it. And, you know, do have a couple of practice questions particularly. I like I like this questions. Peak questions when you're trying to find the peak. I find that I find that those are usually the most applicable questions for trying to find bin search let me see if I can find it. I have this question here peak, find peak element.

Winter Penguin: I will definitely say one of the weaknesses I have is I never know if I actually have the ideal solution or not. And that's one of those things, it's kind of hard to pan out. The confidence in that.

The Legendary Avenger: I hear that. Frankly, I much rather get an inefficient solution that is well communicated. In your case, you really did well, because you give me an efficient solution and overall your communication of great. So that's actually a huge plus. So don't don't be afraid of not getting the most efficient appro- solution, so long as your current solution is as well communicated as possible. Does that make sense? Alright, so let's see. Hint. Okay, I think we already covered the aspect on splicing, already gave you the feedback on bin search. And then yeah, I tested on some advanced topics where they say distributed computation. This was this was actually as I said, something that I was asked at Amazon. And so you catching the split point being an issue is really, really good. That's actually a huge plus. So I'd say just cover some basic, just do a quick review of you know how to do distributed computation, you don't even have to like do it actually just understand what some of these core concepts are like MapReduce, because it's an expectation that tells that you actually aware of them. So it's a core concept in distributed computation, and pretty much any form of any form of high performance computation. So parallelization is something that even front end people will do. So it's just good to be familiar with it. Even if you don't have a mastery, mastery in it necessarily, that way, you can talk through it, even if it's in theory. And so overall, overall, understand your communication, as I said, sorry, on line 27, this is actually you're the first person I've seen do this, because normally give the people this feedback. So this is actually really good. So I noticed that you speak fast, and then code later, which is a good approach. I personally like that approach too, a lot of people tend to try and speak while coding, which can throw them off. So if you've never been told that, that was an explicit skill is actually beneficial. It gives you a lot of organisation, and I'm assuming it's part of the reason why you're able to go through the question really well. And to me, that's a huge, huge plus, that's something that tells me you actually know how to structure your communication. So think through whatever you're thinking and then code it out after the opposite approach might also be effective. But it's only when you actually are confident in your solution. So obviously, you can mix it up a bit. But this is actually something I want to note, keep doing it. It's really, really good. And so let's see, overall, your communication is great, so I really don't have any issues with that. Now, the one thing I can maybe tell you to do a bit more is try and involve your interviewer in the question, even if you're good at it. So like, you know, just having those polling questions. So does this make sense? Do that you think? Does this, you know you can ask me something along the lines of does this seem clear to you or something along the lines? So whatever I will ask you, or I'll tell you whenever, like, I want to see if you understood my question, try and do the same with the interview, even if you're actually 100% on the right track. That way, it showcases a bit of collaboration so that it feels like the interviewer is not just seeing the right solution being written, rather they actually engaging as you go through the questions. So don't go too deep without bringing your interviewer in and making sure that they actually keeping up with what you're writing. Does that make sense?

Winter Penguin: Yep makes 100% sense.

The Legendary Avenger: All right. Any questions on this I don't know if there's something I can expand on?

Winter Penguin: No, no. That was, that was really helpful. That was very nice of you to go through it, what you did. I have never almost never on the interviewer side. So it's nice to see how other people take their notes. One thing you did mention is, when we're talking about binary search things that you're going to look for something that you liked, did you find that?

The Legendary Avenger: It's right at the bottom, I don't know if you went actually attempt it.

Winter Penguin: Sure.

The Legendary Avenger: So line 97. I can paste it in if you want to make an attempt at it.

Winter Penguin: Yeah let's go for it. We got 15 minutes, we'll see if I can get anywhere onit.

The Legendary Avenger: All right. So sorry, what trapped water okay, it's sorry, let me check. Yeah, that's the peak element. All right. So that's the peak element. Here's the description for it okay so that we can just paste it right below then you can comment everything else out. I won't interrupt you on this, I'll just give you a chance to practice. And then if I see any glaring weaknesses, I'll tell you, so take your time, make an attempt at that okay?

Winter Penguin: Yeah I'm just going to create this, this little stub here, while, since I know what the title of the problem is. Alright, so let's see here. So peak element greater than its neighbours. So we're given an array you to find said peak elements return the index. If there are multiple peaks, your return any of the peaks, that's nice, don't have to find all of them. Nums negative zero equals negative nums n equals negative infinity. Okay so, O(N), O log(n) time this here would be like, I mean, obviously, I know, this is a binary search problem, but even if I didn't know, there'd be a giant int right there. You can assume in most interviewers, interviews, you're not gonna be told what the ideal runtime is. But let's see. So peak elements, something that's greater than its neighbours. All right, so

The Legendary Avenger: Maybe, sorry, just to take a step back. I'm gonna let's assume we in an ideal real interview, in this case, I guess. And so I have that line of how do you start thinking through that?

Winter Penguin: Yeah, so the way I'd start things through. Let's see so peak element is greater than its neighbours, given the integer array, returned index Nums. negative one is equal to Nums N which is equal to negative infinity. I'll be honest, this particular statement here is a little bit confusing to me, because so I think nums, negative one is equal to last elements of array. Nums N is any element of array and all elements are negative infinity, is kind of how I'm interpreting that. And so I think that's an incorrect interpretation, because that doesn't really make a lot of sense.

The Legendary Avenger: So think through it this way. So if you are, if you are thinking of these peaks as defining the altitude at any given point, then the end and start basically or the element right before the end. So I know that syntactically this is the last element, at least by Python, but the element before zero, think of it as being pretty much a cliff into the abyss and the element of the mountain being a cliff into the abyss.

Winter Penguin: Okay, got it. That makes sense. So now if I were to look at this, so we have. So we're given an integer array of num, turn the index of peak. So greater than neighbour. So one of the things that. And again, this is kind of a little bit weird, because I know it's going to be binary search but when I look at this, and I look at these statements nothing here tells me that the array is necessarily ordered in any way like I look at it and I think, all right, peak element where it's greater than its neighbours, we can have 010, then we can have negative five, we have four, negative six, and then we can go back to do with like, 7, 8, 7. And then we have three different peaks here, right? Yet there's no order associated with this. So if I were to just look at this, I think the first approach I would go with would be a linear search through where we have a peak behind elements. And I'm just gonna set that for the moment and a peak. Ahead elements where that peak behind element is, since we have this kind of cliffs on both end thing, that will be negative sysmac side Python to get our negative infinite. And then this peak ahead element is I guess this will also we can initialise at least to that Max negative is max size because we don't know nums really has anything right. Which is a good a good side case. Well, if there's no nums if num, if it's not if num, if not nums. There should be zero peaks. I assume if you find no peaks, you want to return an invalid index, which in most cases can be negative one. And then otherwise, a second edge case here is to have a peak, you need to have at least three elements, right? So

The Legendary Avenger: I mean, technically, if you just, if you just have one element, given the condition we have right here unless that element is equal to infinity it will be a peak right?

Winter Penguin: Yeah, that is a good point. Yeah, because we have the cliffs on both ends, as the as we mentioned before, so this is our only real edge case here in terms of amount of elements in that array. So yeah, so like I said, if I were going to go through with this, I think I would just kind of take an iterative approach to start, keep peaking behind, keep peaking ahead, as we move through, check if we are in the middle of those two, we are then cool, that's a peak, and we can just quit out right away and return that particular index. Because we're just returning the one peak elements. We don't care if there are other ones after. So we're still going to be at an O(n). But you know, ideally, we end up with maybe a slightly better where we exit out a little early. So let's see here, yeah.

The Legendary Avenger: Let me ask you this. So say, say you think think of this view actually, as a person, so say, say you're just gonna do a temporary bin search, like, you know, scope bin search like, we're looking at the local, local during this after you see what I'm typing, right? On line 111. So if you were to, let's say, set your starting point, let's say p one, P one, P two, and then meet somewhere in there. So this is what we were looking at. So based off of the values of p one mid and P two, were, what do you think p one and P two tell me with respect to the direction of the peak? Like what do you see as the relationship between p one p two and M element which in this case is actually a peak.

Winter Penguin: So P one, P two, so p one and P two have. In this particular case here, right, if they're both zero, looking for an element greater than zero to find a peak.

The Legendary Avenger: Your correct on that, let's do this. So you've said p two is greater than, we're looking for something greater than zero, and same case. And it will be the same, even if this was let's say negative something, or even even if this was, let's say, four, or six, and this was five, because this is technically still a peak. And so by virtue of this you're looking for greater than M less than that. So and this is how we define a peak, you see that? Say we had this condition where 3, 6, 7, we still don't know what's going on on the other side. So if this was our case, so let's say we had a case where p one is less than P two or is less than mid. Actually, this is the opposite here it is the opposite. And so this is greater than so say, P one is less than mid of which mid is less than P two. do you where do you think the next peak will be in this case? If you were to keep looking for the peak, where will we go?

Winter Penguin: We're still looking for a peak. I think I mean, we would be moving farther, farther left, right. So we would want our p2 to to be more, you know, closer to the midpoint. So moving that left or right, actually, does that mean?

The Legendary Avenger: No look at this case? So this is three went to six and then to seven, right? That's clearly a slope. Right? Yeah. And so, we given that we know that the in assuming that Okay, so let me just delete this. Assuming that this is continuously increasing, so 3679, whatever element it goes, so long as it continuously increasing, I know for sure that at some point, it will clip. So I made sure to find a cliff, so long as it's increasing, right. And so, so long as this is the case, and I know that I keep up I have to keep doing what

Winter Penguin: Oh, keep going to the right, right, because you want to find your cliff.

The Legendary Avenger: Exactly. So if it was the opposite case, then if this is greater then I would keep moving left. Does that makes sense?

Winter Penguin: Yeah

The Legendary Avenger: So if we we're to do this, so let's get this case. And then for this case, this is basically this. It's continuously decreasing, so my slope is going up, but this is the highest point. So I know that whatever the case at this point here, I'll click save. I'm looking for this peak, then I want to keep searching the left side, right? Yeah. And so how can I say if you were to think, think through bin search, in this case? How can you know like, you know, pick any point. So let's say you start here, like if we have to go back to the original approach, so say with any example element here, like, regardless of whether or where you start from, I know there is no inherent order in this case, but sorry, I'm kind of telling you the solution bit, but I'm hoping you code it afterwards. I know we're like kind of on time, but I want to at least make sure you see the logic. But even if we were to start here, let's say this was our P one. And our p, two derivatives is at the end. And our midpoint is somewhere there. Like regardless of where we're looking. If we were to look at our midpoint here, so say actually, no, not that we did the wrong thing. So say we were to start at the middle point. Put it at the middle point somewhere there. Delete this. If this was if this is our case, then what we're looking at here is we know 013. Like, I don't really need to know that this is the beauty of this question. I don't need to find all peaks. I know, either. There'll be a peak somewhere at the end or somewhere in the middle. And wherever my middle point is, it's telling me it's telling me what do you call it? It's telling me the direction of the peak. So if I was to start at this midpoint, and I look for the relationship, it will tell me the direction to go. So starting here with 013. I can see where do you think we'll keep looking based off of the condition here?

Winter Penguin: So we want to keep looking to the right, or well. So, so our P two is valid for M? Right? Wait, no opposite. Oh, wait. So our P one is valid for this M, our P two is invalid for this M for this particular midpoints. So you'd want to do some searching to the right and more to the right. Because eventually, worst case scenario we'll hit that negative infinity, got it? Yeah, I think the thing, the key point there for me was recognising there's always a peak because of the cliffs on both ends. Like I was saying, Oh, it's still a number. But realistically, no, it's not like they said it's negative infinity. It's not a this dot next size, like a negative system x size, which is a number. It's less than that. There is no, that will be exactly. That makes sense.

The Legendary Avenger: Exactly. But do you see how this logic will help you find at least a peak. So in this case, obviously, starting at the end, so you will set the ends to like p three P two here, and obviously your midpoint will be somewhere here, and so M. So you either go left of M or right of M to try and find the peak relative to the previous M until you either find a real peak, which in this case, it might land you somewhere 132, or you just get to the end if it continuously increases and so you're right. At the end, you'll still find a big regardless right? All right.

Winter Penguin: Thank you for that run through that. That would have been difficult to understand just reading leetcode solution

The Legendary Avenger: I hear ya. I don't know, if you have any feedback for me here, I know you'll still get a form afterwards. But is there anything I could have improved in terms of the interview overall, anything you think I could have done better.

Winter Penguin: This is not very helpful, but no. You did a great job in my opinion. I appreciate your very like detailed feedback on real strong, like specific points. I appreciate that a lot.

The Legendary Avenger: Appreciate it. But you'll get a form afterwards. Feel free to fill it out. Give me honest feedback. If anything pops up, by all means please tell me but overall, I really enjoyed this. This you know, just for context. If I was evaluating this, I would have easily given you a pass and I'm currently at Microsoft so give you a real interview based off of what I would have evaluated here.

Winter Penguin: It's good to hear Awesome. Thank you. Appreciate your time. I'll let you turn your fan back on.

The Legendary Avenger: Sounds good. Thank you, man.

Winter Penguin: Have a good one. Bye.