Hacker News Reader

Comment by lazyasciiart | Hacker News Reader

I tech screened at Facebook and the whiteboard question was to partially implement a regex parser.

Meanwhile some of us are just happy if candidates know of the existence of regexes, even if they forgot the exact usage, and can mention using them rather than trying to write a parser from scratch when given a problem statement of extracting phone numbers of various formats from several thousand unstructured files of web page scrapes...

How partially? I could probably do a very simple one, without backtracking (though they'd need a big whiteboard if they want full code there) but if it's something like PCRE then I don't think Facebook headquarters have enough whiteboards to fit the code :)

Though I just realized "regex parser" can mean either "parsing some text using regex" or "code that compiles regex syntax into some kind of data structure but does not actually do anything else". The latter obviously is a much easier task.

It's neither. There's a DP solution for this problem and a recursive solution without memoization (with exponential complexity). The shortest solution I have seen was 18 lines of code.

Please show me a regex parser in 18 lines of code! Even 36! I did this exercise once and it took 100s of lines, I think using C++... but it's been a long time. Maybe it's significantly shorter in Python? But still 18 lines is impressive.

I probably screwed something up, but here's a 16 line attempt in Python, where the regex specials are limited to .?:
def matches(pattern, s): if len(pattern) == 0: return True c = pattern[0] assert c not in ("*", "?") if len(pattern) > 1: if pattern[1] == "?": return ( len(s) > 0 and c in (".", s[0]) and matches(pattern[2:], s[1:]) ) or matches(pattern[2:], s) elif pattern[1] == "*": for i, d in enumerate(s): if c not in (".", d): break return any(matches(pattern[2:], s[j:]) for j in range(i, -1, -1)) return len(s) > 0 and c in (".", s[0])

Pretty much something along these lines, except it's also required that both pattern and s end at the same time for a full match (this complicates the base case a tiny bit). The C/C++ solution looks more elegant because you can use pointers. Note that this particular version requires no prior knowledge of the algorithm and can be solved on the spot fairly easily.

Thanks for the demonstration!

This is LeetCode #10, this is a common question.

The question was: Write a method that can take in a regex and a string and return whether the string matches it, with the regex limited to the characters . * ? (And backtracking is definitely where I started coming unstuck)

Ah, that's definitely different than I understood your first post. You're writing a regex to match a given type of string. The regex parser is in the language itself, consuming what you've written and evaluating it.

No, I was writing the regex parsing code. The regex was one of the inputs.

If the regex is really just a sequence of dots followed by a question mark, asterisk or nothing, thus cannot contain literals, the only thing you need to check for is the length of the string.
The minimum length will be the number of dots without a quantifier (i.e. exactly one character). If there is any dot followed by an asterisk, there is no maximum length. Otherwise, the maximum length will be the minimum length plus the number of dots followed by a question mark.
Writing the code for this is left as an exercise to the reader. ;)

The regex can be any string made up of any number of those three characters in any order.

I got this same question from 2 other companies.

A simple one isn't that hard to put together in an Hour. I've gotten this and thought it to be mildly interesting.

You don’t even have an hour in an initial tech screen.

Reply on news.ycombinator.com