# 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](https://www.youtube.com/watch?v=DduZ1-sMgOg)

### 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](/content/questions/regular-expression-matching/index.html)

### 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:** c*a*b  
  **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.