Javascript Interview (Google Engineer)

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

JavaScript Interview with a Google engineer

Watch someone solve the regular expression matcher problem in an interview with a Google engineer and see the feedback their interviewer left them.

JavaScript interview with a Google engineer: Regular expression evaluator - YouTube

JavaScript interview with a Google engineer: Regular expression evaluator

Interview Summary

Problem type
Regular expression matcher
Interview question
Write a function that takes two strings as arguments s (a string to match) and p (a regular expression pattern) and return a boolean denoting whether s matches p

Interview Feedback

Feedback about Fresh Albatross (the interviewee)

Great job, as I said. Your communication was excellent and you did a good job at initially talking through / breaking down the problem, which allowed you to find some flaws in your approach before starting to write code. Writing comments in your code, and walking through your pseudocode manually on examples, were also good strategies. You also identified one of the harder cases in this problem -- matching "bbb" against "bb" without consuming all the 'b's matching "b" -- on your own. Although we didn't get a chance to test the code on this example, using recursion and branching is the right approach. Finally, testing your code incrementally was also a really good idea.

Feedback about Paisley Wallaby (the interviewer)

I think it was a really good interview. It was a challenging prompt and he gave a lot of great constructive feedback at the end, which I really appreciate since this indicated to me that he was engaged throughout the entire process. Thank you!

Interview Transcript

Paisley Wallaby: Hello can you hear me?
Fresh Albatross: Hi, yes I can.
Paisley Wallaby: Great how are you doing?
Fresh Albatross: I'm good how are you doing?
Paisley Wallaby: I'm good, what language would you like to use?
Fresh Albatross: I'd like to use JavaScript if that's okay.
Paisley Wallaby: Okay. Are you familiar with regular expression matching?
Fresh Albatross: Not really.
Paisley Wallaby: Okay. No problem. So the question is: write a function that takes two strings as arguments s and p and return a boolean denoting whether s matches p. So s is the string to match and p is the pattern. So p is a sequence of any number of the following: so you can have a lowercase letter which stands for itself, you can have a dot which matches any character, or you can have a star which matches zero or more occurrences of the previous single character. So the star always only applies to the previous character, there's no parenthesis or anything in this subset of regular expressions. So some examples….

Fresh Albatross: Yeah totally. Could I delete everything about line 31?
Paisley Wallaby: Go ahead and delete that, that's just boilerplate.
Fresh Albatross: And I just want to clarify: line 18 it works because there are 0 occurrences of 'c' any number of occurrences of a and one occurrence of 'b' and that's why it is true.
Paisley Wallaby: Yep, that's right.

Fresh Albatross: Alright so right now the biggest challenge is dealing with the star. Basically I think one thing that needs to happen for sure is the p string has to be split and kind of segmented out based on where you see dots and where you see starts.
Paisley Wallaby: Yeah I think you're on the right track there and think about using recursion and basically what the different pathway is like what choice you're making at every step.

Fresh Albatross: Exactly. So something in my function between lines 57 and 58 needs to be updated.

Paisley Wallaby: Yeah sure.

Fresh Albatross: Alright, I think this would be my solution. Do you have any suggestions or recommendations?
Paisley Wallaby: Let's see. I guess I'm not entirely clear what recursive calls you're making because you talked about trying each possible number of characters in the recursive calls but I'm not seeing that represented here as a loop or anything. Yeah okay.

Fresh Albatross: Okay. For every element in my split array, let's say let patternArr = p.split('*'); so for every element, let's call it i for now. This will iterate over. For every element in the split array, I would pull out the subString which would be just.

Paisley Wallaby: You're welcome to use it if not what's a lowercase letter.

Fresh Albatross: Okay only for lowercase letters you said?
Paisley Wallaby: Yeah.

Fresh Albatross: Great. Nice talking to you and enjoy the rest of your day.
Paisley Wallaby: See you. Thank you so much.
Fresh Albatross: Yeah no problem, bye
Paisley Wallaby: Bye