Python Interview with a JPMorgan engineer

Watch someone solve the smallest sufficient substring problem in an interview with a JPMorgan engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Smallest sufficient substring

Interview question

Given an array of characters and a string, implement a function that finds the smallest substring containing all the characters in the array.

Interview Feedback

Feedback about Supreme Armadillo (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

2/4

https://www.geeksforgeeks.org/window-sliding-technique/ https://www.geeksforgeeks.org/tag/sliding-window/ Recommendations: - more practise on matching problems to concepts - more communication of though process while coding - less reliance on environment for running code

Feedback about Stochastic Robot (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

really enjoyed this interview and got LOTS of useful feedback. interviewer really made sure to give me real interview experience. 10/10 Thank you so much buddy.

Interview Transcript

Stochastic Robot: Hello.

Supreme Armadillo: Hey, can you hear me?

Stochastic Robot: Hi, yeah. Welcome to this interview. This is gonna be 40 minute interview. We're going to divide it by the first five minutes you can tell me a bit about yourself, what are you preparing for? Next thirty minutes, I'm going to give you a task, which we're going to work on. And the last five minutes, we're going to exchange feedback. I'm going to tel you how you did, you're going to tell me how I did, and this is generally the plan. Sounds okay?

Supreme Armadillo: Yeah, that sounds good. Yeah. So I am preparing... I don't have anything lined up. But I'm preparing for just interviews, maybe something comes up. Right now I'm focusing on like data structure and algorithms. I haven't done any system design stuff. So yeah, that's where I'm at. I have about seven years experience doing full stack, I do everything. Backend, frontend, whatever.

Stochastic Robot: Okay. That sounds nice. I'm going to give you a task. Let me know if you've solved the exact same task so that we can try different questions. Yeah.

Supreme Armadillo: I'm going to change the language to Python. Can you hear me?

Stochastic Robot: Yeah. Did you did you see the task? Wait, I think it was...

Supreme Armadillo: Oh yeah. I see it now.

Stochastic Robot: Oh yeah, the comments sorry.

Supreme Armadillo: Okay given and array of characters and a string... Okay. I'll just create some examples. I think I just want to confirm. So input would be like input A B D and A B C. Output should be... A B D C. Yeah.

Stochastic Robot: Yeah, this is a correct example.

Supreme Armadillo: So, okay. So would input have multiple characters like this?

Stochastic Robot: Yeah. Let's actually for the base case, consider that the character array is going to be consisted of unique characters, meaning there's going to be no repetitions.

Supreme Armadillo: Okay, no repetitions okay. So what I'm going to do basically is since it's A B C I'll start with like... start here and then keep... just trying to think... going to like, create like a sliding window and move the window. So what happens if the input string is... So the answer, I just changed the input in the example, the answer there would be... So that would be the answer. Okay. Yeah. It took me a while to think. So yeah, I will start with input as A input and keep going forward... So can you see my cursor?

Stochastic Robot: Yeah, yep, I see it.

Supreme Armadillo: Keep going forward. So I removed A from the... I'll put that in a set, this A B C. If I see it, I'll remove it from the set. I'll keep going to B, remove B. I don't have D, so I'll do nothing. So I see A, but A matches the first character. First character of the input, so I'll just move the start from zero to one.

Stochastic Robot: Yeah. About... So you mentioned that you remove it from the set? Yeah. So when you reach A again, how do you know that this is a character we're looking for? If you remove this from the set, or do you keep another set?

Supreme Armadillo: How do I know if it's a character we're looking for? Oh, I see what you mean. It has to be because in the beginning, if it's in the beginning, right? So let's say A was not here, and you see A, so this would be an invalid set, right? We shouldn't have been adding A at all, in the beginning if it was not there.

Stochastic Robot: But more meaning of the... so when we have A B D. And so you're saying using a sliding window. So you correctly like started from there. And move up to A and see if it's there, but since you say you have a set, and you would have removed B and A here and you move to A and how do you know that this A is part of the important characters that you are given? Let's name them important characters because they're in the character array. And we're going to need them to actually identify that. So how do we know that A is there if you don't have it in the set anymore to to do an operation and check.

Supreme Armadillo: Yeah, so um, yeah, when we start the array, A is not here, right? So the window would not have A at all?

Stochastic Robot: No, I mean, I'm saying if we're at the stage where we have this window, we finalize this window and because we're already, let's say, I'm going to put a delimiter. So we're here and we will move both the A and the B, which are here. So these two are removed. Because I think you said by when you when you pop a character, you remove it from the set, right?

Supreme Armadillo: Yep.

Stochastic Robot: And we're at this point, we have A B as a substring, a temporary substring. And we moved over to the other A. So how do we know that this A is something that is of value.

Supreme Armadillo: Yeah, I understand. So if A is not here in the first place, and we start the window, right? We see A, we don't start it, we don't include it. So we won't ever have A in the first place. So that would be the window. Like the start pointer would not start from here if A is not here.

Stochastic Robot: A would be in the input. But when you hop over A, you said that you remove it from there.

Supreme Armadillo: From the beginning?

Stochastic Robot: No, from the set. Yeah. So we need A, we have A in the input. When we reach A, we remove it from the set, right?

Supreme Armadillo: Correct. Yeah.

Stochastic Robot: So when we encounter another A in the string, we can't really check if this is a character that we're looking for.

Supreme Armadillo: No, we can't check. Correct, yeah.

Stochastic Robot: So how can we repurpose that so that we can still check for... I mean, we can still label that we have characters and, and we have seen this character, as you said, so I like your use of the remove from set mechanic. But this basically eliminates our ability to check more than once. And if we have something of the kind of A A A B C, and we check the first A, we remove it from the set and reach here. So the first substring we're going to find is this. And to basically like find this, how do we know that we have to remove the A's to actually find the array because we no longer have a set to reference?

Supreme Armadillo: So what I was saying is that if your substring, right, if your current window is this, right? And you've already removed A B, you'll see A here. And the string starts with A, so that automatically implies that A has to be, like otherwise, why would this string start from a? Does that make sense?

Stochastic Robot: Yeah, what if the A is for instance over here? Then you just...

Supreme Armadillo: Oh, so you'll see A and you see one more A? You keep adding though, because you haven't seen seen C, you have no option but to add other A. So you just keep going till you see the C, right.

Stochastic Robot: Mm hmm.

Supreme Armadillo: You cannot do anything, you can only remove from the front, you cannot just remove from the middle.

Stochastic Robot: Right.

Supreme Armadillo: So okay, let's go to the point where we've seen it all, so how do we move from... Actually, let's... Yeah, this is actually a correct output. Okay. Yep. Okay, so let me think of a way to test the mechanic like you said like starting with... so you're basically checking when you... for after you've emptied out the set? Or you're checking if every new character is like the starting point of the substring? Correct?

Stochastic Robot: Correct. Yeah.

Supreme Armadillo: Can we do it... because I would be guessing. Wait, so can we have the input, which is again, A B C and it would have... then it would have something of the kind of Q B T A U C A Q B. How would it handle this?

Stochastic Robot: So yeah, same algorithm. So start will be here, Q is not here. I'll say okay, moving forward. So I'll see B. Okay. I'll say okay, B, so it'll be gone. Keep going. I see A, so gone. So that would be the answer.

Supreme Armadillo: But yeah, I mean.

Stochastic Robot: No. Yeah, I guess it'd be like, yeah, I can just return that. Like this could be the answer.

Supreme Armadillo: Yeah, I mean, the output is something like this. Can you look more in the way of actually instead of using the set as like as a true or false, kind of like is a binary storage, in the way of like it's either there or not there. And it's, it's like, if you remove it once you can't get it back. Can you use something more of the kind of a key value storage to actually...

Stochastic Robot: Yeah, I like that? Okay. Yeah. But at every step, if we do that... the only reason I was trying to do that was like at every step, we have to see if all the values are true, so that would mean like... That would be like...

Supreme Armadillo: But so this is going to be the complexity from every step, we basically check the whole, yeah, check that whole array. But maybe we can lower this down by being a bit... by optimizing a bit saying... Although this is like a good suggestion for lowering down the space complexity, in terms of the time complexity. So instead of checking the dictionary every single time that we have the correct number for each key, can we say that by the time our key reaches a certain value, this changes a counter, meaning if we have stuff such as, say, A B T, right? And we have our dictionary, such as like this, yes?

Stochastic Robot: Mhm.

Supreme Armadillo: Is there a way where, so let's say we iterate over it, when we find a character, we remove one, meaning we do a minus minus. When we leave a character behind, meaning, when we like, do something of the sort of this. So this way, we like leave the B behind, we kind of single out, we do a plus plus, because now we need to get... Can you use something like this, but choose one value and say, if we actually reach this value, this value means that it's a breaking point, not not a breaking point, but like the border, basically seeing it for the first time, to put it this way, have unique characters. So for instance, when you when you reach zero, you know that at the step where you reach the zero for C, you know that this is going to be counted plus plus, and this is going to be one value. Basically, this is going to be one of those, if those are the three checkboxes you have one checkbox is going to be checked. And when you have the number of checkboxes equal to the size of the array, you basically have that one solution, right?

Stochastic Robot: Yeah.

Supreme Armadillo: And going by this methodology, can you actually...

Stochastic Robot: What about what is suggested initially, though? Like you said, there's always one right, so A B C whatever. So next 25, 26 however many other characters? So basically, what you said, exact same thing. So if you see B, it becomes zero. And at every step you can just convert binary to int into that array, and if it's zero, then it means it's valid.

Supreme Armadillo: This is, this is actually a really good optimization for space. Although I'm gonna ask one question, do you know what is the worst case this is going to work on? This is only going to work on a subset of cases for the input.

Stochastic Robot: Only if it's.. like there's no two B's?

Supreme Armadillo: Yeah.

Stochastic Robot: Yeah, I think that cleared it in the beginning, that there's only one.

Supreme Armadillo: This is correct only when we have unique characters, this is going to work. So because we're because we're analyzing the base case, and the base case is said to have characters such as A A B B, let's leave this for now actually, this is a bonus question which I had prepared as sort of like the the last question after we finish the implementation, so it's good that you demonstrated this, but can we focus on like the base case, which is with these inputs and producing something to solve this for now?

Stochastic Robot: Okay. Yeah, that sounds good.

Supreme Armadillo: Can we just analyze the complexity that will follow for the solution that we agreed upon?

Stochastic Robot: Yeah. So... we are trying to optimize not looking at the whole hashmap? Correct? At every step?

Supreme Armadillo: Yep.

Stochastic Robot: So do you want me to... I mean, we are trying to do it for repeating characters, correct? Okay, so there could be multiple.

Supreme Armadillo: So, yeah, it's still the same the algorithm that you proposed, except that instead of looking at the hashmap at every step, meaning iterating to every key, we keep the variable, and we do only one lookup on the hashmap.

Stochastic Robot: Right. Okay. So let's say you're at a window, right? You see C and decrement the value to zero? How do you know that the window is complete?

Supreme Armadillo: Well, so, what will be the case in which... What will we need to reach our counter to to basically, how our values need to be seen?

Stochastic Robot: Yeah, sorry. Go ahead.

Supreme Armadillo: Yeah. So we have a counter, right? And this counter equal the size of the array, right?

Stochastic Robot: Counter equal size of the array?

Supreme Armadillo: Yeah, because like, that's, like all the other special characters, we need to find it. And if we basically... the way we set up the hashmap, is that if our key for our special character reaches zero, meaning that it's out near the iteration. And the reason we're picking zero is because if we find like, for these, for like, really, this is gonna go zero minus one minus two. And we don't want to count after that, because it's not going to be valuable to us. So yeah, and the time we reach the first one for each character in the array, we have a solution, right?

Stochastic Robot: No, yeah. Gotcha. Okay, so the count of characters matches. Yeah, okay. So yeah, we have a count variable and that should be the length of characters, special characters. Yeah, so if we do that, then it would just be a typical size of the input.

Supreme Armadillo: Okay. And for space complexity?

Stochastic Robot: The space would be, so it would be like special characters.

Supreme Armadillo: Okay, um, let's go get in depth.

Stochastic Robot: I'm just going to start with like the basic case I guess.

Supreme Armadillo: Don't worry about syntax. So, yeah, I guess focus more on actually writing the code. We won't be looking to immediately like run it or run it if we get ahead of time.

Stochastic Robot: Okay, no worries. Okay. I'm initializing the start. So when I try to like do this, I usually run stuff

Supreme Armadillo: If it's easier for you, go ahead.

Stochastic Robot: I'm going to just do this for now and I will change the content because I'm not here. I'm going to change the example here a little bit. Okay. That works for the base case. I'm just changing the input here. So we are expecting, so the answer here should change. Okay, like that. Yeah. So that's the smallest window. I mean, it won't work now. Okay, so after we see that we have to move the start pointer forward. What I'm going to do is... So the windows starts here from A A C E B. Like the first... So the window here starts from A B, like the first valid character. Starts with the first valid character. So I'm just going to move the start pointer to one more. So that would make the window invalid. But we also want to knock off like... So here, if we knock off A, we also want to knock off to like B. Like we don't care about A C E characters. While our counter is valid. So I guess that would be while is valid, I guess we have a function, right? So while that function is correct, just continue to loop, I guess. Because we want to when it's no longer valid, right?

Supreme Armadillo: Correct. But if we just remove... so for example, the window starts here, A C E B, eah. If we remove A, it'll say it's not valid, but we shouldn't have C E either in the beginning.

Stochastic Robot: Well, I mean, if we remove A, basically our windows stops, and we start moving forward again. So we're going to move to C E regardless because by the by the idea of how the algorithm works, because we always find the most compressed value, the smallest value that we can find from a given substring, a valid substring. So it doesn't matter if we remove it immediately or in the next iteration. It's still going to get removed.

Supreme Armadillo: Okay. Let's try with that. What happened there? Now we need to increment the counter.

Stochastic Robot: Let's call this the the end for the code phase of the interview and go a bit into the other part. So yeah, so judging by In the implementation, so you create a counts collection, which is your hashmap. You, oh, basically all on this. So remove the start until we reach a valuable character, I presume, is this what this is doing?

Supreme Armadillo: Yeah.

Stochastic Robot: Do we do that separately?

Supreme Armadillo: I guess we don't.

Stochastic Robot: Mm hmm.

Supreme Armadillo: Once you find a valid, you can just remove the invalid from the beginning. We can move the start pointer. Yeah, we don't really need to do it.

Stochastic Robot: Yeah, you're right. Yeah. So I would, I would say that the, the solution could could take the form where this if is valid is just a while loop. And this while runs if is valid, and, of course, you do everything related to finding if the substring is smaller than the one that you have. And then like, last character, but just to change it, if you understood, so if you're checking the brute force way currently, for the is valid, but well, how would you do it with the counter, meaning if we have a counter variable?

Supreme Armadillo: So it would be...

Stochastic Robot: But over here, do we want to increase the count in every single one that we find? Like if we just need A and B? And we have like...

Supreme Armadillo: Oh, yeah, you're right.

Stochastic Robot: Yeah, like this.

Supreme Armadillo: Yeah, yeah, you're right. If so, yeah, that would be an if condition.

Stochastic Robot: I mean, just you can just tell me what the if condition is because we are running out of time.

Supreme Armadillo: So if you're on A and you already found A, so you would see like the counter value would be zero. So you did not actually find one node. So then you won't decrement the counter? I mean, incremental counter.

Stochastic Robot: Right. So. Okay, yeah. Because... Yeah.

Supreme Armadillo: Okay. Make sure that you actually can do it.

Stochastic Robot: This is just more of a question like, would this and where would it break if we have the condition that our character right now can have multiple variables? We have multiple variables with duplicate. What I will say our input character today would be A A A B. Yeah, this is this is valid.

Supreme Armadillo: Yeah. So you mean, how would this break for the specific counter increment? Or in general?

Stochastic Robot: No, I mean, your solution? Like how would it handle this new input?

Supreme Armadillo: So it should, yeah, it should still work. It shouldn't matter to the solution. It's agnostic to the actual count. Okay, so it should not matter. Yeah. It should still work. It's not making an assumption that there's only one.

Stochastic Robot: Mm hmm. Okay. Yeah. And my my other question would have been about the bit array, but you you pointed out in the beginning, so I'm going to end the questions now. And I'm going to go into the feedback phase. So generally, I would say that this was a good interview. I would not give a pass, so if you haven't done interview here it's basically there is a checkbox which says pass or no pass and then start number, just description. So yeah, because you basically even though we had some issues here, like until like the time ended you, you hadn't completed this part. So I guess we went a bit over time, but scenario interview like I they would be pretty strict and saying 35 minutes or 40 minutes, the one they've agreed to at the beginning. This is the end, could just stop writing. But even going from there, like you implemented the bulk of this, I would say you could practice a bit more just on the first part where like pinpointing the solution, because during that you will manage to implement it and then, like, when I gave you gave you a hint, you understood what I was talking about you, you basically know how to solve it, but practice a bit, I would say, pattern matching a concept, a problem concept to given like, a given text or a given problem, because, you know, problems can vary a lot. So this is the windows sliding technique. So, I guess what they will they call it then for doing the basically sliding window approach. And I'm gonna show you a bunch of questions relating to that, well, like a bank of questions, let me just find the link, which you can practice on, of course. It's on the same website. Yeah. So that's that, I think, like 200 questions just on the same concept. Of course, they're not all the same. They're just like, tossing around and stuff around this concept. Other stuff that I will comment on? I would say, it would be very good if like, while coding it, just say, well, just lay out your thought process while coding. Don't let like the interview go into a bit into silence. Of course, this is not just your part, the interviewer shouldn't be someone who just like stay silent the whole interview, but while you're coding, aim to like give out your thought process, because if you don't say anything, I'm not gonna like start asking until you finish, because I don't want to like, get into it, like ask about every line. But by giving out your thought process, while you're writing, if you have some wrong assumption, or you're going the wrong way, the interviewer can just say, Oh, wait, what you just said, let's backtrack on that that or starts asking questions, more or less. So yeah, I guess this is one thing. And the other one is about the... I saw that you rely on the compiler. Well not rely on the compiler. So keep in mind, keep in mind, not every interview you're going to be given a compiler in a coding environment. A lot of the interviews that I think I've done is just a flat out like documents. They just like, you have a link to a document, which you and the interviewer have access to. And they just paste something on the doc file, and doesn't have any of that. So I guess at the beginning, focus more on implementing to just like, lay out your logic in code. And then if they ask, well, let's actually compile that... It's more on the side of don't rely on the on the syntax and running to check your logic because it might not always be available. But yeah, I guess those are just my my two points. To practice more a bit like the first part, which is like just labeling questions based on the text given. Communication a bit more while you're coding. And you basically ask some clarifying questions, which is good. It's always good clarifying questions. So the more you have, the better. I really like that you gave this so, when you have ideas such as those, always put them up, because this one was I was supposed to give it as a bonus question. But the idea that you told it before actually asked about it, and is a plus. And yeah, the third one is just don't rely so much on the environment. And yeah.

Supreme Armadillo: Okay, yeah. Yeah, that's really good feedback. Yeah. Yeah, I can see lots of errors. Yeah, it's been a while since I did sliding windows. Just not fresh off my mind. But yeah, I agree with, I was really quiet when I was writing code. And yeah, relying on the compiler. Yeah, that's really good feedback.

Stochastic Robot: Okay, thanks a lot for the time and interview. Hope it was useful. It was useful for me, and I'm gonna wish you a good day.

Supreme Armadillo: Yeah, same to you, it was very useful to me. Really good feedback. Thank you so much.

Stochastic Robot: Thank you, bye.

Supreme Armadillo: Bye.