Python Interview with a FAANG engineer.

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 it 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, then 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.

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 an 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.
Immutable Brontosaurus: Right.
Cool Pumpkin: So, yeah, given an unsorted integer array nums, return the smallest non-negative integer that is not 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, 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 in 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.
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?
Immutable Brontosaurus: 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 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 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.
Cool Pumpkin: 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 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.

Feedback Highlights

Advice for Future Interviews

  1. Maintain good communication and analytical approach.
  2. Do not rush and think about simpler approaches.
  3. Always check in with the interviewer before coding and listen carefully for hints.