JavaScript interview with a Google engineer: Regular expression evaluator

[Purtonen]

*At an interview*
"Hi, are you familiar with regular expression matching?"
"Not really no"
"Okay bye"

[marceliwanicki]

-So are you familiar with regular expression matching?
-Not really
-Okay no problem
*gives regular expression matching question*

[matthewkazen]

Watching these make me feel a lot better about technical interviews. I still have yet to officially get one, but I know I am also not ready for a google or microsoft position. That being said I think a good step to always take is to look at the simplest case and solve that. Then progressively add the additional constraints.

For instance, just look at string matching -->
S - 'ab' P - 'ab'
S - 'ab' P- 'a'
S - 'ab' P- 'ac'

Once you solve that add the wild cards -->
S - 'abr' P - 'ab.'

S - 'ab' P- 'ab.'
S - 'uranus' P- 'ur.n.r'


Once you solve that add the asterick -->
S - 'tigggger' P - '.ig*er'

S - 'a*b*' P-
S - P- 'ur.n.r'

I just woke up so the test cases could be a lot better but the basic principle of breaking it down into easiest problem and adding to said solution

[abhishekkumar-gupta]

interviewing.io, you are doing a great job.

[juanb]

Tests split function: *Oh so it splits it up* LMAO

[kirklincoln]

"What language would you like to use?"
"Javascript"
"Haha no seriously"

[chrisdahms]

Ouch! This was a tough one. I feel for the interviewee.

[harrytsang]

Isn’t it ironic that it ended up using regex in the code to recreate a simplified version of regex?

[DemetryRomanowski]

For anyone thats wondering the best solution in my opinion is:

function check_match(s, p) {
let reg = new RegExp(p, "gi");
return reg.test(s);
}

[oleksandr]

formal languages is an interesting topic that covers transition graphs, finite automata, deterministic finite automata, cfgs and more

[DreamHomeGTA]

you are welcome to lookup the lib documentation

[coolmik]

It all fits into 22 lines of Haskell code, including comments and (optional) type signatures. Took me a little over 30 minutes. Recursion ftw

[anuragdhyani]

Not gonna lie, python a good programmer could destroy this Interview !

[Number-dpls]

I tried it in java before watching. I think I might have missed some edge cases, also wrote it assuming that it wouldent get invalid inputs. It passed all the example cases he gave at the start but there might be others that break it.

boolean CheckIfStringsMatch(String s, String p){
char[] S = s.toCharArray();
char[] P = p.toCharArray();
return checkChars(S, P, 0, 0);
}

boolean checkChars(char[] s, char[] p, int scount, int pcount){

if(scount>=s.length ){
return true;
}else if(pcount >= p.length){
return false;
}else if(s[scount] == p[pcount] || p[pcount] == '.'){
return checkChars(s, p, scount +1, pcount+1);
}else if(p[pcount] == '*'){
return checkChars(s, p, scount, pcount-1);
}else if(pcount +1 < p.length){
if(p[pcount+1] == '*'){
return checkChars(s, p, scount, pcount+2);
}else{
return false;
}
}
else{
return false;
}
}

[dadisuperman]

The test case line 14:
s="ab", p=".*" -> true.
This is wrong.
p here matches 0 or many instances of the same single letter which is discovered by replacing '.' with the character in s at the same index. Namely the letter "a"
However s has two different letters, which means that p fails to match one letter. Thus it should return false.
The correct test should be:
, p=".*" ->true.

I guess the solution, despite good, is wrong.

[ich_iel]

My solution (but it took me 2 hours):
function stringsMatch(s, p)
{
let _leftToMatch = s.split('');
let _leftToCompare = p.split('');

let _matchChar; // of s, char to match
let _comparisonChar; // of p, by this char
let _prevComparisonChar; // of p, buffer for *

while(_leftToCompare.length != 0)
{
// Early success
if(_leftToMatch.length == 0) return true;

_matchChar = _leftToMatch[0];
_comparisonChar = _leftToCompare[0];

// Direct match -> move on
if(_matchChar == _comparisonChar || _comparisonChar == '.') {
_leftToMatch.shift();
_leftToCompare.shift();

_prevComparisonChar = _matchChar;
continue;
}

// Absorb all subsequent chars of the kind before
if(_comparisonChar == '*') {
if(_prevComparisonChar == '*' || _prevComparisonChar == '.') return null; // Syntax error

if(_matchChar == _prevComparisonChar) {
_leftToMatch.shift();
} else {
_leftToCompare.shift();

_lastAstrixContent = _prevComparisonChar;
_prevComparisonChar = '*';
}
continue;
}

// If _matchChar != _comparisonChar
_leftToCompare.shift();
_prevComparisonChar = _comparisonChar;
}

// We matched all? -> Success
return (_leftToMatch.length == 0);
}

[TheProgrammer]

i decided to just do this problem and it honestly wasnt this complicated, u could use some recursion to handle the star, shifting the string and seeing what matches and the rest is just basic parsing... though he was doin it javascript, idk I wrote in c to deal with raw char arrays and pointers. overall this was a cool problem, idk if i would have been able to do it under pressure in like an interview tho /:

[billytodd]

do people usually write this much sudo code? like for normal work too?

[BobShanely]

Interviewing io only gives positive feedback I guess. From my experience this is a fail at Google because the candidate spent the whole time on the brute Force algo that didnt even pass the cases. Another candidate would make something that works, more efficiently and mention automata

[AnatolyPashin]

Looks like solution would fail for string 'aabb' and pattern 'a*b*b'.