Java Interview with a Microsoft engineer

Watch someone solve the regex matching 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

Regex matching

Interview question

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Interview Feedback

Feedback about Benevolent Mammoth (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

He needs speed, little more practice would help him to solve the problem

Feedback about Strident Pumpkin (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

3/4

Interview Transcript

Strident Pumpkin: Hello?

Benevolent Mammoth: Hello.

Strident Pumpkin: Hey.

Benevolent Mammoth: Hi.

Strident Pumpkin: Hey, so like so can you just briefed me about your background, so just if you can just tell me your years of experience or like so that I can decide upon the complexity of the question?

Benevolent Mammoth: Okay sure yeah, well I have two years of Android development experience.

Strident Pumpkin: Ah so like okay so do you want an easy problem or an intermediate or like a challenging one?

Benevolent Mammoth: Not easy, probably medium.

Strident Pumpkin: Medium okay, all right. So what would be your programming language?

Benevolent Mammoth: Java.

Strident Pumpkin: Java, excellent. So I mean have you taken any interviews?

Benevolent Mammoth: Yeah.

Strident Pumpkin: Okay so the question which I'm gonna give like it has like 45 minutes of time for you to like attempt, like just try out the problem. So have you seen this problem in... probably this is one of an intermediate problem which you can see in leetcode, or have you seen this regular expression matching? So your programming language is Java right? So let me paste the question over here in line number 10. So you have been given an input string X and pattern b. So you need to implement, you need to check, if the given string and pattern matches with each other. So like there are like we are taking only like two regular expressions one is star and one is dot. So dot matches one any single character and star is like it matches none of the characters or one or more characters of the preceding element. So let me make a couple of test cases for you to get a clearer understanding. So if you see this given input a and the pattern being a, so output is going to be false because the pattern didn't completely match with the given string so this is one test case and I can give you another test case. So yes. So if you see the pattern, the string is aab and the pattern is c*a*b, the output is true. So this is because c can be repeated 0 times so it can be neglected which means like it can matches 0 times, so c* can be neglected and like we have a*b, which is like so which a* can serve aa and b matches that b. So the whole pattern and the string matches with each other so the output is returned as true. And there is one more special case which I would like to tell you here, so here are the one more special case. It's not exactly the special case, but it comes in the logic so... If you have a pattern called .*, so . is like matches with any single character and that character can be repeated zero or more times. So in this case, your output would return true.

Benevolent Mammoth: Okay so that means that like a dot... okay.

Strident Pumpkin: I would ask you to work out few examples with a pen and paper and like try to understand the problem more about this problem, so once you get the pattern, like it's going to be easy for you.

Benevolent Mammoth: I'm just trying to think of edge cases. Here I think this case is... for example in this case if I only like did a*, I would like simply just went like... so if I saw a*, then I would like simply go check these a's.

Strident Pumpkin: Mm-hmm.

Benevolent Mammoth: In that case I would miss this. I would have in this problem I'm gonna have to have multiple ways... So if I have a*, every time I go different paths, one is like when it's zero, then it's only one character of the before it start. Then two, you know, like that so like every possible way you can do it and then because in this case if I only try to do it two times then it will fail but in this case it has to be true. But I can't really know that it's going to... I have to do one, I have to actually see all the the paths, different solution, different ways. So when I see a *, I would recursively call the function either on like zero or plus one I guess, plus one yeah. So every time I would see a *, I would try to do it, I will try to match it either once or... I mean either zero, so like either 0 or 1... plus 1. So either 0 or plus 1. It has to be or problem yeah, because if either... if any possible ways I can go, so like I can I can diverge in many possible solutions and if any of those is right, then it has to be true.

Strident Pumpkin: Okay okay.

Benevolent Mammoth: If this case the only thing is this case is when I have... so when I have a .... matching it should be fine. So . can match any character and it's okay. So yeah, let me just do like a quick way, maybe pseudocode. I'm gonna have to look, so whenever in a pattern, I will have to look one beyond. So like if I see aa, I have to see if there's a * there or not after it. So if there isn't, I'm just gonna try to match a and a.

Strident Pumpkin: Okay.

Benevolent Mammoth: With the star, I would have to do this special case where I do multiple ways for like a color cursor which so yeah... If it doesn't have a star and just like try to match then, then compare. This will include that logic too, you know. But so the interesting thing of course that's the easy part the interesting thing is when it's a *, so if the pattern, i plus 1 has a *, then either like recursively do two cases: one case would be when I do... so then one case is I advance... i is equal to i plus two. Do not do anything else. And second case actually don't advance i, but... In the second case I have to do at least one...

Strident Pumpkin: So I... just tell me this: the variable i like is the pointer for the pattern right?

Benevolent Mammoth: Yes.

Strident Pumpkin: Okay okay, good.

Benevolent Mammoth: So yeah the first case I would just like do i equals i plus 2, so let me skip, skip the character and the star, meaning that, it's the case where like it's a zero occurrences of the character. So in the second case would be actually like I try to match the character.

Strident Pumpkin: Mm-hmm.

Benevolent Mammoth: I think that's it and like I was thinking the problem I had was like where do, when do I stop but like when I do this and then the call recursively, it will try to do the zero at any some point for sure.

Strident Pumpkin: Okay so will you move, so in your second case like which point would you move? Like is it gonna be the pattern pointer or the...?

Benevolent Mammoth: So compare and then after you compare, the string pointer, that would advance.

Strident Pumpkin: Okay string pointer is there.

Benevolent Mammoth: Okay I think that's basically it if I'm not mistaken. The problem cases where like I run out of the pattern, then I will have a case where I return false. Oh actually so like the case 1 and 2, I have to do or, so like that, both of them. So yeah and then if I run out of the pattern I return false or like if s... yeah you will have like the pointers, the pointer has to be like finished both at the same time, if not I will return false.

Strident Pumpkin: Mm-hmm.

Benevolent Mammoth: So yeah, that's a special case.

Strident Pumpkin: So that will be your base condition for the recursion right?

Benevolent Mammoth: Yeah that's the base case. So I guess it can be that and this like where I compare each character. Actually no. No it's not a base case, if else. So yeah, the base case would be if the pointers one is finished and the other is not, it is at the end, then I return false in that case. Do you think I should start coding or there are some something else.

Strident Pumpkin: Yeah go ahead.

Benevolent Mammoth: Okay.

Strident Pumpkin: I mean your thought process seems to be good, correct. So you can start coding and let's come up with test cases.

Benevolent Mammoth: Okay cool.

Strident Pumpkin: Let the function return boolean. Like whether the pattern matches so...

Benevolent Mammoth: Okay. So what I'm going to do is if I plus is actually greater than or equal to... I should have done three probably the pattern whatever, but okay I'll just change it up here real quick.

Strident Pumpkin: Oh you're just switching i and j.

Benevolent Mammoth: Yeah yeah. So if i < s.length() and I guess can be better multiple ways. So if either of those is finished and the other is not, then yeah... otherwise if that char at j plus one is equal to *, then do something and then else do something else. So else is the easy one. Else is actually... else all I have to do is return... When I don't have a *, I just compared the character, so if it's a ., then I just return true and advance the pointers and if it's else, I just compare the characters and return that... so in the case of *, I actually... what I do is... what I do is I call match expression... okay so I think I missed something.

Strident Pumpkin: I mean already see your recursion. Okay.

Benevolent Mammoth: Oh... so wait so I compare, so what I'm going to do is, I will in the second case I compare the two and then if... If the character, so like I compare the characters and then I advance the i by one. So if they don't match, I can right away return false because that means 1 occurrence doesn't work.

Strident Pumpkin: Right so in line number 59, so if the character the pattern is dot, you just return a true.

Benevolent Mammoth: If the pattern... I was thinking that should be true yeah, because it matches any kind of character right?

Strident Pumpkin: Single character right?

Benevolent Mammoth: Single character yes.

Strident Pumpkin: Okay. So with that you will end the recursion if you just find just the dot operator?

Benevolent Mammoth: Oh, I see what you mean. Will it end recursion. So let's see. I see what you mean. You're right, so in that case, what I'm gonna do. I don't know like for some reason like I'm doing it recursively but I didn't think recursively there, so the dot then I advance this and this and actually just continue that returning any... And if in this case actually... if else... I guess but notice that this is the same as you so it could be combined, I'm not 100 percent sure. Oh actually it's not the same. So okay and then actually I never return true actually, so the case where it's actually true where I'm finished with both, and that's it you know? I think that's it's based on my logic before.

Strident Pumpkin: Can we run through a few examples with this?

Benevolent Mammoth: Of course... This should be like a helper function you know? Whatever for now. Okay so in this case what will happen is, I have a so and then it's zero and zero, then I check these, these are going to be fine, this is going to be... so I reach this one. Oh I see.

Strident Pumpkin: It would go out of the... do you think j plus 1 will go out of bounds?

Benevolent Mammoth: In this case it does go on bounds because there isn't...

Strident Pumpkin: What will we do to fix that?

Benevolent Mammoth: So I'm gonna... so I do it all this so if if...

Strident Pumpkin: If j plus 1, if it is less than p.length(), then you can check right?

Benevolent Mammoth: So I have to do that in only here and in the else statement, they do it every time so, how do I only...

Strident Pumpkin: Really is gonna be true?

Benevolent Mammoth: You know yeah it shouldn't be true, so I think it is somewhere here where like I do greater or equal... Actually wait, so in this case what's going to happen is aa, then a right? So what I'm going to do is in this case will not happen...

Strident Pumpkin: Like what if your last character doesn't match with the last character. If both the pattern and the string are in the last character with a pattern pointer and the string pointer okay. And if the last two characters doesn't match, do you want to return true or false.

Benevolent Mammoth: So if the last characters is match, then I return true.

Strident Pumpkin: Yeah but in your line 53, so when the pointer reaches the last character, both the pointer reach the last character.

Benevolent Mammoth: Like if it goes beyond the length right?

Strident Pumpkin: Right.

Benevolent Mammoth: Both of them. So but I thought this case would do it... So in this case should have been that j got out of bounds, but s didn't, that's why I have to return, so actually so that that means that j was greater then p.length() - 1 and i was less.

Strident Pumpkin: So can I say this...

Benevolent Mammoth: Okay yeah, so in this case it should be the... okay so then with that case...

Strident Pumpkin: okay can you test this? Really is it false? I don't think so, it's true.

Benevolent Mammoth: So let's see... so what should have happened is it should have like in one of the cases where it should have actually gone beyond, so like you would skip c* and... so let's see... so yeah it should have been that it skips this c*, then in this case so it does j is j plus 2, so we'll stop here. Then you would match maybe a once and in this case, so if it is equal 1 then you will advance the i pointer. So let's see... So one case is that...

Strident Pumpkin: Mm-hm.

Benevolent Mammoth: One case is that, so in this way one time it will do the like this for sure. And then it will at that point... it will again do the same thing. We're not interested in that case, we know that it's going to turn false, I'm gonna try to go through the path that it actually turns true, because only that one has to return true. So I did that then in my case I compare... so like I compare those if they are the same, then I actually called it recursively where I advance these. Again I would do the same thing where I do this and then I advance this one. And then I would do this at a point to so like I would skip it in this case, it's both at b and that means that I'm gonna do this where I return i plus one and so like it has to come here. In that case, it should have hit my this case, where i is greater than that s.length() - 1, and j > p.length() - 1 and should have returned true, or the other thing could be it actually did this one and return false.

Strident Pumpkin: Yes.

Benevolent Mammoth: So that means if I is greater or equal to s.length(), in this case it is true. And j is less than p.length(), that is not true. Or i is less than... That's not... so that's actually not true. So let me just like print out, make a print statement so I know exactly what's going on here. Following my logic, it should have been returned true, so I'm not sure what's gonna... so I'm going to do is the prints. Not too helpful because of all the recursion, let's go downriver.

Strident Pumpkin: I would change in a line. So I mean we are almost in the end of the interview, so like I mean the problem lies with the base case. So if you set your base case right, so for example like I'm trying to tweak your code...

Benevolent Mammoth: So it actually tries to compare these, i and j but like the end, one of them is beyond.

Strident Pumpkin: If one of them is different the line number 52 should have saved you.

Benevolent Mammoth: So in case one, j is greater or equal to p.length().

Strident Pumpkin: Alright, so if you alter the base condition like, then you would be able to like get the correct solution, so as far as the problem is concerned, I mean you have got the solution except the base case, that's why I told you like if you try multiple test cases or if you think of multiple examples you will get to know the pattern, so once if you know the pattern so the half of the question is going to be very easy, so I guess you did a good job here, like when we talk. So what do you think would be the time complexity of the solution?

Benevolent Mammoth: So in this solution the time complexity would be... could be exponential?

Strident Pumpkin: Right so it's going to be exponential, so can you think of any ways to reduce those exponential thing? To a polynomial solution?

Benevolent Mammoth: Memoization maybe?

Strident Pumpkin: Right so while the recursion tree you will see the overlapping subproblems, so either memorization or your dynamic programming technique would help you to identify and reduce the time complexity, so ideally I mean the solution which is expected for this question would be recursion and like we would have asked you for an implementation into memorization or dynamic programming. So yeah, this is a hard question but you were able to pull it out, so good.

Benevolent Mammoth: Thanks.

Strident Pumpkin: Thank you so much.

Benevolent Mammoth: I wanna thank you for your time and thank you for the interview, appreciate it.