We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

Python Interview with a FAANG engineer

Watch someone solve the first missing positive problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

First Missing Positive

Interview question

Given an unsorted integer array nums. Return the smallest non-negative integer that is not present in nums.

Interview Feedback

Feedback about Cool Pumpkin (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

*** Strengths and what went well This is not a simple problem, it has layers and nuances and you were able to see most of them very quickly. Your intuition was good and always leading you to the right direction. Your communication was very good, I was able to follow your thought process, ideas and intentions, which is super important in an interview. You were confident but careful to test your approach to see if it covers everything. You were able to explain what you're doing while coding, which brings clarity and makes it easy to follow you. I'm happy with your coding and debugging skills, you were quick and confident, the code was clean and readable. You were also able to quickly identify and fix any inaccuracies, and make the code working correctly. Lastly, I liked the enthusiasm, and I could see that you are genuinely interested in the problem and having fun. *** Areas for Improvement The main thing I noticed is that you are too quick at moments. Sometimes is good to take a quick pause, take a step back and look for any simple things you might have missed. It's a good practice to first explain your approach, than check if the interviewer agrees and wants you to proceed with the code, and only then start coding. Listen carefully for any nudges or hints from the interviewer. If they are not clear enough, ask to clarify. Taking hints is an important aspect of an interview. It can save you time and help you find the perfect solution. *** Advice for future interviews Keep up with the good communication, analytical approach and sharp thinking. Do not rush. Take a moment to notice if there's a more simple approach or a simple way to implement. Check in with an interviewer before jumping to coding, and always listen carefully for any hints.

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

Interview Transcript

Immutable Brontosaurus: So if you're familiar with the problem, just tell me.

Cool Pumpkin: Okay. I've seen this problem before, but I don't remember how to solve it. Is that all right? Yeah.

Immutable Brontosaurus: That's fine.

Cool Pumpkin: Yeah.

Immutable Brontosaurus: Okay. So tell me how you understand the problem and maybe come up with an example or two and let's go through a couple of examples to see what should be the solution.

Cool Pumpkin: Yeah, of course. All right, so let me read the problem. So in an unsorted array, return the smallest possible integer that it's not present enough. So from my understanding, like, if I have a array smallest possible positive integer. So if I have an array that was like 0, 2, 3, 4, the result would be 1 because that's the smallest positive integer. And then if an unsorted Array nodes. Okay, so let me just change it around. 4, 2, 3, 1. And can negative numbers be a part of this?

Immutable Brontosaurus: Maybe we can go with instead of positive, let it be non-negative.

Cool Pumpkin: Okay.

Immutable Brontosaurus: It's just a slight modification.

Cool Pumpkin: Okay. So then here the result would be 0. Because it's zero is not negative, right?

Immutable Brontosaurus: Right.

Cool Pumpkin: So in this unsorted integer array, could the values be negative? Like can it be negative 1, negative 3? Okay, interesting. Okay, and then this scenario result would also be 0, 3, like negative 1, negative 8, and here the result would be 1. Okay, so yeah, given unsorted integer array nums, return the smallest non-negative integer that is present in nums. Okay, so the first thing I notice is unless 0 is in the nums array, the answer will always be 0.

Immutable Brontosaurus: Right.

Cool Pumpkin: Yeah, so I'll just write The answer will always be 0. It's 0. It's not in the array. Another question I have is, what happens, will I ever have a case where the unsorted array nums is like empty?

Immutable Brontosaurus: No. Let's say the minimum number of elements is like 1.

Cool Pumpkin: Okay, so guaranteed at least one element. And then in that case, if that one element is not 0, then the answer would be 1. So it would be like 0 or 1. Okay. So let me think. Given an on return the smallest non-negative integer that is not present in nums. Okay, the smallest non-negative integer. Okay, so one way, like my brute force solution, is turn nums into like a set. And then so I'll have like a num set. Or actually I'll just write the code for it. Def solution.

Immutable Brontosaurus: So.

Cool Pumpkin: Numset equals a set of nums. And then for my brute force solution, I start from zero all the way to the max value. And then I check if this value is in the numset. And then If it's not, that's my answer. That would be my super brute force solution. Okay. And that would work.

Immutable Brontosaurus: So what would be the complexity here?

Cool Pumpkin: Yeah, for sure. For the space complexity, it would be O, where n is the elements and nums, because I'm making a set of everything of the nums. For the time complexity, technically it's for time complexity it will be whatever the max value is, which is bad if my nums array was like 1 to a really large number. But actually it wouldn't be that bad because as soon as I get to 2 it would end. So space complexity it's O and then for the time complexity I like a part of me wants to say constant because it'll always go just like to that at most to the max number.

Immutable Brontosaurus: But well, is it really constant or like so think about this, like what can be the maximum result that you can get? If your nums have like n elements.

Cool Pumpkin: Okay. Oh, n elements. Okay, I guess if I'm answering your question correctly, I think. Okay, this is not constant in the case I have like a sorted array like 0 1 2 3. It would be O of n because I'm checking like 0 1 2 3 and then I'm checking the entire array and then.

Immutable Brontosaurus: 4. Okay, so right. All right. But basically what I was pointing at was that max value cannot really be larger than n. Oh, so what would be the first scenario?

Cool Pumpkin: Like the first scenario, like 4132?

Immutable Brontosaurus: No, no, worst case scenario. Like, what numbers does the nums have to have? In order to for this loop of yours to go on longest.

Cool Pumpkin: Okay. Oh, another question. Another question is, are duplicate values allowed in this, like, unsorted integer array?

Immutable Brontosaurus: Sure.

Cool Pumpkin: Sure. Okay. Yeah. So the worst case scenario where this would take the longest is if the array is-- like nums array is already in sorted order. So it would check 0, it would check 1, it would check 2, it would check 3, and then it would just keep going until the max value. So it would keep going to n.

Immutable Brontosaurus: OK. And what would be the result?

Cool Pumpkin: The result would be whatever it would be the last value plus 1. Okay.

Immutable Brontosaurus: So, that's n+1, right?

Cool Pumpkin: Yeah, if it was in sorted order. And, yeah.

Immutable Brontosaurus: What do you mean in sorted order?

Cool Pumpkin: So, I think my question oh, like, on line 32, if the array was like 0, 1, 2, 3, 4, 5, 6, 7, 8. But if the array was like -1, -8, 51, 16, or 0, like if it wasn't in sorted order, the answer would be 1.

Immutable Brontosaurus: But what would happen if you have 0, 1, 2, 3, 4, and so on in order, but it's not really sorted?

Cool Pumpkin: Oh, I guess. Oh, it's not really sorted, but you still have the numbers 0, 1, 2, 3, 4. So, yeah, it would be n+1. Okay.

Immutable Brontosaurus: So, it doesn't matter if it's sorted or not. You're really making the numset, so it's not. It's not important, right?

Cool Pumpkin: Yeah.

Immutable Brontosaurus: Okay. So let's say yeah, so we have this solution and maybe we can Maybe you can run it for one or two examples just to see whether it works fine.

Cool Pumpkin: Nums equals 4 1 2 print and then wait, I'll just try all the way. Okay, I will run it. Yeah, 001.

Immutable Brontosaurus: Okay. Good. So let's see now if we can improve this. So, the way to improve it was we could actually, how can we reduce the space complexity?

Cool Pumpkin: Okay. How can we reduce the space complexity? Currently, the space complexity is O because I'm just using a set of the nubs. The reason I did use a set is because I want to keep track of all the elements in the array, but do I really need that? Because doing an unsorted integer array returns the smallest non-negative integer that is present, the smallest non-negative integer. Return the smallest non-negative integer. Okay, so I'm thinking about different types of data structures that I could use to store it. So I'm thinking of when I saw smallest, I was like, can I use a heap somehow? And then so I'm thinking about the approach of using a heap currently, but I don't think that's the right approach because if I use the heap, I wouldn't be able to know what's missing, like what's not present. So a heap, a stack. I don't think a stack would be helpful. So. Hmm. Return the smallest non-negative integer that is not present. 4 1 3 2 this okay now I'm currently like thinking and exploring about like a linked list or a graph or like Some like that type of like structure so I'd be able to detect. But.

Immutable Brontosaurus: In all of those cases, you would probably end up with the same space complexity, right?

Cool Pumpkin: Okay. Yeah.

Immutable Brontosaurus: So is there a way to like think about this? Don't use any additional data structure, just use the array that you already have.

Cool Pumpkin: Okay.

Immutable Brontosaurus: And don't worry for now, don't worry about time complexity. So now we want to focus to reduce the space complexity. Let's say we have a bottleneck with space and we want to minimize it and time complexity doesn't matter.

Cool Pumpkin: Okay. Okay. So the first idea that popped up into my head, oh, it's not a right idea, but the first idea was what if we use the values as the index? But I was like, that doesn't make sense because what if I have a really large like really large value and then my array is small. That doesn't make sense. Now I'm currently thinking what if I do something like I mod it with the array size. I'm currently thinking about negative marking, marking something like an arbitrary value to see that's been visited I guess. Okay, yeah, so like my current idea is like I, let's see, if I have, what the heck, 4-1-3-2, if I have 4-1-3-2, and then the length of the array is 4. That doesn't make sense. I was thinking like, since I have a 1, I can mark index 1 as -1, index 0, 1, 2, that would be that. But then what happens to my 4? Because then my 4, if I modulate it at the length of the array, it becomes 0. But I don't want, that's not the behavior I want. So I'm currently thinking, I definitely feel like the negative 1 marking or like marking the nums array, the initial array is like the right path to go. Let me think. Use the array i. I'll just put, I'll change my test case a bit. Okay, 0-1-2-3-4-0-1-2-3. Okay, 4- negative 0. 0-1-2-3-4. Okay, so in the case they're all negative 1, I would be able to just return, like return the max value plus 1 if they're all present. If there's a case where, let's go back, 1-2-3-4. I'll check to see if it's in the dimensions of the array. In this case, I have 1, 2, 3. I go to index 1 and I mark that -1. I go to index 2 and I mark that -1. Then I see this 3 and this 3 is out of bounds. I don't do anything there. Then I scan through the array again and then I notice that index 0 is not -1. Then I can return 0. Return the index. That is not -1. Then -1 is just an arbitrary value. I can put it like any value. Just for like this demonstration. And then let's see if I had like 0, 3, 5, and then 2. So in this case, 0 would be marked -1, 0, 1, 0. 1, 2, 3, 4, 5, 6. Okay, in this scenario, yeah, that would make sense because it would return 1 because it would return the first index that's not negative 1. So the first index that is not negative 1. Mm-. Okay, so in this, in my three test cases that I made, the solution works, but I feel like there's an edge case that I'm missing. Of course, if it's already a negative one, but, like, yeah, the negative one doesn't matter. But, yeah, there's something. I feel like there's an edge case that I'm overlooking.

Immutable Brontosaurus: So what if you have minus one? Instead of 6?

Cool Pumpkin: Like 0 minus 1? Yes. Yeah, okay. So yeah, negative 1 is just like a filler value. So let me simulate this again. So first I would go to 0. Oh, no. I would read 0. So I would go to index 0 and mark that. For this scenario, I'm just going to mark this as the character a. Then I read the negative one. That's also out of bounds, so I wouldn't do anything. Then I would go to index five. That's also out of bounds, so I wouldn't do anything. Then I read two, and mark that as an a. Now, when I traverse through my nums array one more time, as soon as I reach an index, That's not an A. That's when I return that index. And then this would be 1, and that would be the first missing number, because I didn't find it when I was traversing through the original array.

Immutable Brontosaurus: Okay. And you want to make these markings in the same array, right?

Cool Pumpkin: Wait, I was actually just thinking about that. If I make the marking in the same array, there's a scenario where I mess up something later in the future. I was like, I should make another array, but then I remember you mentioned I should use the same array. Oh, man.

Immutable Brontosaurus: With the additional array? This would be fine. You could make the markings and then just go through this array and completely okay.

Cool Pumpkin: Yeah, but the same array issues.

Immutable Brontosaurus: Let's see, maybe we can overcome those issues.

Cool Pumpkin: Okay. So I'm just going to switch my test case. So now it'd be this one. So 2-0. 2, -1, 5, 0. I'll make this 3. In this scenario, I would read 3, 0, and then I would mark this A, and then I would read, wait, yeah, yeah. Okay, overcome. Those.

Immutable Brontosaurus: Issues.

Cool Pumpkin: Okay, so I'm currently thinking I need to be able, like, once I make those markings, I need to be able to store the index that I was initially at. So I'm not sure if this is the right approach, but I was thinking instead of marking it just A, I could mark it like A0. So the marking has information of the index it was holding. So when I go, when I'm traversing and I see A0, I can update the index is pointing from.

Immutable Brontosaurus: Ah, I see. I see what you want.

Cool Pumpkin: Yeah. Yeah, that's like interesting solution.

Immutable Brontosaurus: Yeah, yeah, it's creative. Yeah, but I don't really like this mixing integers and strings or whatever, you know.

Cool Pumpkin: Yeah, yeah, yeah. Okay, back to the drawing board.

Immutable Brontosaurus: Yeah, let's think about like Maybe we can just use numbers.

Cool Pumpkin: Okay, just use numbers.

Immutable Brontosaurus: Yeah, but in many languages, you wouldn't be able to put anything but numbers.

Cool Pumpkin: So.

Immutable Brontosaurus: Yeah, just think about what number can you put in a specific index? That won't interfere with any other number. You had a problem if you put -1 because there could be -1 in the array, but maybe there could be a number that you can put and it would be fine. There would be no issues at all.

Cool Pumpkin: I'm not sure if you can do this in other languages. I was thinking of putting infinity, like float infinity, because you do that in python.

Immutable Brontosaurus: But so you want to put something that is outside of range?

Cool Pumpkin: Yeah.

Immutable Brontosaurus: Yeah, well, okay, maybe we can go with that.

Cool Pumpkin: Yeah. So, like, mark it as infinity. But then you, but now i'm thinking, like, if I mark it as infinity, How do I keep track of the change in indexes, like you mentioned, if I'm using the same array? How do I keep track of things that I've changed? I wonder... zero. Okay, my first thought was instead of just performing one swap, or like one mark as I mean. So when I go to three, instead of just marking the index at three, I was thinking of what if I could kind of do it recursively. As in, three would call the function to mark zero, but then zero would call the function to mark three. So then three would be marked and zero would be marked. And then it would just propagate down or across the array. It would jump from spots to spots. Jump to spots to mark the array. That's my solution.

Immutable Brontosaurus: That's interesting.

Cool Pumpkin: I would have a function that's like and it would be the index. And then if nums is true, So yeah, that's what it would look like, I guess. So then I would call 3 and then nums of 3 0, then it would call it that. And yeah. So that's how I would do that. I wonder if this works. I think it should. It's so interesting, so fun. So yeah, so just like to implement my solution for I comma n and enumerate nums. I would just, if n does not equal float infinity, Oh, max value plus 1. Okay, so after implementing my solution, this is oh, after implementing my pseudocode, this is what I think the solution would look like.

Immutable Brontosaurus: Okay, so let's see. Let's now analyze this mark function for a bit.

Cool Pumpkin: Yeah.

Immutable Brontosaurus: How would it work for some specific example?

Cool Pumpkin: Okay, yeah, for sure. I'll just use I'll write it right at line 32. Okay, so the first iteration, I'm at I equals 0, and then I-- and then 3 does not equal infinity, so I call Mark. So I call Mark of 0. Wait, that's not correct. I have to call Mark of nums at i. I call Mark 3. Then at mark 3. Oh, yeah?

Immutable Brontosaurus: Yeah, I just said okay.

Cool Pumpkin: Okay. Then at mark 3, I check nums at 3, which is 0, 1, 2, which is 0. Then I call again, so mark them 0. Now, on the way up, It sets-- I call it mark is zero. Okay, okay. Okay, I see the issue. The issue now is this issue now is just going to be an ever ending loop. 3 is going to call 0, 0 is going to call 3, and 3 is going to call 0 over and over again. Yeah. Yeah, okay. How do I fix that? One thing I can do is have like okay, one thing I can do is is store in a temp variable and then if temp, have it temp and then it will be num of I equal to infinity and temp does not equal float infinity. So to go through it again, I call market three and then a temp is a zero. And then okay. Oh, and nums attempt. Okay, and I called. Okay, now it should work. Now it stops that ever ending Loop, because first I call my three. Temp becomes nums at 3, which is 0. Then nums at 3 becomes float, becomes infinity, so I mark it. And then I call mark of temp, which is, yeah, there. Then temp. Becomes infinity and then nuns of zero becomes infinity and then it just stops because yeah, it just stops because nuns of temp Infinity. Oh, wait, not numZippedTemp. Just temp. Yes. Okay, yeah, that's how the markov function would work.

Immutable Brontosaurus: Okay. So, yeah, let's. Let's start it.

Cool Pumpkin: Okay. Awesome. I'm excited. I'm gonna use this test case, too. All right, run.

Immutable Brontosaurus: Oh.

Cool Pumpkin: List index is out of range. Oh, shoot. Oh, I forgot about that. If I... Wait, that makes no sense. Because it shouldn't be called. Oh, what if the first... Okay, okay. What if the first index is out of range? So if I is it... Okay, if I is less than zero, Or I is greater than or equal to length of nums is returned. Yeah, there you go. Right. Okay, for I in range length of nums, oops. Okay, 001. Okay, yeah, those are right.

Immutable Brontosaurus: Great, great. Yeah, but okay, now let's see. So now you have all of. Yeah, you tell me what's the time complexity was the space complexity.

Cool Pumpkin: Yeah, for sure. Now my space complexity is constant because I'm using the array and I'm using the provided array, and the only thing I'm doing is sending this max value, so it's constant. For my time complexity, for my time complexity first, I'm For my tie complexity, in this for loop from line 42 to 44, that is O because it's traversing through every element. Then another thing is even though it's calling the mark function, at most, the mark function will only visit every element at most once because it marks it and it will never mark it again. And that's what happens in the for loop too. If n does not equal full infinity, so this would be O of n. And then to finally get my result from line 47 to 49, I'm just traversing through it again. So that's also O of n. So it would be the total algorithm is O of 2n, which is just O of n. That's my understanding.

Immutable Brontosaurus: Yes, yes, correct. But there is actually a problem because I would argue that your space complexity is still O(n).

Cool Pumpkin: Oh, like the call stack, kind of?

Immutable Brontosaurus: Right, because you're using this recursive method, which can be called n times. So basically, because of the stack, you would end up with O(n) space. That makes sense. The idea The idea is good. So I would just suggest that maybe you can avoid recursion by doing it iteratively.

Cool Pumpkin: Okay, I'll try that. So doing it iteratively. And then the main reason I wanted to do recursion is because I wanted to know I wanted to store where to mark things. But of course I can do that iteratively. So how can I do this iteratively? In my example, if I mark something, I want to be able to go to the next item as well. Okay. Okay, wait, I think I got it. So I'm going to make those changes in line 44. So just for now, I'm just going to put while true. I'm going to make this variable called pointer, and then the variable pointer is going to be at the pointer. So if I'm at 3, the pointer will be at num at i. Okay, I think I got it. So if the pointer is at nums of i, The temp equals the pointer. So in this scenario, wait, let me put it back. Yeah, so three, the pointer, yeah, nums of I, the pointer would be zero. Then I would do nums of basically just putting my recursive function in like iteratively like that and then not mark and my pointer. Wait, hold on, that doesn't make sense. What I mean is my pointer is nums of i, so my pointer is 0. Then nums of i, nums of i, so slow infinity. Okay, okay. Temp equals.

Immutable Brontosaurus: So one pointer be three at the start.

Cool Pumpkin: The pointer should be three. Oh, yeah, I think so. Right, wait. It's like the idea is there. I'm like, almost. This is it, but I'm, like, currently thinking about it.

Immutable Brontosaurus: Okay.

Cool Pumpkin: My pointer. Okay, my pointer is three, and then temp equals pointer. That doesn't make sense. Oh, temp equals nums of I. Okay, so now. I equals and then my pointer equals temp. So now my pointer goes to 3. Okay, and then while pointer. And while my pointer is in bounds, my pointer is less than 5. nums of I. That's not true. It'd be nums of pointer. Yeah, nums of pointer. So my temp is zero. And then nums of pointer. And then pointer. Yeah, I think this makes sense. So the pointer equals n, so pointer is 3. Then temp equals nums of pointer, so temp becomes 0. And then 0 becomes the float infinity. And then the pointer becomes zero again. So that's when I update my three. Yeah. Okay, I think this works. Okay. And. Yeah. Can I run it?

Immutable Brontosaurus: Yeah, yeah, sure.

Cool Pumpkin: Okay, awesome. Clear. Oh. Hello, world. Hello, world. Oh, okay. Okay, it's an infinite Loop. Else break.

Immutable Brontosaurus: -2, 0, 0, 1. All right. Yeah. Good.

Cool Pumpkin: Yeah.

Immutable Brontosaurus: Okay, so maybe you can put just one example more. Go with like minus 2, minus 1, 0, 1, 2, 3, 5.

Cool Pumpkin: Minus 2, minus 1, 0, 1, 2, 3, 5. One, two, three, five. Yes.

Immutable Brontosaurus: And another one where you don't have a five.

Cool Pumpkin: Okay. All right. In both these, they should both return four.

Immutable Brontosaurus: Yeah.

Cool Pumpkin: Yeah. Great.

Immutable Brontosaurus: Cool, cool. Nice. All right, so excuse me.

Cool Pumpkin: For space complexity, now it's for sure constant space. And then for time, even though I have like two loops and like one nested loop, It should still be O of n because I'm not revisiting things that I've already marked. So time complexity is O of n. Right.

Immutable Brontosaurus: So you're actually marking each index at most once?

Cool Pumpkin: Yeah. Yeah.

Immutable Brontosaurus: Yeah, cool.

Cool Pumpkin: That's it. Awesome.

Immutable Brontosaurus: Awesome.

Cool Pumpkin: Yay. So, not so fun. Yeah.

Immutable Brontosaurus: So, okay. Yeah. I think we can stop here and go to some feedback, right?

Cool Pumpkin: Okay. Okay.

Immutable Brontosaurus: So let me tell you what I noticed. So first, communication. It was really good. Like, you're really communicative and you express your thoughts clearly. And I was always able to understand what is your thought process and what you're thinking next. And we were always on the same page. And that's really important for interviews. So you should just keep doing that. And do that knowingly, because it's really important for the interviewer to feel that he understands what you're trying to do and what are your intentions, what we want to accomplish.

Cool Pumpkin: Okay.

Immutable Brontosaurus: Because of multiple things, right? He wants to assess how are you thinking, what is your thought process, how is it going, how is it working? And it also enables him to like direct you to some other approach or to encourage you to go with this approach that you've chosen and stuff like that. So it's a really good thing and I think you nailed it.

Cool Pumpkin: Okay. Sure.

Immutable Brontosaurus: So about coding skills, I think it's really good. So I don't have any issues with your code. You're coding fairly fast, but it's clear and it's clean. There's no any major issues with the code that I would like to point out. It's really good and I don't have any issues with that. As for your problem solving, let's revisit from the beginning. First you analyzed the problem and you understood it from the start. That's really good. But then you wanted to clarify some things and you asked me some clarifying questions. And that's really good. You should keep doing that. And it's always good to ask all the clarifying questions that you can come up with at the beginning. Yeah, because you don't want to miss out something or miss some edge case or some requirement that wasn't clear enough because of ambiguity or whatever, and then you end up solving some different problem. So always clarify things, and when you feel that everything is clear, then you can proceed. So you asked me about negative numbers, about what is the minimum number of elements, stuff like that, and that is all fine. And then you almost immediately came up with this approach with the set, right? And it was good. It's a good approach, actually, yeah, because most of the time it would be optimal. all It's time complexity and space complexity is all then, but yeah, it's pretty good. And you found this approach right from the start, so that's really good. Then I wanted to direct you to these other approaches where you don't have often space complexity.

Cool Pumpkin: Yeah.

Immutable Brontosaurus: And here I noticed something. So while you fairly quickly started exploring this approach where you mark found in the seas, right? There are more simple approaches that you could explore. That's why I tried to direct you by telling you that time complexity doesn't matter now. It only matters that we reduce the space complexity. So one thing that you could come up with is just to source the array. And when you sort the array, then, right, you see the approach, right?

Cool Pumpkin: Yeah, sort the array and then count from the, yeah, that makes sense.

Immutable Brontosaurus: Yeah, you just start from the beginning. When you encounter zero, you know that you found zero and then you just need one missing number and that's it. So it's all of N and basically the iteration is all of N, but since you have the sorting, it's N again. But the space remains reduced, so that's the most straightforward thing. So it's not bad that you didn't come up with it because you started exploring the more advanced and correct approach. Approach, but it signals me that maybe you can pay attention to these little details because, okay, with some other problem, maybe there is no more optimal way. What I want to say, maybe if you reduce space complexity, you have to increase time complexity. And maybe you started exploring some different option that is not really possible, but you missed the simplest thing, you know? So maybe you just, you can pause and go a bit more slower and try to go one step at a time.

Cool Pumpkin: Okay, slower and one step at a time. Yeah. Okay. Yeah.

Immutable Brontosaurus: Just it feels that you rushed a bit there, but the actual intuition was pretty good and correct, and I really liked it. So basically this, so you figured that marking could be a way. But then you notice that you can have problems with later indices or later numbers as you progress through the array. And then you try to think of a way to overcome it. And actually, the recursion idea was really good if you forget about the time complexity, right?

Cool Pumpkin: Yeah. Yeah.

Immutable Brontosaurus: But basically, maybe it's the same point here. If you paused a bit to think about why is the recursion approach really useful here? Because you're basically leaving stuff from later. And then you just avoid this problem of dealing with later indices. You don't want to mark some index five before you reached index five, because then you lose whatever was on that place, right?

Cool Pumpkin: Yeah.

Immutable Brontosaurus: But actually, if you Take a careful look. Say you're at index 3, and there you encounter something like 10, and you want to mark the index 10. So now basically, You need to preserve what was on the index 10, but you don't really need this tree anymore.

Cool Pumpkin: Okay, yeah, that's true.

Immutable Brontosaurus: So you can actually switch the value 3 with whatever was on index 10. Right. And then you just proceed with the same iteration. You don't have to increase the index if you just made the switch and marked some later index. And you just do the switching if the, let's say the target number was not infinity because you don't want to put infinity where it doesn't belong to. So that's a bit more simpler approach. And it just relies on the fact that when you analyze one number at one index, you don't actually need that number anymore. You know that you want to Mark that index, but this index is now free, so you can use it.

Cool Pumpkin: Okay, that makes sense. Yeah.

Immutable Brontosaurus: And your later approach was, I mean, this final one was pretty good. And you were able to explain why is it still often, and that's pretty good. The approach that I just pointed out is a bit more, maybe simpler to implement and to read, but it's not really much different than your approach.

Cool Pumpkin: So that's true.

Immutable Brontosaurus: Yeah, that's good. Okay, so the point is that maybe you can just from time to time pause and try to step back and see, is there something simple that you are maybe missing and that you can use to overcome your issue?

Cool Pumpkin: Okay. So pause, take a step back and then like try to keep it simpler. Pause. Yeah.

Immutable Brontosaurus: And also like try to so we're not done yet. If you have more time, I can like continue, right?

Cool Pumpkin: Oh yeah, yeah, I have as much time as yeah, I have time.

Immutable Brontosaurus: Okay, good. So basically, maybe pay attention to the hints or subtle directions from the interviewer because many times the interviewer either want to nudge you in a different direction or want to encourage you or want.

Cool Pumpkin: To.

Immutable Brontosaurus: Direct you to some conclusion or something like that, you know, and you always want to be like cognizant about that and listen to any hints that are provided. As was with this, like you could easily fall into this trap of going deep down some path, you know? And when interviewer tries to direct you some other way, you could be already invested and you want to keep proceeding to this path because you feel it could be right. But if it's not, then you're in trouble, right? And since you missed the hint, that could be a bad thing. So just keep in mind that anything that interviewer says, try to process it and maybe iterate if you're not really understood what was trying to be communicated. Maybe you can clear out and just have a dialogue. That's completely fine.

Cool Pumpkin: Yeah, that makes sense. I remember you mentioning n plus one and I was like, huh? And I was a little confused by it and I was concerned about time, so I just kept chugging along and it kept going. But yeah, I should have stopped and asked more about it.

Immutable Brontosaurus: Yeah, that was one point. And the other point was the same thing when I mentioned that time complexity is not important right now. You just want to focus on reduced space complexity because I wanted to direct you to this sorting approach. And this n+1 thing was another instance of the same thing. So what I was getting at with this n+1 is for you to see that basically, Yeah, what shows that you didn't really understand me is that you later put max value to be maximum of nums.

Cool Pumpkin: Oh yeah, and it should just be like the length of nums.

Immutable Brontosaurus: Yeah, and actually it works with both. Approaches. If you put just n length of nums or max nums, it would be the same thing. But the n actually carries some deeper information for you, and that was what I was getting at. And the information is that you cannot really have the solution that is greater than n. Because the worst case scenario is that you already have all the numbers from 0 to the n minus 1, and then the n is sold. And if there is some higher number, then there is also a number that is missing and that is smaller and that number will be a solution.

Cool Pumpkin: Okay, that makes sense now. I don't know why it was making sense to me 20 minutes ago, but now it's clicking.

Immutable Brontosaurus: Okay. And why this insight is important? Because actually this conclusion can justify removal or ignoring negative numbers or numbers that are outside the range. Because you know that the solution will be either inside the range or it will be n. So it cannot be outside the range and it cannot be some negative number, you know, so that's why you can just ignore the negative numbers and numbers greater than n. And you'll be fine. So you knew this intuitively and when you tried to come up with the marking system, then you notice that you have a problem with maybe negative numbers, maybe numbers that are greater than length of the arrays. But then you just decided to ignore them and that was correct and your intuition was fine. But this is actually the reason why you can do it.

Cool Pumpkin: Okay.

Immutable Brontosaurus: Yeah. All right. So then we ran the program a couple of times and a couple of times I noticed that you were fixing things and it was really good. It was quick. You noticed everything that was like a minor bug or something and you would fix it immediately. And yeah, I pretty liked it. And actually, when you implemented the recursive function, and when I directed you to just analyze how it would do, you quickly noticed that it would go on infinitely and there's a problem with it, and you were able to fix it. That's just great. You shouldn't really expect to write the cleanest and completely correct code right from the start, without any bugs or issues. So it's always expected to have some kind of minor bug or whatever, the approach is important, but the ability to clear out those Little mistakes is really good to be shown and I think you nailed it.

Cool Pumpkin: Awesome, thank you.

Immutable Brontosaurus: Yeah, so a couple more things I wrote down, just let me see. Yeah, so this is one little thing that I would like to tell you. At a couple of places, you said, so first you said at one point, oh, this is so fun.

Cool Pumpkin: Yeah.

Immutable Brontosaurus: Yeah. And later on, when you were about to run your code, you said, oh, this is exciting. And those two points are really great. So it should.

Cool Pumpkin: Okay. I was worried.

Immutable Brontosaurus: Yeah, you were worried that. That it's not supposed to do. Yeah.

Cool Pumpkin: Okay. I shouldn't do that. Oh, man.

Immutable Brontosaurus: No, no, no. No, no, no. Just. I. I was going to tell you that you should, actually, because it was. Okay. Yeah, I have an impression that maybe the connection is a bit slower. So yeah, we'll get to that. So yeah, I think it was good actually because it showed the enthusiasm and it showed that you're really enjoying the algorithms and problem solving and that's really important thing, especially for fangs or similar companies, you know. So it's a big difference to have a candidate that just you can see that he doesn't enjoy the problem solving process. And okay, maybe some problems are not really fun, but if you're having genuinely fun, you can express it and it's fine. It would really be like a nice signal for the interviewer that you really like what you're doing and I think it's important. And I always try to catch this signs of how much the interviewee is interested in problem solving because it tells a lot about the candidate, about your approach and mentality and everything. So just that was great and I wanted to point it out. No problem. So debugging, I already told you the max issue, yeah, I already mentioned that that's like n+1 thing and yeah, that should be it. So yeah, my main improvement thing was about try not to rush. Because even if in this case you were like close to the perfect solution, you should avoid rushing because maybe in some other case you won't be that close to the perfect solution and you don't want to go any deeper than necessary before realizing that you have something simpler.

Cool Pumpkin: Okay. Yeah.

Immutable Brontosaurus: And you should allow interviewer to take a step back and to direct you some other direction, other approach. So, yeah, just don't rush it. And try to look for a bit simple things, maybe things that you are missing and that's it. But it's not a huge deal actually and I think this overall was pretty good.

Cool Pumpkin: Awesome, thank you. No problem.

Immutable Brontosaurus: Okay, so we can end now and I will write down all this stuff so you can have it in writing and yeah, that's it.

Cool Pumpkin: Hope you have- yeah, thank you so much. Yeah, I hope it's useful. I wish- oh yeah, it was super useful. I wish this one wasn't anonymous. I would love to like connect with you and just like learn more from you. But yeah, thank you.

Immutable Brontosaurus: Well, actually there is an option to like, to share like your identity and to connect So you'll see after the meeting.

Cool Pumpkin: Okay, awesome. Thank you. Bye-bye.

Immutable Brontosaurus: Yeah, no problem. All right, thank you. Take care.

Cool Pumpkin: All right, you have a great day. Thank you.