Java Interview with a Google engineer

Watch someone solve the regex matching problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Java interview with a Google engineer: Regex matching - YouTube

Java interview with a Google engineer: Regex matching

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).

Read more about the questions

• Regular Expression Matching

Interview Feedback

Feedback about Cashmere Panda (the interviewee)
Advance this person to the next round?
No
How were their technical skills?
3/4
How was their problem solving ability?
2/4
What about their communication ability?
3/4

One thing you did that was great was taking the time to step through examples by hand before running your code. As you noticed, this is a good way to find bugs in your proposed algorithm before you even start coding.
We talked quite a bit about what you could do better, but to summarize, I think doing well in interviews like this is 50% problem-solving skills and 50% having a mental "library" of problems you've seen before, and being able to pattern-match so you can apply what you know about a similar problem to one where a few of the details are new to you. The latter is easier to build with practice than the former -- the more practice problems you do, the more likely you are to already have seen a similar problem to the one you're being asked to solve in an interview.
That nebulous "problem-solving skills" piece has something to do with being willing to take a step back and rethink your strategy, as we talked about; also knowing how to recognize when a problem can be solved with recursion. Practice does help with this too: the more recursive algorithms you study, the more you'll notice when a problem can be broken up into smaller subproblems.
If you want to keep working on this problem on your own, you can compare your work against the solution here: https://leetcode.com/problems/regular-expression-matching/description/.
I thought your communication was good and you did a good job of explaining what you were thinking. This is a challenging question, and I know you said you were new to practice interviews, so don't be discouraged and keep practicing!

Feedback about Paisley Wallaby (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

Paisley Wallaby: Hi can you hear me okay?

Cashmere Panda: Yes I can.

Paisley Wallaby: Great, how are you?

Cashmere Panda: I'm good, how about yourself?

Paisley Wallaby: Good. What language would you like to use?

Cashmere Panda: I would like to use Java so I will toggle this to Java.

Paisley Wallaby: Great cool. Are you familiar with regular expressions?

Cashmere Panda: I'm familiar with what they are and yeah. I do know what they are.

Paisley Wallaby: Okay well this question is about matching a simple subset of regular expression so nothing too complicated. So, write a method that takes two strings as arguments. S a string to match against and P a pattern and returns a boolean denoting whether S matches P. P can be any number of the following: a lowercase letter which stands for itself, the dot character which stands for any character - the wild-card, or the star which must follow another single character and stands for zero or more occurrences of that character. So star can never be the first character in a pattern and it only applies to the one character character before it. And you can assume that the pattern is well-formed so that it only includes these things and that the star is used properly and that it's not the empty string.

Examples

• Pattern: ab
  Match: ab
  Result: false
• Pattern: a*
  Match: a
  Result: true
• Pattern: .*
  Match: any string
  Result: true
• Pattern: .
  Match: two characters
  Result: false
• Pattern: cab
  Match: 0 c's some number of a's and a b
  Result: true
• Pattern: a*.
  Match: aa
  Result: true

Feedback Summary

1. Communication Skills:
The interviewer noted that you communicated effectively during the process, often expressing your thought process and rationale for your decisions.

2. Problem-Solving Approach:
Your approach could benefit from practice. Focusing on enhancing familiarity with problems similar to regular expression matching may help in quicker recognition of patterns.

3. Recursion:
Incorporating recursive solutions for certain complex problems like this one can simplify your approach and increase your effectiveness during interviews and problem-solving in general.

Conclusion: Keep practicing, leverage the insights from this interview experience, and don’t hesitate to explore different solution approaches, especially recursion.