3 ms·

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

b3b0p 8y ago
I got this same question from 2 other companies.
Jach 8y ago
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...
smsm42 8y ago
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 :)
- smsm42 8y ago
  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.
  - m0zg 8y ago
    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.
    - epicureanideal 8y ago
      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.
      - psurge 8y ago
        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])
        m0zg 8y ago
        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.
        epicureanideal 8y ago
        Thanks for the demonstration!
      - Kephael 8y ago
        This is LeetCode #10, this is a common question.
  - deleted 8y ago
    [deleted]
  - lazyasciiart 8y ago
    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)
    - senorsmile 8y ago
      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.
      - lazyasciiart 8y ago
        No, I was writing the regex parsing code. The regex was one of the inputs.
    - thijsvandien 8y ago
      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. ;)
      - lazyasciiart 8y ago
        The regex can be any string made up of any number of those three characters in any order.
NikolaeVarius 8y ago
A simple one isn't that hard to put together in an Hour. I've gotten this and thought it to be mildly interesting.
- lazyasciiart 8y ago
  You don’t even have an hour in an initial tech screen.

I got this same question from 2 other companies.

Jach 8y ago

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

smsm42 8y ago

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

smsm42 8y ago
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.
- m0zg 8y ago
  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.
  - epicureanideal 8y ago
    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.
    - psurge 8y ago
      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])
      - m0zg 8y ago
        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.
      - epicureanideal 8y ago
        Thanks for the demonstration!
    - Kephael 8y ago
      This is LeetCode #10, this is a common question.
- deleted 8y ago
  [deleted]
- lazyasciiart 8y ago
  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)
  - senorsmile 8y ago
    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.
    - lazyasciiart 8y ago
      No, I was writing the regex parsing code. The regex was one of the inputs.
  - thijsvandien 8y ago
    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. ;)
    - lazyasciiart 8y ago
      The regex can be any string made up of any number of those three characters in any order.

NikolaeVarius 8y ago

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

lazyasciiart 8y ago
You don’t even have an hour in an initial tech screen.